Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function - MathOverflow

Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function

2012-01-05T23:53:58Z

Given a line function $y = ax + b$ , it is easy to calculate the sum-of-squares distance between the line and a window of samples $(1, y_1), (2, y_2), ..., (n, y_n)$ (where $y_1$ is the oldest sample and $y_n$ is the newest):

$\sum_{x=1}^{n}(y_x - (ax + b))^2 $

I need a fast algorithm for calculating this value for a rolling window (of length n) - I cannot rescan all the samples in the window every time a new sample arrives.
Obviously, some state should be saved and updated for every new sample that enters the window and every old sample leaves the window.
Notice that when a sample leaves the window, the indecies of the rest of the samples change as well - every $y_x$ becomes $y_{x-1}$ . Therefore when a sample leaves the window, every other sample in the window contribute a different value to the new sum: $(y_x - (a(x-1) + b))^2$ instead of $(y_x - (ax + b))^2$ .
Is there a known algorithm for calculating this? If not, can you think of one? (It is ok to have some mistakes due first-order linear approximations).

Thanks

Answer by Jeff Burdges for Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function

2012-01-06T01:03:00Z

We have $\sum_x (y_x - ax-b)^2 = \sum_x y_x^2 - 2a \sum_x x y_x - 2b \sum_x y_x + \sum_x (ax+b)^2$ so the only term requiring $O(n)$ time per shift is $\sum_x x y_x$ because an easy $O(1)$ time trick handles the other terms involving $y_x$.

In this term, you can decrement $x$ in $O(1)$ time too because $\sum_x (x-1) y_x = \sum_x x y_x - \sum_x y_x$, heck you must store $\sum_x y_x$ anyways. After that, you could simply employ the same obvious $O(1)$ time slide trick you used for $\sum_x y_x^2$ and $\sum_x y_x$.

In fact, you need not do anything too special if terms slide off when $x=0$, i.e. you initially added $k y_x$ and subtracted off one $y_x$ per round.

Answer by Oren for Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function

2012-01-06T01:04:41Z

solved: http://stackoverflow.com/questions/8751509/algorithm-for-calculating-the-sum-of-squares-distance-of-a-rolling-window-from-a

If I will have a more detailed solution (step-by-step algorithm) I'll publish it.