Abstract
Substantial progress has been made recently on developing provably accurateand efficient algorithms for low-rank matrix factorization via nonconvexoptimization. While conventional wisdom often takes a dim view of nonconvexoptimization algorithms due to their susceptibility to spurious local minima,simple iterative methods such as gradient descent have been remarkablysuccessful in practice. The theoretical footings, however, had been largelylacking until recently. In this tutorial-style overview, we highlight the important role ofstatistical models in enabling efficient nonconvex optimization withperformance guarantees. We review two contrasting approaches: (1) two-stagealgorithms, which consist of a tailored initialization step followed bysuccessive refinement; and (2) global landscape analysis andinitialization-free algorithms. Several canonical matrix factorization problemsare discussed, including but not limited to matrix sensing, phase retrieval,matrix completion, blind deconvolution, robust principal component analysis,phase synchronization, and joint alignment. Special care is taken to illustratethe key technical insights underlying their analyses. This article serves as atestament that the integrated consideration of optimization and statisticsleads to fruitful research findings.