Low-rank matrix completion theory via Plucker coordinates

Abstract

Despite the popularity of low-rank matrix completion, the majority of its theory has been developed under the assumption of random observation patterns, whereas very little is known about the practically relevant case of non-random patterns. Specifically, a fundamental yet largely open question is to describe patterns that allow for unique or finitely many completions. This paper provides two such families of patterns for any rank. A key to achieving this is a novel formulation of low-rank matrix completion in terms of Plucker coordinates, the latter a traditional tool in computer vision. This connection is of potential significance to a wide family of matrix and subspace learning problems with incomplete data.

15 pages, added two new sections 2.4 and 2.5, resolved a long standing issue by new Theorem 4, accepted by IEEE Transactions on Pattern Analysis and Machine Intelligence