Matrix Completion and Matrix Concentration

Dr. Lester Mackey
Postdoc, Stanford University
Given on: April 25, 2013


The goal in matrix completion is to recover a matrix from a small subset of noisy entries. Web-scale instances of this problem include collaborative filtering for recommendation and link prediction in social networks. Many modern matrix completion algorithms provide strong recovery guarantees but scale poorly due to the repeated and costly computation of truncated SVDs. To address this deficiency, in the first part of this talk, I will introduce Divide-Factor-Combine (DFC), a parallel divide-and-conquer framework for boosting the scalability of a matrix completion algorithm while retaining its theoretical guarantees. Our experiments demonstrate the near-linear to super-linear speed-ups attainable with this approach, and our analysis shows that DFC enjoys high-probability recovery guarantees comparable to those of its base algorithm.

Fundamental to our analysis – and to the analyses of many matrix completion procedures – are matrix concentration inequalities that characterize the fluctuations of a random matrix about its mean. In the second part of this talk, I will show how Stein’s method of exchangeable pairs can be used to derive concentration inequalities for matrix-valued random elements. When applied to a sum of independent random matrices, this approach yields matrix generalizations of the classical inequalities due to Hoeffding, Bernstein, Khintchine, and Rosenthal. The same technique delivers bounds for sums of dependent random matrices and more general matrix functionals of dependent random elements.

This is joint work with Ameet Talwalkar, Michael I. Jordan, Richard Y. Chen, Brendan Farrell, and Joel A. Tropp.


Lester Mackey is a Simons Math+X postdoctoral fellow, working with Emmanuel Candes at Stanford University. In the fall of 2013, he will be joining the Stanford Statistics faculty.

He received his Ph.D. in Computer Science (2012) and M.A. in Statistics (2011) from UC Berkeley, and his B.S.E. in Computer Science (2007) from Princeton University. He has won the Eli Jury award at U.C. Berkeley, Best Student Paper award at ICML 2010, the First Prize in the $50K ALS Prediction Prize4Life Challenge to predict the progression of Lou Gehrig's disease and the Second Prize in the $1M Netflix Prize for collaborative filtering.