Closest arithmetic progression to an array

Question

Given an array of $N$ integers, having the option to increase or decrease its elements, the problem is to find the closest integer arithmetic progression. That corresponds to the smallest difference between the elements of the array and the elements of progression. Thus one needs to minimize the sum of absolute differences. It is a restriction that the values must be integers: 1,ドル 5, 10, 14, 19 \to 0, 5, 10, 15, 20$

It is easy to solve it with the help of linear programming without restriction to integers. But even the simplex method and other similar algorithms are not sufficient because they can handle cases when $N \leq 10^5$. In this case, the integers can be rather large (i believe up to 10ドル^7$). Is there any algorithm for solving it in $O(N\log^k M)$ or even $O(N),ドル where $M$ is the maximum integer value of an array?

Answer 1

Let's call your array $a$. The goal is to find $x,k$ such that $\sum|a_i-(ix+k)|$ is minimized. Fix $x$ and replace $a_i$ by $b_i=a_i-ix$. Now the goal is to minimize $\sum|b_i-k|,ドル so $k$ is obviously the median of $b$. Since it's not hard to solve this problem with fixed $x,ドル it's natural to consider if there's any monotonicity on $x$.

Note that the error can be written as $\sum_{b_i\in upper,円half}b_i-\sum_{b_i\in lower,円half} b_i$. Substitute $b_i$ by $a_i-ix$ and we'll get a formula like $c-(\sum_{b_i\in upper}i-\sum_{b_i\in lower}i)x,ドル which is linear. The optimal $x$ can be found trivially in this case, but the order of $b$ changes when $x$ incerases (decreases). Let's see how it changes.

Scan $x$ from negative to positive. At some points a "swap" may happen: originally $b_i<b_j$ but after this point $b_i>b_j$. This only happens when $i<j$. If they are originally in the same half then nothing happens. But if originally $i$ is in the lower half and $j$ is in the upper half, now $i$ moves to the upper half and $j$ moves to the lower half. This increases the slope by 2ドル(j-i)$. Median should be excluded from both halves if $N$ is odd but the conclusion "slope is increasing" remains.

Now we know the error is a convex function so we can find the minimum by ternary search on $x$. Since we can compute the error in $O(N)$ if we fix $x$ and the range of $x$ is bounded by $O(M),ドル the total complexity is $O(N \log M)$. (Here I consider the cost of each arithmetic operation as a constant.)

Answer 2

The continuous case is that of finding the Least absolute deviation. Not easily tractable, but you may find libraries that are more efficient that the LP formulation.

Iteratively reweighted least-squares is not too hard to implement yourself. If you are not looking for the optimum, a simple least-square could do.

Answer 3

Why not compute the mean value of the consecutive differences in the array and use it as a progression value? The mean will naturally be a real value, however you could always round it or ceil it. This gives you 2 progression values. You could try both and use the one with less distance. This way the algorithm might run in $O(N)$ time. Correct me if I misunderstood.

• aaaaajack: It's not optimal. Consider 1,2,3,4,5,11ドル$. So your greedy solution gives 1,3,5,7,9,11ドル$ (error 10ドル$) while there's obviously a error 5ドル$ solution 1,2,3,4,5,6ドル$.
• Tolga Birdal: Then use the median value for slight robustness instead of the mean?
• D.W.: Do you have a proof that using a median will always ensure that your algorithm outputs the optimal (i.e., correct) answer? Have you tried testing it on many examples to see if it seems to work correctly on everything you've tested? If not, you're just guessing, and given that the mean doesn't work, it wouldn't be terribly surprising if the median didn't work either.
• Tolga Birdal: Nope. For the moment I neither have the proof, nor tested on various sequences.