Low-rank matrix completion using alternating minimization

By Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi. 2012

1,135 citations recorded by the source corpus.

Alternating minimization represents a widely applicable and empirically successful approach for finding low-rank matrices that best fit the given data. For example, for the problem of low-rank matrix completion, this method is believed to be one of the most accurate and efficient, and formed a major component of the winning entry in the Netflix Challenge [17]. In the alternating minimization approach, the low-rank target matrix is written in a bi-linear form, i.e. X = UV†; the algorithm then alternates between finding the best U and the best V. Typically, each alternating step in isolation is convex and tractable. However the overall problem becomes non-convex and is prone to local minima. In fact, there has been almost no theoretical understanding of when this approach yields a good result. In this paper we present one of the first theoretical analyses of the performance of alternating minimization for matrix completion, and the related problem of matrix sensing. For both these problems, celebrated recent results have shown that they become well-posed and tractable once certain (now standard) conditions are imposed on the problem. We show that alternating minimization also succeeds under similar conditions. Moreover, compared to existing results, our paper shows that alternating minimization guarantees faster (in particular, geometric) convergence to the true matrix, while allowing a significantly simpler analysis.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Optimization, Numerical Methods & Scientific Computing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

  1. Martin J. Wainwright
  2. Jason D. Lee
  3. Prateek Jain
  4. Francis R. Bach
  5. Michael I. Jordan
  6. E.J. Candes
  7. Rong Ge
  8. Yuxin Chen

In Computer Vision and Pattern Recognition

  1. Luc Van Gool
  2. Dacheng Tao
  3. Lei Zhang
  4. Ming-Hsuan Yang
  5. Trevor Darrell
  6. Xiaogang Wang
  7. Chunhua Shen
  8. Andrew Zisserman

In Mathematical Optimization

  1. Prateek Jain
  2. Jason D. Lee
  3. Moritz Hardt
  4. Srinadh Bhojanapalli
  5. Rong Ge
  6. Sébastien Bubeck
  7. Yuanzhi Li
  8. Sujay Sanghavi

In Numerical Methods & Scientific Computing

  1. Srinadh Bhojanapalli
  2. Rong Ge
  3. Prateek Jain
  4. Moritz Hardt
  5. Justin P. Haldar
  6. Sébastien Bubeck
  7. Stephen J. Wright
  8. Yuxin Chen

Citations in the corpus