(09/26/18) New paper: Nonconvex optimization meets low-rank matrix factorization

September 26, 2018
Substantial progress has been made recently on developing provably accurate and efficient algorithms for low-rank matrix factorization via nonconvex optimization. In our recent paper, we (Yuejie Chi, Yuxin Chen, and I) present a technical overview to 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, robust principal component analysis, phase synchronization, and joint alignment. The article serves as a testament that the integrated thinking of optimization and statistics leads to fruitful research findings.