Matrix inversion using woodbury indentity inverse

110 Views Asked by At

Consider closed-form solution of linear regression $$ \hat{\beta}=\left(\lambda I+X^TX\right)^{-1}X^Ty $$ where $X \in \mathbb{R}^{n \times d}, y \in \mathbb{R}^{n}$

Say we have extra data points $(X_{n+1}, y_{n+1})$. We can define \begin{gather*} X' = (\frac{X}{x_n+1}) \in \mathbb{R^{(n+1)\times d}} \\ y' = (\frac{t}{y_n+1}) \in \mathbb{R^{(n+1)}} \end{gather*} and compute $$\hat{\beta'}=\left(\lambda I+X'^TX'\right)^{-1}X'^Ty'$$

Let \begin{gather*} V_{n} = X^{T}X+\lambda I \\ V_{n+1} = X'^{T}X'+\lambda I \end{gather*} How to derive $V_{n+1}^{-1}$ as a function of $V_{n}^{-1}$ using Woodbury matrix identity?

1

There are 1 best solutions below

2
On

$X^TX=\sum_{i=1}^n x_i^Tx_i$, where each $x_i$ is row $i$ within $X$ (with $x_i$ a row vector, $x_i^T$ a column vector). Therefore, $X'^TX'=X^TX+x_{n+1}^Tx_{n+1}$. That identifies $x_{n+1}^Tx_{n+1}$ as the rank-one update for the Woodbury formula, or more simply, the Sherman-Morrison formula.