Seminar, Hosted by Institute for Computational and Experimental Research in Mathematics (ICERM), Brown University
Tight Sampling Bounds for Eigenvalue Approximation
Abstract
David Woodruff develops sampling bounds for estimating the spectrum of symmetric matrices with bounded entries. Principal-submatrix sampling achieves epsilon times n additive error using roughly 1/epsilon² samples, eliminating dependence on n and improving prior epsilon dependence up to logarithmic factors. Squared row-norm sampling gives epsilon times the Frobenius norm accuracy with roughly 1/epsilon² samples, improving a previous 1/epsilon⁸ bound. For bounded-entry positive-semidefinite matrices, O(1/epsilon) sampled columns permit nonadaptive approximation of the leading eigenvector with epsilon times n additive error. Applications include faster dense-matrix spectral sketches and improved sample complexity. Joint work with William Swartworth.
Topics
- symmetric matrices, search World Wide
- bounded entries, search World Wide
- Principal-submatrix sampling, broader topic: sampling
- Squared row-norm sampling, broader topic: sampling
- Frobenius norm, search World Wide
- positive-semidefinite matrices, search World Wide
- leading eigenvector, search World Wide
- spectral sketches, search World Wide
- sample complexity