Convergence analysis of projected gradient descent for Schatten-p nonconvex matrix recovery

Research paper by Yun Cai, Song Li

Indexed on: 05 Dec '14Published on: 05 Dec '14Published in: Science China Mathematics


The matrix rank minimization problem arises in many engineering applications. As this problem is NP-hard, a nonconvex relaxation of matrix rank minimization, called the Schatten-p quasi-norm minimization (0 < p < 1), has been developed to approximate the rank function closely. We study the performance of projected gradient descent algorithm for solving the Schatten-p quasi-norm minimization (0 < p < 1) problem. Based on the matrix restricted isometry property (M-RIP), we give the convergence guarantee and error bound for this algorithm and show that the algorithm is robust to noise with an exponential convergence rate.