Testing Positive Semidefiniteness and Eigenvalue Approximation

on YouTube ↗48m

" summary

Provides optimal, concrete algorithms: for L1 testing the procedure uses Krylov/Chebyshev ideas to get O(eps^{-1/3}) matrix‑vector products (and a matching lower bound), removing top eigenvalues first to shrink the required shift. Nonadaptive bilinear sketches use a G A G^T sketch with Gaussian G (rows ~1/eps^2) to test PSD or estimate the spectrum up to additive eps ||A||_F; adaptivity cuts bilinear VMV cost to O(eps^{-1}) (p=1) or O(eps^{-2}) (p=2) via a stochastic‑gradient style estimator.

AI-written summary · about

" chapters (5)

1. 0:00Intro
2. 6:57Matrix-Vector Queries
3. 25:12Bilinear Sketches
4. 36:02Leveraging Adaptivity
5. 41:29Spectrum Estimation

" related talks

• 35mTesting Positive Semidefiniteness and Eigenvalue ApproximationDavid P. Woodruff · Sketching and Algorithm Design 2023
• 29mRecent Advances in Positive Semidefinite Matrix ApproximationCameron Musco · Randomized Numerical Linear Algebra and Applications 2018
• 35mConvergence Theory for Iterative EigensolversMark Embree · Randomized Numerical Linear Algebra and Applications 2018
• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 31mSimple and Deterministic Matrix SketchesEdo Liberty · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 03mSampling for Linear Algebra, Statistics, and Optimization IMichael Mahoney · Foundations of Data Science Boot Camp 2018
• 01h 04mSketching and Randomized Linear AlgebraDavid P. Woodruff · Sublinear Algorithms Boot Camp 2024
• 01h 03mSketching as a Tool for Numerical Linear AlgebraDavid P. Woodruff · Fast Algorithms via Spectral Methods 2014