Abstract
Randomized Numerical Linear Algebra (RNLA) has traditionally utilized sketching to reduce problem dimensionality. However, applying "sketch-and-precondition" techniques to low-rank matrix approximation has remained challenging. This paper introduces Error-Powered Sketched Inverse Iteration (EPSI), a framework that leverages sketching to construct a preconditioner for iterative solvers. EPSI ensures the true eigenvector is a fixed point and achieves a convergence rate that scales linearly with the sketch size, offering a robust and efficient alternative to standard subspace iteration and Rayleigh Quotient Iteration.
Introduction
In the field of Randomized Numerical Linear Algebra (RNLA), two primary philosophies dominate: Sketch-and-Solve and Sketch-and-Precondition. Sketch-and-solve methods reduce a massive matrix to a smaller "sketch" to solve the problem quickly, but they often hit an accuracy ceiling unless expensive refinement steps are taken. Conversely, sketch-and-precondition methods use the sketch to build a preconditioner that accelerates an iterative solver on the original high-dimensional problem.
While sketch-and-precondition has been highly successful for linear systems like least squares, its application to low-rank matrix approximation (finding eigenvectors and singular values) has been an open challenge. Standard refinement techniques for these problems do not typically see their convergence speed scale linearly with the sketch size. This work bridges that gap, creating an algorithm where a better sketch directly translates to faster, more accurate convergence without sacrificing the original problem's precision.
Methods: Error-Powered Sketched Inverse Iteration (EPSI)
The core innovation of EPSI is the reinterpretation of classic inverse power iteration through the lens of Newton’s method for nonlinear programming. By treating the search for an eigenvector as minimizing a Lagrange form, the authors use a sketched approximation of the matrix ($\hat{A}$) to approximate the Hessian, deriving a Newton-like update.
Key Methodological Components
- Error-Powered Iteration: Unlike standard methods, EPSI applies the sketched inverse to the sketching error $(\hat{A} - A)u_k$ rather than the estimated eigenvector itself. This ensures that the true eigenvector remains a fixed point of the iteration, meaning the quality of the randomized embedding affects the speed of convergence (as a preconditioner) rather than the final accuracy.
- Lazy-EPSI: For computing top-$k$ singular vectors, a "Lazy" variant is introduced. It utilizes a novel orthogonalization step that allows the convergence of the $i$-th vector to depend on the gap to the $(k+1)$-th eigenvalue, preventing intermediate spectral gaps from slowing down the process.
- Computational Efficiency: The method employs the Randomized Nyström Approximation to build the preconditioner and leverages the Woodbury matrix identity to perform matrix inversions in $O(nl^2)$ time, where $n$ is the matrix dimension and $l$ is the sketch size.
Results and Key Insights
The authors evaluated EPSI using synthetic dense matrices with controlled spectral decay, low-rank data with white noise, and the real-world 1138-bus sparse matrix dataset.
Key Findings
- Theoretical Performance: The authors prove that EPSI achieves linear-quadratic convergence. Numerical experiments show that EPSI's convergence rate improves at least linearly with the sketch size; doubling the sketch budget roughly doubles the convergence speed.
- Superior Speed and Stability: On the
1138-busdataset, EPSI reached high precision ($10^{-10}$ error) significantly faster than the standard block power method or Davidson’s method. - Robustness: Unlike Rayleigh Quotient Iteration (RQI), which is cubically fast but highly sensitive to initialization, EPSI provides a stable middle ground—faster than standard power methods but far more robust than RQI across independent trials.
Conclusion
EPSI introduces a powerful "sketch-and-precondition" framework for low-rank approximation that maintains fixed-point stability while scaling performance with computational budget. While the current work focuses on symmetric matrices and requires a negative shift for stability, it opens the door for extending these principles to Canonical Component Analysis (CCA), generalized PCA, and streaming data environments.
Summary updated