The rank minimization with linear equality constraints has two closely related models, the low rank approximation model, that is to find the best rank-k approximation of a matrix satisfying the linear constraints, and its corresponding factorization model. The latter one is an unconstrained nonlinear least squares problem and hence enjoys a few fast first-order methods such as the nonlinear successive over-relaxation algorithm LMaFit or alternating least squares. However, the solutions obtained by the above mentioned approaches lack of global optimality guarantee. In this paper, we focus on exploring the theoretical properties of the factorization model of the low rank approximation with linear constraints. Under some particular situations, we show that the corresponding factorization models are of the property that all second-order stationary points are global minimizers. By assuming such property holds, we propose an algorithm framework which outputs the global solution of the linear constrained rank minimization problem after solving a series of its factorization models with different ranks to the second-order necessary optimality. The adaptive regularization with cubics can be used as the inner local solvers to obtain the second-order stationary point. Finally, we put forward a conjecture that the reduction between the global minima of the low rank approximation with consecutive ranks is monotonically decreasing with the increase of the rank. If this conjecture holds, we can accelerate the estimation of the optimal rank by an adaptive technique, and hence significantly increase the efficiency of the overall performance of our framework in solving the linear constrained rank minimization problem.
Citation
1/2015