Information Theoretic Bounds for Low-Rank Matrix Completion
arXiv:1001.2331
Abstract
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.
References in corpus (6)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- A Singular Value Thresholding Algorithm for Matrix Completion
- Matrix Completion With Noise
- Uniqueness of Low-Rank Matrix Completion by Rigidity Theory
- Learning Low Rank Matrices from O(n) Entries
- On the singularity probability of discrete random matrices