TY - JOUR
T1 - Nonconvex Optimization Meets Low-Rank Matrix Factorization
T2 - An Overview
AU - Chi, Yuejie
AU - Lu, Yue M.
AU - Chen, Yuxin
N1 - Funding Information:
Manuscript received September 20, 2018; revised June 5, 2019; accepted August 12, 2019. Date of publication August 23, 2019; date of current version September 16, 2019. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Jarvis Haupt. The work of Y. Chi was supported in part by the Office of Naval Research (ONR) under Grants N00014-18-1-2142 and N00014-19-1-2404, in part by the Army Research Office (ARO) under Grant W911NF-18-1-0303, in part by the Air Force Office of Scientific Research (AFOSR) under Grant FA9550-15-1-0205, and in part by the National Science Foundation (NSF) under Grants CCF-1901199, CCF-1806154, and ECCS-1818571. The work of Y. M. Lu was supported in part by the NSF under Grants CCF-1718698 and CCF-1910410 and in part by the Harvard Dean’s Competitive Fund for Promising Research. The work of Y. Chen was supported in part by AFOSR under Grant YIP FA9550-19-1-0030, in part by ARO under Grant W911NF-18-1-0303, in part by ONR under Grant N00014-19-1-2120, and in part by NSF under Grants CCF-1907661 and IIS-1900140. (Corresponding author: Yuxin Chen.) Y. Chi is with the Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213 USA (e-mail: yuejiechi@ cmu.edu).
Publisher Copyright:
© 1991-2012 IEEE.
PY - 2019/10/15
Y1 - 2019/10/15
N2 - 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.
AB - 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.
KW - First-order methods
KW - landscape analysis
KW - matrix factorization
KW - nonconvex optimization
KW - statistics
UR - http://www.scopus.com/inward/record.url?scp=85074892724&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85074892724&partnerID=8YFLogxK
U2 - 10.1109/TSP.2019.2937282
DO - 10.1109/TSP.2019.2937282
M3 - Article
AN - SCOPUS:85074892724
SN - 1053-587X
VL - 67
SP - 5239
EP - 5269
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
IS - 20
M1 - 8811622
ER -