Gradient Descent Meets Shift-and-Invert Preconditioning for Eigenvector Computation
Zhiqiang Xu · Neural Information Processing Systems · 2018
There has been a recent surge of interest in developing theoretically faster algorithms for leading eigenvector computation. The key to achieving faster convergence rates therein is to use the classic shift-and-invert preconditioning technique on top of power methods. The underlying problem then can be reduced to a series of linear system subproblems that can leverage fast approximate least squares solvers. Despite the simplicity of the power iterations as the base method, it may suffer from making limited progress towards solutions. In this work, we consider that the shift-and-invert preconditioning is paired with a new base method, namely gradient descent search. By virtue of the flexibility of setting step-sizes in gradient search processes, we expect the shift-and-inverted gradient descent solver can outperform the shift-and-inverted power methods. In particular, we present a novel convergence analysis for this new pairing that achieves a rate at ˜ O ( √ λ1 λ1−λp+1 ) , where λi represents the i -th largest eigenvalue of the given real symmetric matrix and p is the multiplicity of λ1 . Our experimental studies show that the proposed algorithm can be significantly faster than the shift-and-inverted power method in practice.