Information-theoretic limits of matrix completion

Authors

Erwin Riegler, David Stotz, and Helmut Bölcskei

Reference

Proc. of IEEE International Symposium on Information Theory (ISIT), Hong Kong, China, pp. 1836-1840, June 2015.

Abstract

We propose an information-theoretic framework for matrix completion. The theory goes beyond the low-rank structure and applies to general matrices of “low description complexity”. Specifically, we consider m x n random matrices X of arbitrary distribution (continuous, discrete, discrete-continuous mixture, or even singular). With S an ε-support set of X, i.e., P[X in S] ≥ 1 − ε, and dim_B(S) denoting the lower Minkowski dimension of S, we show that k > dim_B(S) trace inner product measurements with measurement matrices A_i, suffice to recover X with probability of error at most ε. The result holds for Lebesgue a.a. A_i and does not need incoherence between the A_i and the unknown matrix X. We furthermore show that k > dim_B(S) measurements also suffice to recover the unknown matrix X from measurements taken with rank-one A_i, again this applies to a.a. rank-one A_i. Rank-one measurement matrices are attractive as they require less storage space than general measurement matrices and can be applied faster. Particularizing our results to the recovery of low-rank matrices, we find that k > (m+n−r)r measurements are sufficient to recover matrices of rank at most r. Finally, we construct a class of rank-r matrices that can be recovered with arbitrarily small probability of error from k < (m + n − r)r measurements.

Keywords

Matrix completion, compressive sensing, Minkowski dimension, information theory

Comments

The version posted here corrects a mathematical typo in the version published in the proceedings. Specifically, we added a missing logarithm in the second line from the bottom in the left column on page 5.

Download this document:

Copyright Notice: © 2015 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.