Testing Positive Semidefiniteness and Eigenvalue Approximation - Optimal Algorithms and Novel Approaches

Explore optimal algorithms for testing positive semidefiniteness and eigenvalue approximation in this insightful talk by David P. Woodruff, PhD. Discover a novel random walk algorithm using a single vector-matrix-vector product per iteration, offering significant improvements over classical methods. Learn about obtaining additive error estimates for all eigenvalues using an optimal-sized sketch, and how to recover accurate estimates despite the eigenvalues of the sketch not being direct approximations. Dive into cutting-edge advancements in matrix analysis and algorithm optimization, based on collaborative works with Deanna Needell and William Swartworth. Gain valuable insights into matrix-vector queries, bilinear sketches, leveraging adaptivity, and spectrum estimation, making this talk ideal for enthusiasts of machine learning, data science, and artificial intelligence.

- Intro
- Matrix-Vector Queries
- Bilinear Sketches
- Leveraging Adaptivity
- Spectrum Estimation