MATRIX COMPLETION MODELS WITH FIXED BASIS COEFFICIENTS AND RANK REGULARIZED PROBLEMS WITH HARD CONSTRAINTS

The problems with embedded low-rank structures arise in diverse areas such as engineering, statistics, quantum information, finance and graph theory. This thesis is devoted to dealing with the low-rank structure via techniques beyond the widely-used nuclear norm for achieving better performance. In the first part, we propose a rank-corrected procedure for low-rank matrix completion problems with fixed basis coefficients. We establish non-asymptotic recovery error bounds and provide necessary and sufficient conditions for rank consistency. The obtained results, together with numerical experiments, indicate the superiority of our pro- posed rank-correction step over the nuclear norm penalization. In the second part, we propose an adaptive semi-nuclear norm regularization approach to address rank regularized problems with hard constraints via solving their nonconvex but con- tinuous approximation problems instead. This approach overcomes the difficulty of extending the iterative reweighted l1 minimization from the vector case to the matrix case. Numerical experiments show that the iterative scheme of our pro- pose approach has advantages of achieving both the low-rank-structure-preserving ability and the computational efficiency.