Large Low-rank Matrices
Sujay Sanghavi, University of Texas at Austin
The modeling of data by low-rank matrices is a fundamental operation in many large-scale problems where inferences / extrapolations have to be made from limited data; examples include collaborative filtering, clustering, localization, manifold learning etc. In several of these applications, the rank of the matrix of interest is often much smaller than the size of the problem; this leads to settings where, for example, both the input data (e.g. sparse network graphs, user ratings of items etc.), and the final desired output (e.g. a clustering, or top items) may fit into main memory, but the matrix representation itself does not.
In this talk we present recent results on provably optimal low-rank modeling, for a variety of problems, via the use of a highly non-convex (but otherwise lightweight and parallelizable) method: alternating minimization.
(Joint work w/ Prateek Jain and Praneeth Netrapalli, some of which is to appear at STOC 2013)