Online algorithm to compute rolling standard error for intercept in multiple regression

Question

Suppose I'm fitting a multiple linear model $y = \beta_0 + \beta_1 x_1 + \beta_2 x_2$ + .... My $n$ data vectors are arriving sequentially and I'm trying to get the $t$-statistic for the estimated regression coefficient of the intercept over the most recent $k \ll n$ data points, $\frac{\hat{\beta_i}}{SE_{\hat{\beta_i}}}$ in the most efficient manner.

I found an online algorithm to estimate $\hat{\beta_i}$ over the sliding window of $k$ feature vectors, so this generalizes to the intercept.

What remains is an efficient way to compute only the diagonal element corresponding to the intercept in $\hat{\sigma}^2\left(X^TX\right)^{-1}$. Is it possible to do this online?

This seems nontrivial. Since my regression model and hence in-sample predictions are changing with each data point, I'll need to iterate over all $k$ points to compute the variance of the residuals. But I'm guessing that at least $\left(X^TX\right)^{-1}$ is well-studied so there must be some literature to compute it online over a sliding window.

Answer 1

What you want is the Sherman-Morrison-Woodbury update. I'll walk through the special case you have.

Suppose $A$ is an $m \times m$ invertible matrix, in this case $X^TX$. Although it is (almost always) written as $X^TX$, it can also be computed by using the fact that $X^TX = \sum_{i=1}^n x_ix_i^T$, where $x_i$ is the $i^{\text{th}}$ row of $X$. (This is actually how these computations were performed back in the days when RAM was very limited and an entire $X$ matrix might not be able to be held in memory). Using this, if we want to update $A$ when an additional row of data $x$ is added,

$$A_{updated} = A + xx^T$$

Obviously a similar operation can be performed to update $A$ when we remove a row of data, only subtracting $xx^T$ instead of adding.

In the more general case which S-M-W applies to, we are updating $A$ with the outer product of two vectors $uv^T$, but in this case, $u = v$ (or, in the case of removing a row, $u = -v$). We have the following direct update of the inverse of $A$:

$$(A + uv^T)^{-1} = A^{-1} - {A^{-1}uv^TA^{-1} \over 1+v^TA^{-1}u} $$

which is entirely in terms of $A^{-1}$ (in your case, $(X^TX)^{-1}$) and the row to be added or removed. You would need to perform this operation twice each time the window moves one observation, once for removing the row that is leaving the sliding window and once for adding the row that is entering the sliding window.