Testing Positive Semidefiniteness and Eigenvalue Approximation with David P. Woodruff, PhD

Join David P. Woodruff, PhD, as he explores the intricacies of testing positive semidefiniteness and eigenvalue approximation. In this talk, Dr. Woodruff presents optimal algorithms for determining if a matrix 𝐴 is positive semidefinite or has a minimum eigenvalue sufficiently negative. He introduces a novel random walk algorithm that uses only a single vector-matrix-vector product per iteration, offering a significant improvement over classical methods.

Dr. Woodruff also dives into how obtaining additive error estimates for all eigenvalues of
𝐴 using an optimal-sized sketch,𝐺𝐴𝐺𝑇, where 𝐺 is a random Gaussian matrix. Despite the eigenvalues of 𝐺𝐴𝐺𝑇 not being direct approximations of those of 𝐴, he demonstrates a method to recover accurate estimates. This talk is based on his collaborative works with Deanna Needell and William Swartworth, showcasing cutting-edge advancements in matrix analysis and algorithm optimization. Ideal for enthusiasts of machine learning, data science, and AI.

#MachineLearning #DeepLearning #DataScience #AI #ArtificialIntelligence #EigenvalueApproximation #MatrixAnalysis #AlgorithmOptimization #PositiveSemidefiniteness #MLAlgorithms #DataEngineering #ODSC

Timecodes:
0:00 - Intro
6:57 - Matrix-Vector Queries
25:12 - Bilinear Sketches
36:02 - Leveraging Adaptivity
41:29 - Spectrum Estimation

You can also follow ODSC on: