Tight Sampling Bounds for Eigenvalue Approximation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910685766615040 |
|---|---|
| author | Swartworth, William Woodruff, David P. |
| author_facet | Swartworth, William Woodruff, David P. |
| contents | We consider the problem of estimating the spectrum of a symmetric bounded entry (not necessarily PSD) matrix via entrywise sampling. This problem was introduced by [Bhattacharjee, Dexter, Drineas, Musco, Ray '22], where it was shown that one can obtain an $εn$ additive approximation to all eigenvalues of $A$ by sampling a principal submatrix of dimension $\frac{\text{poly}(\log n)}{ε^3}$. We improve their analysis by showing that it suffices to sample a principal submatrix of dimension $\tilde{O}(\frac{1}{ε^2})$ (with no dependence on $n$). This matches known lower bounds and therefore resolves the sample complexity of this problem up to $\log\frac{1}ε$ factors. Using similar techniques, we give a tight $\tilde{O}(\frac{1}{ε^2})$ bound for obtaining an additive $ε\|A\|_F$ approximation to the spectrum of $A$ via squared row-norm sampling, improving on the previous best $\tilde{O}(\frac{1}{ε^{8}})$ bound. We also address the problem of approximating the top eigenvector for a bounded entry, PSD matrix $A.$ In particular, we show that sampling $O(\frac{1}ε)$ columns of $A$ suffices to produce a unit vector $u$ with $u^T A u \geq λ_1(A) - εn$. This matches what one could achieve via the sampling bound of [Musco, Musco'17] for the special case of approximating the top eigenvector, but does not require adaptivity.
As additional applications, we observe that our sampling results can be used to design a faster eigenvalue estimation sketch for dense matrices resolving a question of [Swartworth, Woodruff'23], and can also be combined with [Musco, Musco'17] to achieve $O(1/ε^3)$ (adaptive) sample complexity for approximating the spectrum of a bounded entry PSD matrix to $εn$ additive error. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_03227 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tight Sampling Bounds for Eigenvalue Approximation Swartworth, William Woodruff, David P. Data Structures and Algorithms We consider the problem of estimating the spectrum of a symmetric bounded entry (not necessarily PSD) matrix via entrywise sampling. This problem was introduced by [Bhattacharjee, Dexter, Drineas, Musco, Ray '22], where it was shown that one can obtain an $εn$ additive approximation to all eigenvalues of $A$ by sampling a principal submatrix of dimension $\frac{\text{poly}(\log n)}{ε^3}$. We improve their analysis by showing that it suffices to sample a principal submatrix of dimension $\tilde{O}(\frac{1}{ε^2})$ (with no dependence on $n$). This matches known lower bounds and therefore resolves the sample complexity of this problem up to $\log\frac{1}ε$ factors. Using similar techniques, we give a tight $\tilde{O}(\frac{1}{ε^2})$ bound for obtaining an additive $ε\|A\|_F$ approximation to the spectrum of $A$ via squared row-norm sampling, improving on the previous best $\tilde{O}(\frac{1}{ε^{8}})$ bound. We also address the problem of approximating the top eigenvector for a bounded entry, PSD matrix $A.$ In particular, we show that sampling $O(\frac{1}ε)$ columns of $A$ suffices to produce a unit vector $u$ with $u^T A u \geq λ_1(A) - εn$. This matches what one could achieve via the sampling bound of [Musco, Musco'17] for the special case of approximating the top eigenvector, but does not require adaptivity. As additional applications, we observe that our sampling results can be used to design a faster eigenvalue estimation sketch for dense matrices resolving a question of [Swartworth, Woodruff'23], and can also be combined with [Musco, Musco'17] to achieve $O(1/ε^3)$ (adaptive) sample complexity for approximating the spectrum of a bounded entry PSD matrix to $εn$ additive error. |
| title | Tight Sampling Bounds for Eigenvalue Approximation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.03227 |