# Permutations Unlabeled beyond Sampling Unknown

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

## Key facts

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

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

- [Unlabeled Principal Component Analysis and Matrix Completion](https://mlsanity.com/paper/2101.09446/) (2021)
- [Linear regression with partially mismatched data: local search with theoretical guarantees](https://mlsanity.com/paper/2106.02175/) (2021)
- [Multiview Sensing With Unknown Permutations: An Optimal Transport Approach](https://mlsanity.com/paper/2103.07458/) (2021)
- [Shuffled Multi-Channel Sparse Signal Recovery](https://mlsanity.com/paper/2212.07368/) (2022)
- [Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing](https://mlsanity.com/paper/2211.07621/) (2022)
- [Optimal Estimator for Linear Regression with Shuffled Labels](https://mlsanity.com/paper/2310.01326/) (2023)
- [Cross-Channel Unlabeled Sensing over a Union of Signal Subspaces](https://mlsanity.com/paper/2506.09773/) (2025)

## Abstract (arXiv)

A recent unlabeled sampling result by Unnikrishnan, Haghighatshoar and Vetterli states that with probability one over iid Gaussian matrices A, any x can be uniquely recovered from an unknown permutation of y = A x as soon as A has at least twice as many rows as columns. We show that this condition on A implies something much stronger: that an unknown vector x can be recovered from measurements y = T A x, when the unknown T belongs to an arbitrary set of invertible, diagonalizable linear transformations T. The set T can be finite or countably infinite. When it is the set of m × m permutation matrices, we have the classical unlabeled sampling problem. We show that for almost all A with at least twice as many rows as columns, all x can be recovered either uniquely, or up to a scale depending on T, and that the condition on the size of A is necessary. Our proof is based on vector space geometry. Specializing to permutations we obtain a simplified proof of the uniqueness result of Unnikrishnan, Haghighatshoar and Vetterli. In this letter we are only concerned with uniqueness; stability and algorithms are left for future work.