Low-Rank Incremental Methods for Computing Dominant Singular Subspaces

Computing the singular values and vectors of a matrix is a crucial kernel in numerous scientific 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. Specifically, we describe a unification of a number of previously independent methods for approximating the dominant SVD after a single pass through A. We connect the behavior of these methods to that of a class of optimization-based iterative eigensolvers on ATA. An iterative procedure is proposed which allows the computation of an accurate dominant SVD using 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