# Tensor Methods for Nonlinear Matrix Completion

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2018.

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

- [Unlabeled Principal Component Analysis and Matrix Completion](https://mlsanity.com/paper/2101.09446/) (2021)
- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [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)
- [A Perturbation Bound on the Subspace Estimator from Canonical Projections](https://mlsanity.com/paper/2206.14278/) (2022)
- [An Interdisciplinary and Cross-Task Review on Missing Data Imputation](https://mlsanity.com/paper/2511.01196/) (2025)
- [Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics](https://mlsanity.com/paper/2606.31390/) (2026)

## Abstract (arXiv)

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.