Fast and Global Optimal Nonconvex Matrix Factorization via Perturbed Alternating Proximal Point

In this paper, we use the perturbed gradient based alternating minimization for solving a class of low-rank matrix factorization problems. Alternating minimization is a simple but popular approach which has been applied to problems in optimization, machine learning, data mining, and signal processing, etc. By leveraging the block structure of the problem, the algorithm updates two blocks of variables in an alternating manner. For the nonconvex optimization problem, it is well-known the alternating minimization algorithm converges to the first-order stationary solution with a global sublinear rate. In this paper, a perturbed alternating proximal point (PA-PP) algorithm is proposed, which 1) minimizes the smooth nonconvex problem by updating two blocks of variables alternatively and 2) adds some random noise occasionally under some conditions to extract the negative curvature of the second-order information of the objective function. We show that the proposed PA-PP is able to converge (with high probability) to the set of second-order stationary solutions (SS2) with a global sublinear rate, and as a consequence quickly finds global optimal solutions for the problems considered.