  This paper develops new methods to recover the missing entries of a high-rank
or even full-rank matrix when the intrinsic dimension of the data is low
compared to the ambient dimension. Specifically, we assume that the columns of
a matrix are generated by polynomials acting on a low-dimensional intrinsic
variable, and wish to recover the missing entries under this assumption. We
show that we can identify the complete matrix of minimum intrinsic dimension by
minimizing the rank of the matrix in a high dimensional feature space. We
develop a new formulation of the resulting problem using the kernel trick
together with a new relaxation of the rank objective, and propose an efficient
optimization method. We also show how to use our methods to complete data drawn
from multiple nonlinear manifolds. Comparative studies on synthetic data,
subspace clustering with missing data, motion capture data recovery, and
transductive learning verify the superiority of our methods over the
state-of-the-art.
