6 ms·
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.
- Pierdimi 4mo ago[dead]
- rzzzwilson 4mo agoInteresting. A "zero code" implementation?
- Pierdimi 4mo agoYes. 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.
- Pierdimi 4mo ago[dead]
- Pierdimi 4mo agoThe 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".
- Pierdimi 4mo ago[dead]
- rzzzwilson 4mo agoMy comment was about the lack of any sort of link showing what you claim.
- Pierdimi 4mo agoA 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 https://doi.org/10.5281/zenodo.20574595).