Algebraic Variety Models for HighRank Matrix Completion
[edit]
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:26912700, 2017.
Abstract
We consider a nonlinear generalization of lowrank 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 highrank, but it becomes lowrank after mapping each column to a higher dimensional space of monomial features. Algebraic varieties capture a range of wellstudied linear models, including affine subspaces and their union, but also quadratic and higher degree curves and surfaces. We study the sampling requirements for a general variety model with a focus on the union of affine subspaces. We propose an efficient matrix completion algorithm that minimizes a convex or nonconvex surrogate of the rank of the lifted matrix. Our algorithm uses the wellknown “kernel trick” to avoid working directly with the highdimensional lifted data matrix and scales efficiently with data size. We show the proposed algorithm is able to recover synthetically generated data up to the predicted sampling complexity bounds. The algorithm also outperforms standard techniques in experiments with real data.
Related Material


