Abstract
This paper examines fundamental error characteristics for a general class of matrix completion problems, where the matrix of interest is a product of two a priori unknown matrices, one of which is sparse, and the observations are noisy. Our main contributions come in the form of minimax lower bounds for the expected per-element squared error for this problem under several common noise models. Specifically, we analyze scenarios where the corruptions are characterized by additive Gaussian noise or additive heavier-tailed (Laplace) noise, Poisson-distributed observations, and highly-quantized (e.g., one bit) observations, as instances of our general result. Our results establish that the error bounds derived in (Soni et al., 2016) for complexity-regularized maximum likelihood estimators achieve, up to multiplicative constants and logarithmic factors, the minimax error rates in each of these noise scenarios, provided that the nominal number of observations is large enough, and the sparse factor has (on an average) at least one non-zero per column.
Original language | English (US) |
---|---|
Pages (from-to) | 3274-3285 |
Number of pages | 12 |
Journal | IEEE Transactions on Information Theory |
Volume | 64 |
Issue number | 5 |
DOIs | |
State | Published - May 2018 |
Bibliographical note
Funding Information:Manuscript received September 28, 2015; revised February 14, 2017 and October 26, 2017; accepted December 7, 2017. Date of publication February 27, 2018; date of current version April 19, 2018. This work was supported by the DARPA Young Faculty Award under Grant N66001-14-1-4047.
Publisher Copyright:
© 1963-2012 IEEE.
Keywords
- Matrix completion
- minimax lower bounds
- sparse factor models