7
$\begingroup$

Today my studies led me to read about the matrix inversion lemma, which Wikipedia introduces as follows:

In mathematics (specifically linear algebra), the Woodbury matrix identity, named after Max A. Woodbury[1][2] says that the inverse of a rank-k correction of some matrix can be computed by doing a rank-k correction to the inverse of the original matrix.

After some searching I couldn't find any explanation of the terminology rank-$k$ correction, but I did find a Wikipedia article about the BFGS algorithm that uses the same term:

Instead, the Hessian matrix is approximated using rank-one updates specified by gradient evaluations... the approximate Hessian at stage $k$ is updated by the addition of two matrices $$B_{k+1} = B_k + U_k + V_k$$ Both $U_k$ and $V_k$ are symmetric rank-one matrices... [and together] construct a rank-two update matrix...

As far as I can tell from these sources, a rank-$k$ correction of matrix $A$ consists of the addition of a matrix $B$ of rank $k$ to $A$.

However, it is unclear to me what exactly the reason is for describing matrix addition in this way. Can someone help me understand the implications and applications of this terminology at a basic level, as well as its importance to optimization problems?

$\endgroup$
4
$\begingroup$

Rank updates to a matrix are often performed when new data is acquired and needs to be incorporated into a given model.

For example, in the case of regression, in order to compute the coefficient estimates, $\beta$, of linear model, the Normal equations say that we can compute them as $\hat{\beta} = (X^{T}X)^{g}X^{T}y$. If we assume that $X \in R^{n \times p}$ has full column-rank, then $(X^{T}X)^{g} = (X^{T}X)^{-1}$. Now let's say we observe some new samples $x_{n+1},x_{n+2},x_{n+3}... \in R^{p}$, we can define $X^{*} = \begin{bmatrix} X \\ x_{n+1} \\ x_{n+2} \\ ... \end{bmatrix}$. Rather than explicitly computing $(X^{*T}X^{*})^{-1}$, which might be costly if $p$ is large, we can make use of the matrix inversion lemma to simply update $(X^{T}X)^{-1}$ (which we already have stored somewhere from fitting our original model) with our new samples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.