Tight Sampling Bounds for Eigenvalue Approximation

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 fracpoly(log n)ε3. We improve their analysis by showing that it suffices to sample a principal submatrix of dimension tildeO(frac1ε2) (with no dependence on n). This matches known lower bounds and therefore resolves the sample complexity of this problem up to logfrac1ε factors. Using similar techniques, we give a tight tildeO(frac1ε2) bound for obtaining an additive ε|A|F approximation to the spectrum of A via squared row-norm sampling, improving on the previous best tildeO(frac1ε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(frac1ε) columns of A suffices to produce a unit vector u with uT A u ≥ λ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.