# Recursive (online) regularised least squares algorithm

Can anyone point me in the direction of an online (recursive) algorithm for Tikhonov Regularisation (regularised least squares)?

In an offline setting, I would calculate $\hat\beta=(X^TX+λI)^{−1}X^TY$ using my original data set where $λ$ is found using n-fold cross validation. A new $y$ value can be predicted for a given $x$ using $y=x^T\hat\beta$.

In an online setting I continually draw new data points. How can I update $\hat\beta$ when I draw new additional data samples without doing a full recalculation on the whole data set (original + new)?

$\hat\beta_n=(XX^T+λI)^{−1} \sum\limits_{i=0}^{n-1} x_iy_i$

Let $M_n^{-1} = (XX^T+λI)^{−1}$, then

$\hat\beta_{n+1}=M_{n+1}^{−1} (\sum\limits_{i=0}^{n-1} x_iy_i + x_ny_n)$ , and

$M_{n+1} - M_n = x_nx_n^T$, we can get

$\hat\beta_{n+1}=\hat\beta_{n}+M_{n+1}^{−1} x_n(y_n - x_n^T\hat\beta_{n})$

According to Woodbury formula, we have

$M_{n+1}^{-1} = M_{n}^{-1} - \frac{M_{n}^{-1}x_nx_n^TM_{n}^{-1}}{(1+x_n^TM_n^{-1}x_n)}$

As a result,

$\hat\beta_{n+1}=\hat\beta_{n}+\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n} x_n(y_n - x_n^T\hat\beta_{n})$

Polyak averaging indicates you can use $\eta_n = n^{-\alpha}$
to approximate $\frac{M_{n}^{−1}}{1 + x_n^TM_n^{-1}x_n}$ with $\alpha$ ranges from $0.5$ to $1$. You may try in your case to select the best $\alpha$ for your recursion.

I think it also works if you apply a batch gradient algorithm:

$\hat\beta_{n+1}=\hat\beta_{n}+\frac{\eta_n}{n} \sum\limits_{i=0}^{n-1}x_i(y_i - x_i^T\hat\beta_{n})$