Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Can you use $\Theta(n)$ storage? Why not just make a queue of squares of differences. When you advance the window by 1, simply add the new square difference and subtract the square distance that disappears from the window. This is constant time per step once you spend $O(n)$ time setting up the initial window. Or do you mean that the window is moved to some position arbitrarily far away? –  Andrew D. King Jan 6 '12 at 0:03
    
Yes, you can use O(n) storage. See the remark that I added - when samples leave the window the indexes of the other samples change - i.e. their position in the window moved and they became "older". –  Oren Jan 6 '12 at 0:34
    
So in other words, the line for $y$ is "glued to" the window, and you move the window along the $x$-axis? –  Andrew D. King Jan 6 '12 at 0:56
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
I think it's a '$(ax + b)$' in the last sum in the first line. –  Oren Jan 6 '12 at 1:11
    
Yup, cut & paste error. –  Jeff Burdges Jan 6 '12 at 1:38
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.