Computing Singular Vectors with Random Noise

Tuesday, October 15, 2013 - 1:30pm - 2:30pm
Lind 305
Ke Wang (University of Minnesota, Twin Cities)
Computing singular vectors of a large matrix is a basic task in
high dimensional data analysis with many applications in computer science
and statistics. In practice, the data is usually perturbed by noise. The
following question is of importance: How much does the singular vector of
data matrix change under a small perturbation? The classical perturbation
results, i.e. Davis-Kahan theorem and Wedin sin theorem, give tight
estimates for the worst-case scenario. We show that better estimates can be
achieved if the data matrix is low rank and the perturbation is random.
This is joint work with Sean O'Rourke and Van Vu.