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

W. Miao, S. Pan, Defeng Sun

Research output: Journal article publicationJournal articleAcademic researchpeer-review

23 Citations (Scopus)

Abstract

© 2015, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. 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.
Original languageEnglish
Pages (from-to)289-338
Number of pages50
JournalMathematical Programming
Volume159
Issue number1-2
DOIs
Publication statusPublished - 1 Sep 2016
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this