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~(0)-norm of singular values [1], our algorithm is shown to run significantly faster with much lower computational complexity than general-purpose interior-point solvers, for instance, the SeDuMi package [2]. In addition, the proposed algorithm can recover the matrix exactly with much fewer measurements and is also appropriate for large-scale applications.