The algebraic combinatorial approach for low-rank matrix completion

Franz Király, Louis Theran, Ryota Tomioka

Research output: Contribution to journalArticlepeer-review

32 Citations (Scopus)


We present a novel algebraic combinatorial view on low-rank matrix completion based on studying relations between a few entries with tools from algebraic geometry and matroid theory. The intrinsic locality of the approach allows for the treatment of single entries in a closed theoretical and practical framework. More specifically, apart from introducing an algebraic combinatorial theory of low-rank matrix completion, we present probability-one algorithms to decide whether a particular entry of the matrix can be completed. We also describe methods to complete that entry from a few others, and to estimate the error which is incurred by any method completing that entry. Furthermore, we show how known results on matrix completion and their sampling assumptions can be related to our new perspective and interpreted in terms of a completability phase transition.
Original languageEnglish
Pages (from-to)1391-1436
Number of pages46
JournalJournal of Machine Learning Research
Publication statusPublished - 1 Aug 2015


  • Low-rank matrix completion
  • Entry-wise completion
  • Matrix reconstruction
  • Algebraic combinatorics


Dive into the research topics of 'The algebraic combinatorial approach for low-rank matrix completion'. Together they form a unique fingerprint.

Cite this