{"id":"arxiv/2608.00840","url":"https://arxiv.org/abs/2608.00840","tags":["cs.DS","math.NA"],"score":0,"title":"Sublinear Time Eigenvector Approximation via Column Sampling","domain":"cs.DS","source":"arxiv","authors":["Rajarshi Bhattacharjee","Cameron Musco","Dominic Rutkowski"],"reviews":0,"subject":"cs.DS","summary":"We study sublinear time sampling methods for approximating the outlying eigenvectors of large matrices. Our main result is an algorithm that uniformly samples just $\\tilde{O}(\\log n/ε^4)$ columns of a symmetric matrix $A \\in \\mathbb{R}^{n \\times n}$ with entries bounded in magnitude by $1$, and, for any eigenvalue $λ$ of $A$ with $|λ| \\ge εn$, outputs an approximate eigenvector $v$ satisfying $\\|Av - λv\\|_2 \\le εn$. For approximating just the eigenvector of the largest magnitude eigenvalue, our algorithm samples only $\\tilde{O}(\\log n/ε^2)$ columns. Given the ability to sample rows and…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-01","reactions":{}}