Efficient Sum-Based Hierarchical Smoothing Under \ell_1-Norm

Details Efficient Sum-Based Hierarchical Smoothing Under \ell_1-Norm Efficient Sum-Based Hierarchical Smoothing Under \ell_1-Norm

2011-08-08

arxiv.org/abs/1108.1751v1

Computer Science

Data Structures and Algorithms

Scientific paper

We introduce a new regression problem which we call the Sum-Based Hierarchical Smoothing problem. Given a directed acyclic graph and a non-negative value, called target value, for each vertex in the graph, we wish to find non-negative values for the vertices satisfying a certain constraint while minimizing the distance of these assigned values and the target values in the lp-norm. The constraint is that the value assigned to each vertex should be no less than the sum of the values assigned to its children. We motivate this problem with applications in information retrieval and web mining. While our problem can be solved in polynomial time using linear programming, given the input size in these applications such a solution might be too slow. We mainly study the \ell_1-norm case restricting the underlying graphs to rooted trees. For this case we provide an efficient algorithm, running in O(n^2) time. While the algorithm is purely combinatorial, its proof of correctness is an elegant use of linear programming duality. We believe that our approach may be applicable to similar problems, where comparable hierarchical constraints are involved, e.g. considering the average of the values assigned to the children of each vertex. While similar in flavor to other smoothing problems like Isotonic Regression (see for example [Angelov et al. SODA'06]), our problem is arguably richer and theoretically more challenging.

Affiliated with

Also associated with

No associations

Rating

Efficient Sum-Based Hierarchical Smoothing Under \ell_1-Norm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Sum-Based Hierarchical Smoothing Under \ell_1-Norm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Sum-Based Hierarchical Smoothing Under \ell_1-Norm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-190509