  For the problems of low-rank matrix completion, the efficiency of the
widely-used nuclear norm technique may be challenged under many circumstances,
especially when certain basis coefficients are fixed, for example, the low-rank
correlation matrix completion in various fields such as the financial market
and the low-rank density matrix completion from the quantum state tomography.
To seek a solution of high recovery quality beyond the reach of the nuclear
norm, in this paper, we propose a rank-corrected procedure using a nuclear
semi-norm to generate a new estimator. For this new estimator, we establish a
non-asymptotic recovery error bound. More importantly, we quantify the
reduction of the recovery error bound for this rank-corrected procedure.
Compared with the one obtained for the nuclear norm penalized least squares
estimator, this reduction can be substantial (around 50%). We also provide
necessary and sufficient conditions for rank consistency in the sense of Bach
(2008). Very interestingly, these conditions are highly related to the concept
of constraint nondegeneracy in matrix optimization. As a byproduct, our results
provide a theoretical foundation for the majorized penalty method of Gao and
Sun (2010) and Gao (2010) for structured low-rank matrix optimization problems.
Extensive numerical experiments demonstrate that our proposed rank-corrected
procedure can simultaneously achieve a high recovery accuracy and capture the
low-rank structure.
