Reproduce “Faster Eigenvector Computation via Shift-and-Invert Preconditioning” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Dan Garber, Elad Hazan, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, Aaron Sidford

The authors present a PCA method that shifts the eigenproblem and uses stochastic variance-reduced linear-system solvers to compute leading eigenvectors. The shift makes the leading eigenvalue at least 100 times the second, but transfers difficulty to solving linear systems. Their offline bound separates data-reading cost from spectral structure but retains inverse-square eigengap dependence; the online sample guarantee assumes a good initial vector.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.