# Unlabeled Principal Component Analysis and Matrix Completion

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 109 references that are in the map.
- First posted on arXiv 23 Jan 2021.

## Builds on (most cited first, 28 of 28)

- [Style Transfer from Non-Parallel Text by Cross-Alignment](https://mlsanity.com/paper/1705.09655/) (2017)
- [DeepPermNet: Visual Permutation Learning](https://mlsanity.com/paper/1704.02729/) (2017)
- [Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery](https://mlsanity.com/paper/1711.09492/) (2017)
- [Fast, Robust and Non-convex Subspace Recovery](https://mlsanity.com/paper/1406.6145/) (2014)
- [Dual Principal Component Pursuit](https://mlsanity.com/paper/1510.04390/) (2015)
- [Streaming PCA and Subspace Tracking: The Missing Data Case](https://mlsanity.com/paper/1806.04609/) (2018)
- [Provable Self-Representation Based Outlier Detection in a Union of Subspaces](https://mlsanity.com/paper/1704.03925/) (2017)
- [Linear Regression with Sparsely Permuted Data](https://mlsanity.com/paper/1710.06030/) (2017)
- [Linear regression without correspondence](https://mlsanity.com/paper/1705.07048/) (2017)
- [Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis](https://mlsanity.com/paper/1609.04789/) (2016)
- [Robust PCA by Manifold Optimization](https://mlsanity.com/paper/1708.00257/) (2017)
- [A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data](https://mlsanity.com/paper/1907.07148/) (2019)
- [Algebraic Variety Models for High-Rank Matrix Completion](https://mlsanity.com/paper/1703.09631/) (2017)
- [Linear Regression without Correspondences via Concave Minimization](https://mlsanity.com/paper/2003.07706/) (2020)
- [Optimal Permutation Recovery in Permuted Monotone Matrix Model](https://mlsanity.com/paper/1911.10604/) (2019)
- [Matrix Completion Under Monotonic Single Index Models](https://mlsanity.com/paper/1512.08787/) (2015)
- [Theoretical Analysis of Sparse Subspace Clustering with Missing Entries](https://mlsanity.com/paper/1801.00393/) (2018)
- [A Pseudo-Likelihood Approach to Linear Regression with Partially Shuffled Data](https://mlsanity.com/paper/1910.01623/) (2019)
- [Word Ordering Without Syntax](https://mlsanity.com/paper/1604.08633/) (2016)
- [Tensor Methods for Nonlinear Matrix Completion](https://mlsanity.com/paper/1804.10266/) (2018)
- [Permutations Unlabeled beyond Sampling Unknown](https://mlsanity.com/paper/1812.00498/) (2018)
- [A Hypergradient Approach to Robust Regression without Correspondence](https://mlsanity.com/paper/2012.00123/) (2020)
- [Hyperplane Clustering Via Dual Principal Component Pursuit](https://mlsanity.com/paper/1706.01604/) (2017)
- [Static and Dynamic Robust PCA and Matrix Completion: A Review](https://mlsanity.com/paper/1803.00651/) (2018)
- [Low-rank matrix completion theory via Plucker coordinates](https://mlsanity.com/paper/2004.12430/) (2020)
- [New Directions in Anonymization: Permutation Paradigm, Verifiability by Subjects and Intruders, Transparency to Users](https://mlsanity.com/paper/1501.04186/) (2015)
- [Homomorphic Sensing of Subspace Arrangements](https://mlsanity.com/paper/2006.05158/) (2020)
- [Results on the algebraic matroid of the determinantal variety](https://mlsanity.com/paper/2002.05082/) (2020)

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

- [ARCS: Accurate Rotation and Correspondence Search](https://mlsanity.com/paper/2203.14493/) (2022)
- [Polynomial Width is Sufficient for Set Representation with High-dimensional Features](https://mlsanity.com/paper/2307.04001/) (2023)
- [Low-rank Matrix Recovery With Unknown Correspondence](https://mlsanity.com/paper/2110.07959/) (2021)
- [Shuffled Multi-Channel Sparse Signal Recovery](https://mlsanity.com/paper/2212.07368/) (2022)
- [Cross-Channel Unlabeled Sensing over a Union of Signal Subspaces](https://mlsanity.com/paper/2506.09773/) (2025)

## Abstract (arXiv)

We introduce robust principal component analysis from a data matrix in which the entries of its columns have been corrupted by permutations, termed Unlabeled Principal Component Analysis (UPCA). Using algebraic geometry, we establish that UPCA is a well-defined algebraic problem in the sense that the only matrices of minimal rank that agree with the given data are row-permutations of the ground-truth matrix, arising as the unique solutions of a polynomial system of equations. Further, we propose an efficient two-stage algorithmic pipeline for UPCA suitable for the practically relevant case where only a fraction of the data have been permuted. Stage-I employs outlier-robust PCA methods to estimate the ground-truth column-space. Equipped with the column-space, Stage-II applies recent methods for unlabeled sensing to restore the permuted data. Allowing for missing entries on top of permutations in UPCA leads to the problem of unlabeled matrix completion, for which we derive theory and algorithms of similar flavor. Experiments on synthetic data, face images, educational and medical records reveal the potential of our algorithms for applications such as data privatization and record linkage.