Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
复制标题
DOI：
10.1109/tsp.2019.2937282
复制
发表时间：
2019-10-15
影响因子：
5.4
通讯作者：
Chen, Yuxin
中科院分区：
文献类型：
--
作者：
Chi, Yuejie;Lu, Yue M.;Chen, Yuxin
近年来，在通过非凸优化来开发可证明准确和有效的低秩矩阵分解算法方面取得了实质性进展。虽然传统的智慧往往采取了非凸优化算法，由于他们的敏感性虚假的局部最小值，简单的迭代方法，如梯度下降在实践中已经非常成功。然而，直到最近，理论基础在很大程度上仍然缺乏。在这个教程式的概述中，我们强调了统计模型在实现具有性能保证的高效非凸优化方面的重要作用。我们回顾了两种对比的方法：（1）两阶段算法，其中包括一个定制的初始化步骤，随后连续细化;和（2）全球景观分析和初始化免费算法。几个典型的矩阵分解问题进行了讨论，包括但不限于矩阵传感，相位恢复，矩阵完成，盲反卷积，和鲁棒的主成分分析。特别注意说明他们的分析背后的关键技术见解。这篇文章证明了最优化和统计的综合考虑导致了丰硕的研究成果。
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.