MULTISTAGE CONVEX RELAXATION APPROACH TO RANK REGULARIZED MINIMIZATION PROBLEMS BASED ON EQUIVALENT MATHEMATICAL PROGRAM WITH A GENERALIZED COMPLEMENTARITY CONSTRAINT

摘要

This paper concerns itself with the rank regularized minimization problem with a spectral norm ball constraint. We reformulate this NP-hard problem as an equivalent MPGCC (mathematical program with a generalized complementarity constraint) and show that the penalty problem, yielded by moving the generalized complementarity constraint to the objective, is exact in the sense that it has the same global optimal solution set as the MPGCC does when the penalty parameter is over a threshold. Then, by solving the exact penalty problem in an alternating way, we propose a multistage convex relaxation approach, and provide its theoretical guarantee for the rank regularized least squares problem with a spectral norm ball constraint. Specifically, we derive the error and approximate rank bounds for the optimal solution of each stage and quantify the reduction of the error and approximate rank bounds of the first stage convex relaxation (which is exactly the nuclear norm relaxation) in the subsequent stages. In particular, we establish the geometric convergence in a statistical sense for the error sequence, which reduces to the linear convergence in the noiseless case and implies the exact recoverability of the multistage convex relaxation approach. Numerical experiments are conducted on some low-rank matrix recovery examples to confirm the theoretical results.