Shift-and-Invert Preconditioning for Faster Leading Eigenvector Computation

Shift-and-Invert Preconditioning for Faster Leading Eigenvector Computation is a matrix-free spectral estimation framework introduced by Garber, Hazan, Jin, Kakade, Musco, Netrapalli, and Sidford (2016) that computes an epsilon-approximate top eigenvector x (x^T Sigma x >= (1 - epsilon) lambda_1(Sigma)) of an explicit matrix Sigma = A^T A (A in R^{n x d}) or a streaming covariance matrix Sigma = E_{a ~ D}[a a^T] by reducing leading eigenvector computation to a logarithmic sequence of inexact linear system solves in the shifted matrix B_lambda = lambda I - Sigma with shift parameter lambda in [(1 + gap / 150) lambda_1, (1 + gap / 100) lambda_1] where gap = (lambda_1 - lambda_2) / lambda_1. Because B_lambda^{-1} shares the top eigenvector v_1 of Sigma while amplifying the relative eigenvalue ratio to lambda_1(B_lambda^{-1}) / lambda_2(B_lambda^{-1}) = (lambda - lambda_2) / (lambda - lambda_1) >= 100 (Section 3.1, Theorem 4), tracking progress via the B-norm tangent potential function G(x) = ||P_{v_1^perp} x||_B / ||P_{v_1} x||_B (Section 3.2, Lemma 3) proves that each shifted-and-inverted power step only requires an inexact linear solver achieving constant relative error in the B norm (Theorem 5, Corollary 6, Theorem 8). Decomposing f(w) = (1/2) w^T B w - b^T w into possibly non-convex row components psi_i(w) = (1/2) w^T ((lambda ||a_i||_2^2 / ||A||_F^2) I - a_i a_i^T) w - (1/n) b^T w with importance sampling probabilities p_i = ||a_i||_2^2 / ||A||_F^2 and applying sum-of-non-convex SVRG (Theorem 9, Lemma 11, Theorem 12) decouples the input sparsity nnz(A) from the spectral gap, achieving offline runtime O~((nnz(A) + d sr(A) / gap^2) log(1/epsilon)) (Theorem 16), accelerated offline runtime O~((nnz(A)^{3/4} (d sr(A))^{1/4} / sqrt(gap)) log(1/epsilon)) (Theorem 17), and minimax-optimal online sample complexity O(v(D) / (gap * epsilon)) (Theorem 25, Theorem 32).