Testing Positive Semidefiniteness and Eigenvalue Approximation
summary
Presents concrete testers and tight bounds: for Schatten-1 norm, adaptive matrix‑vector Krylov methods use a polynomial filtering trick to get 1/epsilon^{1/3} queries (general p gives epsilon^{-p/(2p+1)}), and matching lower bounds show optimality. For bilinear sketches a GAG^T sketch with k = Theta(1/epsilon^2) rows gives nonadaptive PSD testing and an eigenvalue estimator; adaptivity can reduce bilinear queries to 1/epsilon via a stochastic gradient‑style iteration. Spectrum recovery needs Gaussian sketches and a subtract trace/k I correction to be optimal.
AI-written summary · about
chapters (9)
- 0:00Problem definition
- 3:03Matrix-vector query testers
- 7:34Krylov subspace iteration
- 12:31Eigenvalue deflation strategy
- 17:38Generalizing to p-norms
- 20:15Bilinear sketch analysis
- 22:57Trace-based testing
- 27:58Adaptive gradient methods
- 30:26Spectrum estimation
related talks
48mTesting Positive Semidefiniteness and Eigenvalue Approximation
29mRecent Advances in Positive Semidefinite Matrix Approximation
01h 04mSketching and Randomized Linear Algebra
32mRandomized Numerical Linear Algebra: Overview
35mConvergence Theory for Iterative Eigensolvers
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
31mSimple and Deterministic Matrix Sketches
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods