Low-Rank Incremental Methods for Computing Dominant Singular Subspaces

C.G. Baker, K.A. Gallivan, P. Van Dooren

Computing the singular values and vectors of a matrix is a crucial kernel in numerous scientic and industrial applications. As such, numerous methods have been proposed to handle this problem in a computationally efficient way. This paper considers a family of methods for incrementally computing the dominant SVD of a large matrix A. Specically, we describe a unification of a number of previously independent methods for approximating the dominant SVD via a single pass through A. We tie the behavior of these metho ds to that of a class of optimization-based iterative eigensolvers on transpose(A) * A. An iterative procedure is proposed which allows the computation of an accurate dominant SVD via multiple passes through A. We present an analysis of the convergence of this iteration and provide empirical demonstration of the proposed method on both synthetic and benchmark data.

Keywords: singular value decomposition, incremental SVD, iterative methods, pass-efficient linear algebra, convergence analysis