Lower Bounds on the Mean-Squared Error of Low-Rank Matrix Reconstruction
Authors:
- 12 July 2011
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 59 (10) , 4559-4571
Abstract
We investigate the behavior of the mean-square error (MSE) of low-rank matrix reconstruction and its special case, matrix completion. We first derive the constrained Cramér-Rao bound (CRB) on the MSE matrix of any locally unbiased estimator, and then analyze the behavior of the constrained CRB when a subset of entries of the underlying matrix is randomly observed. We design an alternating minimization procedure to compute the maximum likelihood estimator (MLE) for the low-rank matrix, and demonstrate through numerical simulations that the performance of the MLE approaches the constrained CRB when the signal-to-noise ratio is high. Applying a Chapman-Robbins type Barankin bound allows us to derive lower bounds on the worst-case scalar MSE. We demonstrate that the worst-case scalar MSE is infinite even if the model is identifiable. However, the infinite scalar MSE is achieved only on a set of low-rank matrices with measure zero. We discuss the implications of these bounds and compare them with the empirical performance of the matrix LASSO estimator and the existing bounds in the literature.Keywords
This publication has 32 references indexed in Scilit:
- Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random MeasurementsIEEE Transactions on Information Theory, 2011
- The Power of Convex Relaxation: Near-Optimal Matrix CompletionIEEE Transactions on Information Theory, 2010
- Fixed point and Bregman iterative methods for matrix rank minimizationMathematical Programming, 2009
- The restricted isometry property and its implications for compressed sensingComptes Rendus Mathématique, 2008
- On sparse reconstruction from Fourier and Gaussian measurementsCommunications on Pure and Applied Mathematics, 2007
- Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements2006
- Radial Basis Functions2003
- Probability in Banach Spaces1991
- MUSIC, maximum likelihood, and Cramer-Rao bound: further results and comparisonsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1990
- Lower bounds for parametric estimation with constraintsIEEE Transactions on Information Theory, 1990