Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
For practitioners needing low-rank approximations, this work offers faster algorithms with theoretical guarantees, though it is an incremental improvement over existing randomized linear algebra techniques.
The authors accelerate the power method for low-rank matrix approximation using fast sketching, achieving strong numerical performance on benchmarks. They provide provably efficient methods for SVD, low-rank factorization, and Nyström approximation.
The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, the cost of matrix multiplication associated with this procedure becomes a major bottleneck. We develop an algorithmic and theoretical framework for accelerating the power method using fast sketching, which is a popular paradigm in randomized linear algebra. Our framework leads to simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nyström approximation, which attain strong numerical performance on benchmark problems. The key novelty in our analysis is the use of regularized spectral approximation, a property of fast sketching methods which proves more flexible in generalizing power method guarantees than traditional arguments.