A fast and efficient algorithm for low rank matrix recovery from incomplete observations

Minimizing the rank of a matrix X over certain constraints arises in diverse areas such as machine learning, control system and is known to be computationally NP-hard. In this paper, a new simple and efficient algorithm for solving this rank minimization problem with linear constraints is proposed. By using gradient projection method to optimize S while consecutively updating matrices U and V (where X = USV^T ) in combination with the use of an approximation function for l⁰-norm of singular values, our algorithm is shown to run significantly faster with much lower computational complexity than general-purpose interior-point solvers, for instance, the SeDuMi package. In addition, the proposed algorithm can recover the matrix exactly with much fewer measurements and is also appropriate for large-scale applications.