Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview

Yuejie Chi, Yue M. Lu, Yuxin Chen

Research output: Contribution to journalArticlepeer-review

228 Scopus citations


Substantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. While conventional wisdom often takes a dim view of nonconvex optimization algorithms due to their susceptibility to spurious local minima, simple iterative methods such as gradient descent have been remarkably successful in practice. The theoretical footings, however, had been largely lacking until recently. In this tutorial-style overview, we highlight the important role of statistical models in enabling efficient nonconvex optimization with performance guarantees. We review two contrasting approaches: (1) two-stage algorithms, which consist of a tailored initialization step followed by successive refinement; and (2) global landscape analysis and initialization-free algorithms. Several canonical matrix factorization problems are discussed, including but not limited to matrix sensing, phase retrieval, matrix completion, blind deconvolution, and robust principal component analysis. Special care is taken to illustrate the key technical insights underlying their analyses. This article serves as a testament that the integrated consideration of optimization and statistics leads to fruitful research findings.

Original languageEnglish (US)
Article number8811622
Pages (from-to)5239-5269
Number of pages31
JournalIEEE Transactions on Signal Processing
Issue number20
StatePublished - Oct 15 2019

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Electrical and Electronic Engineering


  • First-order methods
  • landscape analysis
  • matrix factorization
  • nonconvex optimization
  • statistics


Dive into the research topics of 'Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview'. Together they form a unique fingerprint.

Cite this