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

详细信息    查看全文

• 作者：Weimin Miao ; Shaohua Pan ; Defeng Sun
• 刊名：Mathematical Programming
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：159
• 期：1-2
• 页码：289-338
• 全文大小：1,129 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646
• 卷排序：159

文摘

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. http://www.math.nus.edu.sg/~matsundf/MajorPen_May5.pdf, 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.KeywordsMatrix completionFixed basis coefficientsLow-rank Convex optimizationRank consistencyConstraint nondegeneracy