Efficient coordinate-wise leading eigenvector computation
This work addresses computational efficiency in eigenvector computation, which is incremental but offers specific improvements for certain spectral conditions.
The paper tackles the problem of efficiently computing the leading eigenvector by developing coordinate-wise methods that use only vector-vector products per step, achieving global convergence with runtime guarantees at least as good as Lanczos's method and better for slowly decaying spectra.
We develop and analyze efficient "coordinate-wise" methods for finding the leading eigenvector, where each step involves only a vector-vector product. We establish global convergence with overall runtime guarantees that are at least as good as Lanczos's method and dominate it for slowly decaying spectrum. Our methods are based on combining a shift-and-invert approach with coordinate-wise algorithms for linear regression.