Matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. However, the problem is in general NP-hard, and it is computationally hard to solve directly in practice. In this paper, we provide a new kind of approximation functions for the rank of matrix, and the corresponding approximation problems can be used to approximate the matrix rank minimization problem within any level of accuracy. Furthermore, the monotonicity and the Frechet derivative of the approximation functions are discussed. On this basis, we design a new method, which is called as successive projected gradient method, for solving the matrix rank minimization problem by using the projected gradient method to find the stationary point of a series of approximation problems. Finally, the convergence analysis and the preliminary numerical results of the successive projected gradient method for the rank minimization problem are given.
Citation
School of Mathematics and Computer Science, Fujian Normal University, Fuzhou 350007, China, 08/2012