mlsanityData to 13 Oct 2026

Unlabeled Principal Component Analysis and Matrix Completion

arXiv 2101.09446 ↗First posted 23 Jan 2021cs.LG stat.MLcited by 5

Not on the map. Why?

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.

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

Builds on

28 of 109 references.

References · 28

  1. 2017Style Transfer from Non-Parallel Text by Cross-Alignmentcited by 247
  2. 2017DeepPermNet: Visual Permutation Learningcited by 32
  3. 2017Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recoverycited by 25
  4. 2014Fast, Robust and Non-convex Subspace Recoverycited by 20
  5. 2015Dual Principal Component Pursuitcited by 19
  6. 2018Streaming PCA and Subspace Tracking: The Missing Data Casecited by 19
  7. 2017Provable Self-Representation Based Outlier Detection in a Union of Subspacescited by 18
  8. 2017Linear Regression with Sparsely Permuted Datacited by 18
  9. 2017Linear regression without correspondencecited by 16
  10. 2016Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysiscited by 13
  11. 2017Robust PCA by Manifold Optimizationcited by 13
  12. 2019A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Datacited by 12
16 more
  1. 2017Algebraic Variety Models for High-Rank Matrix Completioncited by 11
  2. 2020Linear Regression without Correspondences via Concave Minimizationcited by 11
  3. 2019Optimal Permutation Recovery in Permuted Monotone Matrix Modelcited by 10
  4. 2015Matrix Completion Under Monotonic Single Index Modelscited by 8
  5. 2018Theoretical Analysis of Sparse Subspace Clustering with Missing Entriescited by 8
  6. 2019A Pseudo-Likelihood Approach to Linear Regression with Partially Shuffled Datacited by 8
  7. 2016Word Ordering Without Syntaxcited by 7
  8. 2018Tensor Methods for Nonlinear Matrix Completioncited by 7
  9. 2018Permutations Unlabeled beyond Sampling Unknowncited by 7
  10. 2020A Hypergradient Approach to Robust Regression without Correspondencecited by 7
  11. 2017Hyperplane Clustering Via Dual Principal Component Pursuitcited by 6
  12. 2018Static and Dynamic Robust PCA and Matrix Completion: A Reviewcited by 6
  13. 2020Low-rank matrix completion theory via Plucker coordinatescited by 4
  14. 2015New Directions in Anonymization: Permutation Paradigm, Verifiability by Subjects and Intruders, Transparency to Userscited by 2
  15. 2020Homomorphic Sensing of Subspace Arrangementscited by 2
  16. 2020Results on the algebraic matroid of the determinantal varietycited by 1

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 2; 2023: 1; 2024: 0; 2025: 1.

5 papers.

  1. 2022ARCS: Accurate Rotation and Correspondence Searchcited by 15
  2. 2023Polynomial Width is Sufficient for Set Representation with High-dimensional Featurescited by 6
  3. 2021Low-rank Matrix Recovery With Unknown Correspondencecited by 4
  4. 2022Shuffled Multi-Channel Sparse Signal Recoverycited by 1
  5. 2025Cross-Channel Unlabeled Sensing over a Union of Signal Subspacescited by 0