Title :
Information theoretic bounds for low-rank matrix completion
Author :
Vishwanath, Sriram
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Texas at Austin, Austin, TX, USA
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.
Keywords :
information theory; matrix algebra; erasure channel; information theoretic bounds; low-rank matrix completion problem; order-wise optimal bounds; Algorithm design and analysis; Channel coding; Codes; Communication channels; Concrete; Quantization; Rate-distortion; The Netflix prize;
Conference_Titel :
Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on
Conference_Location :
Austin, TX
Print_ISBN :
978-1-4244-7890-3
Electronic_ISBN :
978-1-4244-7891-0
DOI :
10.1109/ISIT.2010.5513545
