Show HN: O(1) Recursive Moving Linear Regression
Constant time recursive filter for moving linear regression. Works for any window size k. Formula in the first comment.
8 comments
A runnable implementation used for the comparative analysis against the Savitzky-Golay filter on a sawtooth signal is provided in Appendix B of the deposited working paper "Recursive Moving Polynomial Regression: A Unified Constant‑Time Approach" (https://doi.org/10.5281/zenodo.20574595).
Interesting. A "zero code" implementation?
Yes. The moving linear regression reduces to a fixed‑cost O(1) recurrence, in a way analogous to a recursive moving average. The internal state requires only the two previous estimates y1_hat(n−1) and y1_hat(n−2), the current sample y(n), the previous sample y(n−1), and a circular buffer of length k+1 to access the samples leaving the window, y(n−k) and y(n−k−1). There is no need to rescan the window, both the computational cost and the additional memory remain constant as k increases.
The statement "There is no need to rescan the window, both the computational cost and the additional memory remain constant as k increases" is inaccurate. The correct statement is: "There is no need to rescan the window; the computational cost remains constant as k increases, while the additional memory requirement grows linearly due to the circular buffer needed to store the windowed samples".
My comment was about the lack of any sort of link showing what you claim.