Fast low-rank modifications of the thin singular value decomposition |
| |
Authors: | Matthew Brand |
| |
Institution: | MERL, 201 Broadway, Cambridge, MA 02139, USA |
| |
Abstract: | 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 × q matrix can be computed in O(pqr) time for . |
| |
Keywords: | 49M27 15A18 15A23 65F20 |
本文献已被 ScienceDirect 等数据库收录! |
|