Low-rank updates in BFGS

Question

I have read this and other threads on this site on BFGS, but I still don't have a clear understanding of what it's meant by low-rank updates.

For example, I read the following in this book:

The approach adopted by quasi-Newton methods (of which the BFGS algorithm is the most prominent) is to approximate the inverse of the Hessian $H$, with a matrix $M_t$ that is iteratively refined by low rank updates to become a better approximation of $H^{−1}$.

What's exactly low-rank update? How is it different from, say, a high-rank update?

Answer 1

A low rank update to an $n$ by $n$ matrix $A$ is an update of the form

$A=A+UU^{T}$

where $U$ is matrix with $n$ rows but very few columns (typically just one or two.) If the matrix $UU^{T}$ has $k$ columns, then its rank is at most $k$, so this is a low-rank update to the $A$ matrix.

Low rank updates are important in computational linear algebra and optimization because you can update the LU or Cholesky factorizaton of a matrix after a low-rank update without having to factor the updated matrix from scratch.

Answer 2

To add on Brian's answer. The idea behind the low rank update is to find what an approximation that is "good enough", thus saving on computation resources. The BFGS method approximates the hessian with low rank updates by enforcing properties of the real hessian (e.g symmetry, etc.). You can also have a full update every certain number of iterations and a low rank update for the remaining iterations.