Gradient Descent Meets Shift and Invert Preconditioning for Eigenvector Computation
Shift and invert preconditioning, as a classic acceleration technique for the leading eigenvector computation, has received much attention again recently, owing to fast least squares solvers for efficiently approximating matrix inversions in power iterations. In this work, we adopt an inexact Riemannian gradient descent perspective to investigate this technique on the effect of the step size scheme. The shift and inverted power method is included as a special case with adaptive step sizes. Particularly, two other step size settings, i.e. constant step sizes and Barzilai Borwein (BB) step sizes, are examined theoretically and/or empirically. We present a novel convergence analysis for the constant step size setting that achieves a rate at \tilde{O}\sqrt{\frac{\lambda_{1}\lambda_{1} \lambda_{p+1} where \lambda_{i} represents the $i$ th largest eigenvalue of the given real symmetric matrix and $p$ is the multiplicity of \lambda_{1} Our experimental studies show that the proposed algorithm can be significantly faster than the shift and inverted power method in practice.
NeurIPS