# Polynomial Matrix Completion for Missing Data Imputation and Transductive Learning

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2019.

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

- [Data Imputation with Iterative Graph Reconstruction](https://mlsanity.com/paper/2212.02810/) (2022)
- [BrainODE: Dynamic Brain Signal Analysis via Graph-Aided Neural Ordinary Differential Equations](https://mlsanity.com/paper/2405.00077/) (2024)
- [A Simple Approach to Automated Spectral Clustering](https://mlsanity.com/paper/2107.12183/) (2021)
- [Explainability of Machine Learning Models under Missing Data](https://mlsanity.com/paper/2407.00411/) (2024)
- [Unique sparse decomposition of low rank matrices](https://mlsanity.com/paper/2106.07736/) (2021)
- [Nonlinear matrix recovery using optimization on the Grassmann manifold](https://mlsanity.com/paper/2109.06095/) (2021)
- [Conditional expectation with regularization for missing data imputation](https://mlsanity.com/paper/2302.00911/) (2023)
- [Blockwise Principal Component Analysis for monotone missing data imputation and dimensionality reduction](https://mlsanity.com/paper/2305.06042/) (2023)
- [DPER: Efficient Parameter Estimation for Randomly Missing Data](https://mlsanity.com/paper/2106.05190/) (2021)
- [Imputation using training labels and classification via label imputation](https://mlsanity.com/paper/2311.16877/) (2023)
- [Directly Handling Missing Data in Linear Discriminant Analysis for Enhancing Classification Accuracy and Interpretability](https://mlsanity.com/paper/2407.00710/) (2024)
- [DPERC: Direct Parameter Estimation for Mixed Data](https://mlsanity.com/paper/2501.10540/) (2025)
- [Challenges and proposed solutions in modeling multimodal medical data: A systematic review](https://mlsanity.com/paper/2505.06945/) (2025)
- [Distributed clustering in partially overlapping feature spaces](https://mlsanity.com/paper/2510.09799/) (2025)
- [An Interdisciplinary and Cross-Task Review on Missing Data Imputation](https://mlsanity.com/paper/2511.01196/) (2025)

## Abstract (arXiv)

This paper develops new methods to recover the missing entries of a high-rank or even full-rank matrix when the intrinsic dimension of the data is low compared to the ambient dimension. Specifically, we assume that the columns of a matrix are generated by polynomials acting on a low-dimensional intrinsic variable, and wish to recover the missing entries under this assumption. We show that we can identify the complete matrix of minimum intrinsic dimension by minimizing the rank of the matrix in a high dimensional feature space. We develop a new formulation of the resulting problem using the kernel trick together with a new relaxation of the rank objective, and propose an efficient optimization method. We also show how to use our methods to complete data drawn from multiple nonlinear manifolds. Comparative studies on synthetic data, subspace clustering with missing data, motion capture data recovery, and transductive learning verify the superiority of our methods over the state-of-the-art.