Sublinear Time Eigenvector Approximation via Column Sampling
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.00840
curl -X POST /api/v1/records/arxiv/2608.00840/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.00840/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'