Show simple item record

dc.contributor.authorKirály, Franz J.
dc.contributor.authorTheran, Louis
dc.contributor.authorRyota,Tomioka
dc.contributor.authorUno, Takeaki
dc.date.accessioned2016-09-22T10:46:38Z
dc.date.available2016-09-22T10:46:38Z
dc.date.issued2013-03-14
dc.identifier.urihttp://publications.mfo.de/handle/mfo/195
dc.descriptionOWLF 2012
dc.descriptionOWLF 2013
dc.description.abstractWe 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.en_US
dc.language.isoenen_US
dc.publisherMathematisches Forschungsinstitut Oberwolfachen_US
dc.relation.ispartofseriesOberwolfach Preprints;2013,05
dc.titleThe algebraic combinatorial approach for low-rank matrix completionen_US
dc.typePreprinten_US
dc.identifier.doi10.14760/OWP-2013-05
local.scientificprogramOWLF 2012
local.scientificprogramOWLF 2013
local.series.idOWP-2013-05


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record