Nonconvex Low Rank Matrix Factorization via Inexact First Order Oracle
Nonconvex Low Rank Matrix Factorization via Inexact First Order Oracle
复制标题
通过不精确一阶预言机进行非凸低秩矩阵分解
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Han Liu
中科院分区：
文献类型：
--
作者：
T. Zhao;Zhaoran Wang;Han Liu
利用非凸优化方法研究了低阶矩阵分解问题。与凸松弛方法相比，非凸优化方法在大规模低阶矩阵估计中表现出了更好的经验性能。然而，对其理论保障的理解是有限的。为了弥补这一差距，我们利用了不精确一阶预言的概念，这一概念自然出现在低阶矩阵分解问题中，如矩阵感知和完成。特别是，我们的分析表明，一类广泛的非凸优化算法，包括交替极小化方法和梯度型方法，可以看作是利用不精确的一阶预言来求解两个凸优化算法序列。因此，我们可以证明这些算法在适当的条件下几何地收敛到全局最优值，并恢复真正的低秩阵。数值结果支持了我们的理论。
We study the low rank matrix factorization problem via nonconvex optimization. Compared with the convex relaxation approach, nonconvex optimization exhibits superior empirical performance for large scale low rank matrix estimation. However, the understanding of its theoretical guarantees is limited. To bridge this gap, we exploit the notion of inexact first order oracle, which naturally appears in low rank matrix factorization problems such as matrix sensing and completion. Particularly, our analysis shows that a broad class of nonconvex optimization algorithms, including alternating minimization and gradient-type methods, can be treated as solving two sequences of convex optimization algorithms using inexact first order oracle. Thus we can show that these algorithms converge geometrically to the global optima and recover the true low rank matrices under suitable conditions. Numerical results are provided to support our theory.