Uniqueness of low-rank matrix completion by rigidity theory

Amit Singer, Mihai Cucuringu

Research output: Contribution to journalArticle

47 Scopus citations

Abstract

The problem of completing a low-rank matrix from a subset of its entries is often encountered in the analysis of incomplete data sets exhibiting an underlying factor model with applications in collaborative filtering, computer vision, and control. Most recent work has been focused on constructing efficient algorithms for exact or approximate recovery of the missing matrix entries and proving lower bounds for the number of known entries that guarantee a successful recovery with high probability. A related problem from both the mathematical and algorithmic points of view is the distance geometry problem of realizing points in a Euclidean space from a given subset of their pairwise distances. Rigidity theory answers basic questions regarding the uniqueness of the realization satisfying a given partial set of distances. We observe that basic ideas and tools of rigidity theory can be adapted to determine uniqueness of low-rank matrix completion, where inner products play the role that distances play in rigidity theory. This observation leads to efficient randomized algorithms for testing necessary and sufficient conditions for local completion and for testing sufficient conditions for global completion. Crucial to our analysis is a new matrix, which we call the completion matrix, that serves as the analogue of the rigidity matrix.

Original languageEnglish (US)
Pages (from-to)1621-1641
Number of pages21
JournalSIAM Journal on Matrix Analysis and Applications
Volume31
Issue number4
DOIs
StatePublished - Dec 1 2009

All Science Journal Classification (ASJC) codes

  • Analysis

Keywords

  • Collaborative filtering
  • Iterative methods
  • Low-rank matrices
  • Missing values
  • Rigidity theory

Fingerprint Dive into the research topics of 'Uniqueness of low-rank matrix completion by rigidity theory'. Together they form a unique fingerprint.

  • Cite this