Information Theoretic Bounds for Low-Rank Matrix Completion

Understand

This paper studies the low-rank matrix completion problem from an information theoretic perspective.

• The completion problem is rephrased as a communication problem of an (uncoded) low-rank matrix source over an erasure channel.
• The paper then uses achievability and converse arguments to present order-wise optimal bounds for the completion problem.