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 poly(log n) ǫ 3

. We improve their analysis by showing that it suffices to sample a principal submatrix of dimension Õ( 1ǫ 2 ) (with no dependence on n). This matches known lower bounds and therefore resolves the sample complexity of this problem up to log 1 ǫ factors. Using similar techniques, we give a tight Õ( 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 Õ( 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( 1 ǫ ) columns of A suffices to produce a unit vector u with u T Au ≥ λ 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.