Abstract: Matrix completion is a problem where one is given some entries of a matrix, and needs to complete the others. Various assumptions have been used to make this problem well-posed, and recently, low rank matrix completion (LRMC) has received the most attention. The low rank assumption means that the columns (or rows) of the matrix to be completed are points on a low-dimensional linear variety. This work extends this thinking to cases where the columns are points on low-dimensional nonlinear algebraic varieties, a problem which we call Low Algebraic-Dimension Matrix Completion (LADMC). We discuss two optimization approaches to this problem, one kernelized algorithm and one that leverages existing LRMC techniques on a tensorized representation of the data. We also provide a formal mathematical justification for the success of our method and experimental results showing that the new approach outperforms existing state-of-the-art methods for matrix completion in many situations.