3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\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 '16 at 20:15
  • $\begingroup$ @GoHokies true. $\endgroup$ – Brian Borchers Sep 25 '16 at 20:38
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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