Matrix perturbation with random noise and matrix recovery problems

Computer Science/Discrete Mathematics Seminar II
Topic:Matrix perturbation with random noise and matrix recovery problems
Speaker:Van Vu
Affiliation:Yale University
Date:Tuesday, October 22
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2013/1022-VanVu

Classical matrix perturbation bounds, such as Weyl (for eigenvalues) and David-Kahan (for eigenvectors) have, for a long time, been playing an important role in various areas: numerical analysis, combinatorics, theoretical computer science, statistics, machine learning, etc. In this talk, I am going to discuss a popular setting where the perturbation is random and the original matrix (data) is low rank (or approximately low rank). In this case, we can significantly improve the classical bounds mentioned above. As an application, I will discuss a simple universal approach to several matrix recovery problems, such as the hidden clique problem, the hidden coloring problem, the clustering problem, the Netflix problem, etc. In certain cases, our method leads to results beyond the currently known. Joint work with S. O'rourke (Yale) and K. Wang (IMA)