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)?
 A: A point that no one has addressed so far is that it generally doesn't make sense to keep the regularization parameter $\lambda$ constant as data points are added.  The reason for this is that $\| X \beta -y \|^{2}$ will typically grow linearly with the number of data points, while the regularization term $\| \lambda\beta \|^{2}$ won't.  
A: Perhaps something like Stochastic gradient descent could work here. Compute $\hat{\beta}$ using your equation above on the initial dataset, that will be your starting estimate. For each new data point you can perform one step of gradient descent to update your parameter estimate.
A: Here is an alternative (and less complex) approach compared to using the Woodbury formula.  Note that $X^TX$ and $X^Ty$ can be written as sums.  Since we are calculating things online and don't want the sum to blow up, we can alternatively use means ($X^TX/n$ and $X^Ty/n$).
If you write $X$ and $y$ as :
$$
X = \begin{pmatrix} x_1^T \\ \vdots \\ x_n^T \end{pmatrix}, \quad
y = \begin{pmatrix} y_1 \\ \vdots \\ y_n \end{pmatrix},
$$
we can write the online updates to $X^TX/n$ and $X^Ty/n$ (calculated up to the $t$-th row) as:
$$
A_t = \left(1 - \frac{1}{t}\right) A_{t-1} + \frac{1}{t}x_t x_t^T,
$$
$$
b_t = \left(1 - \frac{1}{t}\right) b_{t-1} + \frac{1}{t}x_t y_t.
$$
Your online estimate of $\beta$ then becomes 
$$\hat\beta_t = (A_t + \lambda I)^{-1}b_t.$$
Note that this also helps with the interpretation of $\lambda$ remaining constant as you add observations! 
This procedure is how https://github.com/joshday/OnlineStats.jl computes online estimates of linear/ridge regression.
A: $\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})$ 
A: In linear regression, one possibility is updating the QR decomposition of $X$ directly, as explained here. I guess that, unless you want to re-estimate $\lambda$ after each new datapoint has been added, something very similar can be done with ridge regression. 
