2015/04/20 by Erwin Riegler, Riegler, Erwin, David Stotz +3
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1504.04970
arxiv created 2016/08/10 · arxiv updated 2016/08/11
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× 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\inS]≥ 1-ε, and \underlinedimB(S) denoting the lower Minkowski dimension of S, we show that k> \underlinedimB(S) trace inner product measurements with measurement matrices Ai, suffice to recover X with probability of error at most ε. The result holds for Lebesgue a.a. Ai and does not need incoherence between the Ai and the unknown matrix X. We furthermore show that k> \underlinedimB(S) measurements also suffice to recover the unknown matrix X from measurements taken with rank-one Ai, again this applies to a.a. rank-one Ai. 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.