Information Theoretic Bounds for Low-Rank Matrix Completion

2010/01/14 by Sriram Vishwanath, Vishwanath, Sriram · 1 citation
Computer Science · Engineering · Mathematics · #Blind Source Separation Techniques #Sparse and Compressive Sensing Techniques #Wireless Communication Security Techniques #cs.CC #cs.IT #math.IT #math.PR

paper · pdf · doi:10.48550/arxiv.1001.2331

arxiv created 2010/01/14 · arxiv updated 2016/09/08

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.

Citations

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

Cited by

• Haplotype Assembly: An Information Theoretic View

Related

• Obtaining error-minimizing estimates and universal entry-wise error bounds for low-rank matrix completion
• Information Theory of Matrix Completion
• Computational Limits for Matrix Completion
• A deterministic theory of low rank matrix completion
• A Simpler Approach to Matrix Completion