# Complexity of iterative least squares regression

Given a set of points $P = \{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n) \}$ one can use least squares method to fit a polynomial to $P$. In particular I am interested in linear and quadratic regression.

I am not familiar with the literature, but it seems a fit to $P$ can be computed in $O(n)$ time,
(the degree of the polynomial is considered a constant).

Is there any algorithms for updating these polynomials as one point is added to or removed from P without recomputing the whole polynomial?

Edit: I found this implementation: http://algs4.cs.princeton.edu/14analysis/LinearRegression.java.html Which easily can be modified to dynamically update a linear regression in constant time.

I still wonder how to do quadratic regression but I will try to mimic the technique I found for linear regression.

## Linear regression

Yes. For linear regression, you can do both updates in $O(1)$ time.

Recall that for ordinary least squares estimation, we estimate the parameter vector $\hat\beta$ using the equation

$$\hat{\beta} = (X^T X)^{-1} X^T y.$$

Here $X$ is a $n \times 2$ matrix and $y$ is a $n$-vector. Adding a point amounts to adding a row to $X$ and $y$; deleting a point corresponds to deleting a row.

So, here is the technique. When you do the initial estimate, remember the value of $X^T X$ (which is a $2 \times 2$ matrix) and of $X^T y$ (which is a $2$-vector). This only requires $O(1)$ storage.

Now let's say you add a point. This involves adding a row to $X,y$, to obtain new values, call them $X',y'$. We now need to compute $(X'^T X')^{-1} X'^T y'$. Fortunately, this can computed efficiently. It is easy to compute $X'^T X'$ in $O(1)$ time, given the value of $X^T X$ and the row that was added to $X$. It is also easy to compute $X'^T y'$ in $O(1)$, given the value of $X^T y$ and the row that was added to $X,y$. Once you know the values of $X'^T X'$ and $X'^T y'$, you can simply multiply them (takes $O(1)$ time) and update the stored values.

A similar procedure can be used to remove a point, if you've stored all of the points and all of $X,y$.

The same techniques work for quadratic regression. Now instead of a $n\times 2$ matrix, we have a $n \times 3$ matrix. Basically, instead of the simple linear model $y \sim \beta_1 x + \beta_2$, we obtain the model $y \sim \beta_1 x^2 + \beta_2 x + \beta_3$, which has three parameters instead of two. Everything else transfers over, and all updates can be done in $O(1)$ time.