×

Fast low-rank modifications of the thin singular value decomposition. (English) Zbl 1088.65037

Summary: This paper develops an identity for additive modifications of a singular value decomposition (SVD) to reflect updates, downdates, shifts, and edits of the data matrix. This sets the stage for fast and memory-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\) thin SVD of a \(p\times q\) matrix can be computed in \(O(pqr)\) time for \(r\leq \sqrt{\min(p,q)}\).

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Mirsky, L., Symmetric gauge functions and unitarily invariant norms, Quart. J. Math. Oxford, 11, 50-59 (1960) · Zbl 0105.01101
[2] Golub, Gene; van Loan, Arthur, Matrix Computations (1996), Johns Hopkins U. Press · Zbl 0865.65009
[3] Businger, P., Updating a singular value decomposition, BIT, 10, 376-385 (1970)
[4] Bunch, J. R.; Nielsen, C. P., Updating the singular value decomposition, Numer. Math., 31, 111-129 (1978) · Zbl 0421.65028
[6] Chandrasekaran, S.; Manjunath, B. S.; Wang, Y. F.; Winkeler, J.; Zhang, H., An eigenspace update algorithm for image analysis, Graphical Models Image Process.: GMIP, 59, 5, 321-332 (1997)
[8] Gu, M.; Eisenstat, S., Downdating the singular value decomposition, SIAM J. Matrix Anal. Appl., 16, 793-810 (1995) · Zbl 0828.65039
[10] Zha, H.; Simon, H. D., On updating problems in latent semantic indexing, SIAM J. Sci. Comput., 21, 2, 782-791 (1999) · Zbl 0952.65034
[11] Witter, D. I.; Berry, M. W., Downdating the latent semantic indexing model for conceptual information retrieval, The Computer J., 410, 1998 (1998) · Zbl 0920.68049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.