Sublinear Time Eigenvector Approximation via Column Sampling

DOI10.48550/arXiv.2608.00840MaRDI QIDQ7284568arXivFDO

Authors Cameron Musco, Rajarshi Bhattacharjee, Dominic Rutkowski

Publication date 1 August 2026

Published in arXiv

Tldr We develop sublinear time algorithms for approximating outlying eigenvectors by sampling columns of a symmetric matrix, achieving near optimal sample complexity. Our methods span the output eigenvectors using only a small number of columns and have poly(log n, 1/epsilon) per-entry computation time, enabling applications in quantum-inspired algorithms.

Full work available at URL https://doi.org/10.48550/arXiv.2608.00840

arXiv classification

cs.DSmath.NA

This page was built for publication: Sublinear Time Eigenvector Approximation via Column Sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7284568)