Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T14:57:39Z http://mathoverflow.net/feeds/question/85012 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85012/algorithm-for-calculating-the-sum-of-squares-distance-of-a-rolling-window-from-a Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function Oren 2012-01-05T23:53:58Z 2012-01-06T01:11:32Z <p>Given a line function <code>$y = ax + b$</code>, it is easy to calculate the sum-of-squares distance between the line and a window of samples <code>$(1, y_1), (2, y_2), ..., (n, y_n)$</code> (where <code>$y_1$</code> is the oldest sample and <code>$y_n$</code> is the newest):</p> <p><code>$\sum_{x=1}^{n}(y_x - (ax + b))^2$</code></p> <p>I need a fast algorithm for calculating this value for a rolling window (of length <code>n</code>) - I cannot rescan all the samples in the window every time a new sample arrives.<br> Obviously, some state should be saved and updated for every new sample that enters the window and every old sample leaves the window.<br> Notice that when a sample leaves the window, the indecies of the rest of the samples change as well - every <code>$y_x$</code> becomes <code>$y_{x-1}$</code>. Therefore when a sample leaves the window, every other sample in the window contribute a different value to the new sum: <code>$(y_x - (a(x-1) + b))^2$</code> instead of <code>$(y_x - (ax + b))^2$</code>.<br> 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).</p> <p>Thanks</p> http://mathoverflow.net/questions/85012/algorithm-for-calculating-the-sum-of-squares-distance-of-a-rolling-window-from-a/85018#85018 Answer by Jeff Burdges for Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function Jeff Burdges 2012-01-06T01:03:00Z 2012-01-06T01:11:32Z <p>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$.</p> <p>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$.</p> <p>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.</p> http://mathoverflow.net/questions/85012/algorithm-for-calculating-the-sum-of-squares-distance-of-a-rolling-window-from-a/85019#85019 Answer by Oren for Algorithm for calculating the sum-of-squares distance of a rolling window from a given line function Oren 2012-01-06T01:04:41Z 2012-01-06T01:04:41Z <p>solved: <a href="http://stackoverflow.com/questions/8751509/algorithm-for-calculating-the-sum-of-squares-distance-of-a-rolling-window-from-a">http://stackoverflow.com/questions/8751509/algorithm-for-calculating-the-sum-of-squares-distance-of-a-rolling-window-from-a</a></p> <p>If I will have a more detailed solution (step-by-step algorithm) I'll publish it.</p>