  Rank regularized minimization problem is an ideal model for the low-rank
matrix completion/recovery problem. The matrix factorization approach can
transform the high-dimensional rank regularized problem to a low-dimensional
factorized column-sparse regularized problem. The latter can greatly facilitate
fast computations in applicable algorithms, but needs to overcome the
simultaneous non-convexity of the loss and regularization functions. In this
paper, we consider the factorized column-sparse regularized model. Firstly, we
optimize this model with bound constraints, and establish a certain equivalence
between the optimized factorization problem and rank regularized problem.
Further, we strengthen the optimality condition for stationary points of the
factorization problem and define the notion of strong stationary point.
Moreover, we establish the equivalence between the factorization problem and
its a nonconvex relaxation in the sense of global minimizers and strong
stationary points. To solve the factorization problem, we design two types of
algorithms and give an adaptive method to reduce their computation. The first
algorithm is from the relaxation point of view and its iterates own some
properties from global minimizers of the factorization problem after finite
iterations. We give some analysis on the convergence of its iterates to the
strong stationary point. The second algorithm is designed for directly solving
the factorization problem. We improve the PALM algorithm introduced by Bolte et
al. (Math Program Ser A 146:459-494, 2014) for the factorization problem and
give its improved convergence results. Finally, we conduct numerical
experiments to show the promising performance of the proposed model and
algorithms for low-rank matrix completion.
