| Abstract | Recently, the decomposition based approaches were illustrated to be much more efficient than the convex approximation based methods in solving rank minimization problems, due to no need for calling singular value decomposition in each step. However, such approaches are usually lack of theoretical guarantee. In this paper, we consider the rank minimization problems with linear constraints. We show that for some types of linear constraints, the corresponding decomposition models have no non-global local minimizer. On the other hand, we find a special case in which such property does not hold. By assuming such property holds, we propose a complete decomposition scheme which returns the global solution of the linear constrained rank minimization problem after solving a series of nonlinear least squares to the local optimality. |
