A rank-corrected procedure for matrix completion with fixed basis coefficients

作者：Miao, Weimin^*; Pan, Shaohua; Sun, Defeng

来源：Mathematical Programming, 2016, 159(1-2): 289-338.

DOI：10.1007/s10107-015-0961-7

• Matrix completion
• Fixed basis coefficients
• Low-rank
• Convex optimization
• Rank consistency
• Constraint nondegeneracy

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 (J Mach Learn Res 9:1019-1048, 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 (A majorized penalty approach for calibrating rank constrained correlation matrix problems. , 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.

• 出版日期2016-9
• 单位华南理工大学