  We consider a generalization of low-rank matrix completion to the case where
the data belongs to an algebraic variety, i.e. each data point is a solution to
a system of polynomial equations. In this case the original matrix is possibly
high-rank, but it becomes low-rank after mapping each column to a higher
dimensional space of monomial features. Many well-studied extensions of linear
models, including affine subspaces and their union, can be described by a
variety model. In addition, varieties can be used to model a richer class of
nonlinear quadratic and higher degree curves and surfaces. We study the
sampling requirements for matrix completion under a variety model with a focus
on a union of affine subspaces. We also propose an efficient matrix completion
algorithm that minimizes a convex or non-convex surrogate of the rank of the
matrix of monomial features. Our algorithm uses the well-known "kernel trick"
to avoid working directly with the high-dimensional monomial matrix. We show
the proposed algorithm is able to recover synthetically generated data up to
the predicted sampling complexity bounds. The proposed algorithm also
outperforms standard low rank matrix completion and subspace clustering
techniques in experiments with real data.
