A Rank-Corrected Procedure for Matrix Completion with Fixed Basis Coefficients
arXiv:1210.3709
Abstract
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.
arXiv comment51 pages, 4 figures
References in corpus (24)
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Rejoinder to "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Least Angle Regression
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Discussion of "Least angle regression" by Efron et al
- Nearly unbiased variable selection under minimax concave penalty
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Quantum state tomography via compressed sensing
- Nonconcave penalized likelihood with a diverging number of parameters
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
- Estimation of high-dimensional low-rank matrices
- Consistency of trace norm minimization
- Matrix Completion from a Few Entries
- Adaptive Lasso for High Dimensional Regression and Gaussian Graphical Modeling
- Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
- Universal low-rank matrix recovery from Pauli measurements
- Learning with the Weighted Trace-norm under Arbitrary Sampling Distributions
- Asymptotic equivalence of quantum state tomography and noisy matrix completion