Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition

Abstract

Since being analyzed by Rokhlin, Szlam, and Tygert and popularized by Halko, Martinsson, and Tropp, randomized Simultaneous Power Iteration has become the method of choice for approximate singular value decomposition. It is more accurate than simpler sketching algorithms, yet still converges quickly for any matrix, independently of singular value gaps. After $\tilde{O}(1/\epsilon )$ iterations, it gives a low-rank approximation within $(1+\epsilon )$ of optimal for spectral norm error. We give the first provable runtime improvement on Simultaneous Iteration: a simple randomized block Krylov method, closely related to the classic Block Lanczos algorithm, gives the same guarantees in just $\tilde{O}(1/\sqrt{\epsilon })$ iterations and performs substantially better experimentally. Despite their long history, our analysis is the first of a Krylov subspace method that does not depend on singular value gaps, which are unreliable in practice. Furthermore, while it is a simple accuracy benchmark, even $(1+\epsilon )$ error for spectral norm low-rank approximation does not imply that an algorithm returns high quality principal components, a major issue for data applications. We address this problem for the first time by showing that both Block Krylov Iteration and a minor modification of Simultaneous Iteration give nearly optimal PCA for any matrix. This result further justifies their strength over non-iterative sketching methods. Finally, we give insight beyond the worst case, justifying why both algorithms can run much faster in practice than predicted. We clarify how simple techniques can take advantage of common matrix properties to significantly improve runtime.

Neural Information Processing Systems 2015

References in corpus (1)

• An implementation of a randomized algorithm for principal component analysis

Cited by in corpus (29)

• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• FREDE: Anytime Graph Embeddings
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning
• A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
• Accelerated Stochastic Power Iteration
• Streaming Batch Eigenupdates for Hardware Neuromorphic Networks
• Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition
• Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls
• Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation
• Enhanced parallelization of the incremental 4D-Var data assimilation algorithm using the Randomized Incremental Optimal Technique (RIOT)
• First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate
• Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis
• How to reduce dimension with PCA and random projections?
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
• Convergence of Stochastic Gradient Descent for PCA
• Fast Low-Rank Matrix Estimation without the Condition Number
• Fast Multilevel Algorithms for Compressive Principle Component Pursuit
• Faster Principal Component Regression and Stable Matrix Chebyshev Approximation
• Range-Net: A High Precision Streaming SVD for Big Data Applications
• Approximating matrix eigenvalues by subspace iteration with repeated random sparsification
• Solving Ridge Regression using Sketched Preconditioned SVRG
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
• Superlinear Convergence of Randomized Block Lanczos Algorithm
• Robust Estimation for Random Graphs
• Sparse sketches with small inversion bias
• Efficient Frequent Directions Algorithm for Sparse Matrices
• Subspace Approximation for Approximate Nearest Neighbor Search in NLP
• A Short Proof for Gap Independence of Simultaneous Iteration
• Gen-Oja: A Two-time-scale approach for Streaming CCA