Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge decomposition

Details Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge decomposition Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge decomposition

2010-03-25

arxiv.org/abs/1003.4942v2

Computer Science

Data Structures and Algorithms

1) 12 pages 2) Updated 2nd Version: Removed section 3.3 of 1st version, updated references (for more details see www.cs.cmu.

Scientific paper

Let $P=(P_1, P_2, \ldots, P_n)$, $P_i \in \field{R}$ for all $i$, be a signal and let $C$ be a constant. In this work our goal is to find a function $F:[n]\rightarrow \field{R}$ which optimizes the following objective function: $$ \min_{F} \sum_{i=1}^n (P_i-F_i)^2 + C\times |\{i:F_i \neq F_{i+1} \} | $$ The above optimization problem reduces to solving the following recurrence, which can be done efficiently using dynamic programming in $O(n^2)$ time: $$ OPT_i = \min_{0 \leq j \leq i-1} [ OPT_j + \sum_{k=j+1}^i (P_k - (\sum_{m=j+1}^i P_m)/(i-j) )^2 ]+ C $$ The above recurrence arises naturally in applications where we wish to approximate the original signal $P$ with another signal $F$ which consists ideally of few piecewise constant segments. Such applications include database (e.g., histogram construction), speech recognition, biology (e.g., denoising aCGH data) applications and many more. In this work we present two new techniques for optimizing dynamic programming that can handle cost functions not treated by other standard methods. The basis of our first algorithm is the definition of a constant-shifted variant of the objective function that can be efficiently approximated using state of the art methods for range searching. Our technique approximates the optimal value of our objective function within additive $\epsilon$ error and runs in $\tilde{O}(n^{1.5} \log{(\frac{U}{\epsilon}))}$ time, where $U = \max_i f_i$. The second algorithm we provide solves a similar recurrence within a factor of $\epsilon$ and runs in $O(n \log^2n / \epsilon)$. The new technique introduced by our algorithm is the decomposition of the initial problem into a small (logarithmic) number of Monge optimization subproblems which we can speed up using existing techniques.

Affiliated with

Also associated with

No associations

Rating

Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge decomposition 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 Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge decomposition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-556623