Name
Abstract | ||
|---|---|---|
We consider the problem of noisy matrix completion, in which the goal is to reconstruct a structured matrix whose entries are partially observed in noise. Standard approaches to this underdetermined inverse problem are based on assuming that the underlying matrix has low rank, or is well-approximated by a low rank matrix. In this paper, we first identify how the classical non-negative rank model enforces restrictions that may be undesirable in practice. We propose a richer model based on what we term the “permutation-rank” of a matrix and show how the restrictions due to classical low rank assumptions can be avoided by using the richer permutation-rank model. We establish information-theoretic lower bounds on the rates of estimation, and design an estimator which we prove is simultaneously optimal (up to logarithmic factors) for both the permutation-rank and the low-rank models. Our results thus show that the proposed permutation-rank model and estimator enjoy a surprising win-win in terms of the statistical bias-variance tradeoff as compared to the classical low-rank models. An extended version of this paper is available on arXiv [1]. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/ISIT.2018.8437629 | 2018 IEEE International Symposium on Information Theory (ISIT) |
Keywords | DocType | Volume |
low permutation-rank matrices,noisy matrix completion,nonnegative rank model,inverse problem,structural properties,information-theoretic lower bounds,statistical bias-variance tradeoff | Conference | abs/1709.00127 |
Issue | ISBN | Citations |
101 | 978-1-5386-4102-6 | 1 |
PageRank | References | Authors |
0.35 | 17 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nihar B. Shah | 1 | 1202 | 77.17 |
| Balakrishnan, Sivaraman | 2 | 320 | 25.13 |
| Martin J. Wainwright | 3 | 7398 | 533.01 |