0
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Andrew D. King
    Commented Jan 6, 2012 at 0:03
  • $\begingroup$ 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". $\endgroup$
    – Oren
    Commented Jan 6, 2012 at 0:34
  • $\begingroup$ So in other words, the line for $y$ is "glued to" the window, and you move the window along the $x$-axis? $\endgroup$
    – Andrew D. King
    Commented Jan 6, 2012 at 0:56

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think it's a '$(ax + b)$' in the last sum in the first line. $\endgroup$
    – Oren
    Commented Jan 6, 2012 at 1:11
  • $\begingroup$ Yup, cut & paste error. $\endgroup$
    – Jeff Burdges
    Commented Jan 6, 2012 at 1:38
0
$\begingroup$

solved: https://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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .