Sublinear Time Eigenvalue Approximation via Random Sampling
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore a 47-minute lecture on sublinear time eigenvalue approximation through random sampling, presented by Cameron Musco from Microsoft Research New England at the Simons Institute. Delve into sketching algorithms for approximating the full eigenspectrum of symmetric matrices, focusing on a novel sublinear time algorithm that uses randomly sampled principal submatrices. Examine concentration bounds on the complete eigenspectrum of random submatrices, extending beyond known bounds on singular values. Investigate improved error bounds achieved through non-uniform sampling techniques, considering row sparsities and squared ell_2 norms. Analyze the technical aspects, including new eigenvalue concentration and perturbation bounds for matrices with bounded entries, as well as an innovative algorithmic approach involving strategic zeroing of entries in randomly sampled submatrices. Gain insights into the advancements made in approximating singular values and testing for large negative eigenvalues in the context of sketching and algorithm design.
Syllabus
Sublinear Time Eigenvalue Approximation via Random Sampling
Taught by
Simons Institute
Related Courses
Differential Equations Part I Basic TheoryKorea Advanced Institute of Science and Technology via Coursera Matrix Analysis with Applications
Indian Institute of Technology Roorkee via Swayam Essential Mathematics for Machine Learning
Indian Institute of Technology Roorkee via Swayam Advanced Matrix Theory and Linear Algebra for Engineers
NPTEL via YouTube Eigenvalues
YouTube