# Algebraic Variety Models for High-Rank Matrix Completion

arXiv: https://arxiv.org/abs/1703.09631 · HTML: https://mlsanity.com/paper/1703.09631/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2017.

## Built on by (most cited first, 11 of 11)

- [Sensing Theorems for Unsupervised Learning in Linear Inverse Problems](https://mlsanity.com/paper/2203.12513/) (2022)
- [Unlabeled Principal Component Analysis and Matrix Completion](https://mlsanity.com/paper/2101.09446/) (2021)
- [Beyond the Signs: Nonparametric Tensor Completion via Sign Series](https://mlsanity.com/paper/2102.00384/) (2021)
- [Kernel approximation on algebraic varieties](https://mlsanity.com/paper/2106.02755/) (2021)
- [Nonlinear matrix recovery using optimization on the Grassmann manifold](https://mlsanity.com/paper/2109.06095/) (2021)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)
- [Registration of algebraic varieties using Riemannian optimization](https://mlsanity.com/paper/2401.08562/) (2024)
- [Fusion Subspace Clustering for Incomplete Data](https://mlsanity.com/paper/2205.10872/) (2022)
- [Matrix Completion via Residual Spectral Matching](https://mlsanity.com/paper/2412.10005/) (2024)
- [An Interdisciplinary and Cross-Task Review on Missing Data Imputation](https://mlsanity.com/paper/2511.01196/) (2025)
- [High Rank Matrix Completion via Grassmannian Proxy Fusion](https://mlsanity.com/paper/2602.02565/) (2026)

## Abstract (arXiv)

We consider a generalization of low-rank 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 high-rank, but it becomes low-rank after mapping each column to a higher dimensional space of monomial features. Many well-studied extensions of linear models, including affine subspaces and their union, can be described by a variety model. In addition, varieties can be used to model a richer class of nonlinear quadratic and higher degree curves and surfaces. We study the sampling requirements for matrix completion under a variety model with a focus on a union of affine subspaces. We also propose an efficient matrix completion algorithm that minimizes a convex or non-convex surrogate of the rank of the matrix of monomial features. Our algorithm uses the well-known "kernel trick" to avoid working directly with the high-dimensional monomial matrix. We show the proposed algorithm is able to recover synthetically generated data up to the predicted sampling complexity bounds. The proposed algorithm also outperforms standard low rank matrix completion and subspace clustering techniques in experiments with real data.