Please use this identifier to cite or link to this item:
Files in This Item:
File SizeFormat 
OWP2013_05.pdf867.27 kBAdobe PDFView/Open
Title: The algebraic combinatorial approach for low-rank matrix completion
Authors: Király, Franz J.Theran, LouisTomioka, RyotaUno, Takeaki
Publishers Version:
Issue Date: 2013
Published in: Oberwolfach Preprints (OWP), Volume 2013-05, ISSN 1864-7596
Publisher: Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach
Abstract: We propose an algebraic combinatorial framework for the problem of completing partially observed low-rank matrices. We show that the intrinsic properties of the problem, including which entries can be reconstructed, and the degrees of freedom in the reconstruction, do not depend on the values of the observed entries, but only on their position. We associate combinatorial and algebraic objects, differentials and matroids, which are descriptors of the particular reconstruction task, to the set of observed entries, and apply them to obtain reconstruction bounds. We show how similar techniques can be used to obtain reconstruction bounds on general compressed sensing problems with algebraic compression constraints. Using the new theory, we develop several algorithms for low-rank matrix completion, which allow to determine which set of entries can be potentially reconstructed and which not, and how, and we present algorithms which apply algebraic combinatorial methods in order to reconstruct the missing entries.
DDC: 510
License: CC BY-SA 3.0 US
Link to License:
Appears in Collections:Mathematik

This item is licensed under a Creative Commons License Creative Commons