TR2006-059

Fast Low-Rank Modifications of the Thin Singular Value Decomposition


    •  Brand, M., "Fast Low-Rank Modifications of the Thin Singular Value Decomposition", Linear Algebra and Its Applications, Vol. 415, No. 1, pp. 20-30, May 2006.
      BibTeX Download PDF
      • @article{Brand2006may,
      • author = {Brand, M.},
      • title = {Fast Low-Rank Modifications of the Thin Singular Value Decomposition},
      • journal = {Linear Algebra and Its Applications},
      • year = 2006,
      • volume = 415,
      • number = 1,
      • pages = {20--30},
      • month = may,
      • url = {http://www.merl.com/publications/TR2006-059}
      • }
  • MERL Contact:
  • Research Area:

    Algorithms


TR Image
Run-time of sequential SVD updating (solid line) versus batch Lanczos (dashed line), as a function of the number of singular vector/value triplets computed from a random matrix.

This paper develops an identity for additive modivations of a singular value decomposition (SVD) to reflect updates, downdates, shifts, and edits of the data matrix. This sets the stage for fast and ememory-efficient sequential algorithms for tracking singular values and subspaces. In conjunction with a fast solution for the pseudo-inverse of a submatrix of an orthogonal matrix, we develop a scheme for computing a thin SVD of streaming data in a single pass with linear time complexity: A rank-r think SVD of a p x q matrix can be computed in O(pqr) time for r less-than-or-equal sqroot(min(p,q)).