Complexity of iterative least squares regression

Question

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.

Answer 1

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$.

Quadratic regression

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.

Gradient descent

Finally, one last method. Some variations on linear regression work by using gradient descent (or some other iterative mathematical optimization algorithm) to find the best model that maximizes some objective function (likelihood, or loss, or whatever).

Heuristically, if you update the set of points, you can often update the existing model much more efficiently than computing a new one from scratch. In particular, you simply use grade descent with the new objective function -- but you use the old model as the starting point / initial point for the gradient descent. Gradient descent is usually much faster when the starting point is close to the final optimum value, and when you make a small change (like adding or removing one point) we can expect this to be the case.

I don't think there are any complexity-theoretic guarantees with this approach, so it's entirely heuristic -- but it might work in practice if you are using gradient descent based methods for estimation instead of ordinary least squares.