Low-rank matrix completion theory via Plucker coordinates
This addresses a fundamental gap in theory for matrix completion, which is relevant to matrix and subspace learning problems with incomplete data.
The paper tackles the problem of low-rank matrix completion under non-random observation patterns, providing two families of patterns that allow for unique or finitely many completions for any rank.
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.