Guaranteed Matrix Completion via Non-Convex Factorization

Ruoyu Sun, Zhi Quan Luo

Research output: Contribution to journalArticlepeer-review

111 Scopus citations

Abstract

Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization, even with huge size, can be solved very efficiently through the standard optimization algorithms in practice. However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of whether these algorithms will generate a good solution. In this paper, we establish a theoretical guarantee for the factorization-based formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of a factorization-based formulation and recover the true low-rank matrix. We study the local geometry of a properly regularized objective and prove that any stationary point in a certain local region is globally optimal. A major difference of this paper from the existing results is that we do not need resampling (i.e., using independent samples at each iteration) in either the algorithm or its analysis.

Original languageEnglish (US)
Article number7536166
Pages (from-to)6535-6579
Number of pages45
JournalIEEE Transactions on Information Theory
Volume62
Issue number11
DOIs
StatePublished - Nov 2016

Bibliographical note

Funding Information:
This work was supported in part by NSF under Grant CCF-1526434, in part by NSFC under Grant 61571384, and in part by a Doctoral Dissertation Fellowship from the Graduate School of the University of Minnesota. This paper was presented in part at the 2015 IEEE FOCS.

Keywords

  • Matrix completion
  • Perturbation analysis
  • SGD
  • alternating minimization
  • matrix factorization
  • nonconvex optimization

Fingerprint Dive into the research topics of 'Guaranteed Matrix Completion via Non-Convex Factorization'. Together they form a unique fingerprint.

Cite this