  In the low-rank matrix completion (LRMC) problem, the low-rank assumption
means that the columns (or rows) of the matrix to be completed are points on a
low-dimensional linear algebraic variety. This paper extends this thinking to
cases where the columns are points on a low-dimensional nonlinear algebraic
variety, a problem we call Low Algebraic Dimension Matrix Completion (LADMC).
Matrices whose columns belong to a union of subspaces are an important special
case. We propose a LADMC algorithm that leverages existing LRMC methods on a
tensorized representation of the data. For example, a second-order tensorized
representation is formed by taking the Kronecker product of each column with
itself, and we consider higher order tensorizations as well. This approach will
succeed in many cases where traditional LRMC is guaranteed to fail because the
data are low-rank in the tensorized representation but not in the original
representation. We provide a formal mathematical justification for the success
of our method. In particular, we give bounds of the rank of these data in the
tensorized representation, and we prove sampling requirements to guarantee
uniqueness of the solution. We also provide experimental results showing that
the new approach outperforms existing state-of-the-art methods for matrix
completion under a union of subspaces model.
