Sublinear Time Eigenvalue Approximation via Random Sampling

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.