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?


2 Answers 2


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


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.

  • $\begingroup$ perhaps the second sentence should read "If the matrix $U$ has $k$ columns, then the rank of $UU^T$ is (at most) $k$"? $\endgroup$
    – GoHokies
    Sep 25, 2016 at 20:15
  • $\begingroup$ @GoHokies true. $\endgroup$ Sep 25, 2016 at 20:38

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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