The nonconvex geometry of low-rank matrix optimizations with general objective functions
The nonconvex geometry of low-rank matrix optimizations with general objective functions
复制标题
DOI：
10.1093/imaiai/iay003
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Qiuwei Li;Gongguo Tang
中科院分区：
文献类型：
--
作者：
Qiuwei Li;Gongguo Tang
本文研究一类一般凸函数f (X)在最优解X *为低秩的正半定矩阵锥上的最小化问题。标准的一阶凸解需要在每次迭代中执行特征值分解，严重限制了其可扩展性。这个问题的一个自然的非凸的重新表述将变量X因子化为一个列数较少的矩形矩阵与其转置的乘积。对于一类特殊的具有二次目标函数的矩阵感知和补全问题，局部搜索算法应用于分解问题已被证明是更有效的，尽管是非凸的，收敛到全局最优。这项工作的目的是将这条研究线扩展到一般凸目标函数f (X)，并研究由此产生的因子公式的几何形状。具体地，我们证明了当f (X)满足受限良条件假设时，分解问题的每个临界点对应于最优解X *或一个严格鞍，其中Hessian矩阵具有严格负特征值。这种因子式的几何结构保证了许多局部搜索算法可以通过随机初始化收敛到全局最优。
This work considers the minimization of a general convex function f (X) over the cone of positive semi-definite matrices whose optimal solution X∗ is of low-rank. Standard first-order convex solvers require performing an eigenvalue decomposition in each iteration, severely limiting their scalability. A natural nonconvex reformulation of the problem factors the variable X into the product of a rectangular matrix with fewer columns and its transpose. For a special class of matrix sensing and completion problems with quadratic objective functions, local search algorithms applied to the factored problem have been shown to be much more efficient and, in spite of being nonconvex, to converge to the global optimum. The purpose of this work is to extend this line of study to general convex objective functions f (X) and investigate the geometry of the resulting factored formulations. Specifically, we prove that when f (X) satisfies the restricted well-conditioned assumption, each critical point of the factored problem either corresponds to the optimal solution X∗ or a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a geometric structure of the factored formulation ensures that many local search algorithms can converge to the global optimum with random initializations.