Information-theoretic limits of matrix completion
Information-theoretic limits of matrix completion
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 random matrices X ∈ ℝ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m×n</sup> of arbitrary distribution (continuous, discrete, discrete-continuous mixture, or even singular). With S ⊆ ℝ <sup …