Low-rank matrix completion (LRMC) has received tremendous attention in recent years. The low-rank assumption means that the columns (or rows) of the matrix to be completed are points on a low-dimensional linear variety. Our work extends this thinking to cases where the columns are points on low-dimensional nonlinear algebraic varieties, which we call Low Algebraic-Dimension Matrix Completion (LADMC). We propose a LADMC algorithm that leverages existing LRMC methods on a tensorized representation of the data. We also provide a formal mathematical justification for the success of our method. In particular, the new algorithm can succeed in many cases where traditional LRMC is guaranteed to fail, such when the data belongs to a union of subspaces.