In classical statistics, we assume our data arrives in neat pairs: for every input $x$, we have a corresponding label $y$. But in many real-world scenarios—ranging from privacy-preserving data releases to multi-target tracking—this link is broken. We might have a set of features and a set of responses, but we have no idea which response belongs to which feature. This challenge is known as unlabeled sensing or the broken sample problem.
The Combinatorial Nightmare
The fundamental difficulty of unlabeled sensing is the sheer scale of possible alignments. If you have $n$ data points, there are $n!$ (n-factorial) ways to pair them. As Martin J Wainwright, Thomas A. Courtade, and Ashwin Pananjady point out in Linear regression with an unknown permutation: Statistical and computational limits, this creates a massive combinatorial gap.
Standard regression minimizes the squared error between paired points. In shuffled regression, we must simultaneously find the signal vector $\beta$ and an unknown permutation matrix $\Pi$ that minimizes $\|y - \Pi X\beta\|^2$. Without the correct $\Pi$, the data looks like random noise; without the correct $\beta$, we have no metric to find $\Pi$.
Solving the Chicken and Egg Problem
To break this cycle, researchers have developed three primary strategies to recover the signal without checking every possible permutation.
1. Algebraic Invariance
One clever approach is to transform the data into a representation that doesn't change when you shuffle it. Manolis C. Tsakiris and Liangzu Peng demonstrate this in An Algebraic-Geometric Approach to Shuffled Linear Regression. By using symmetric polynomials, they can "cancel out" the unknown permutation. This allows them to estimate the signal $\beta$ directly from the shuffled observations, providing a robust starting point for more precise algorithms.
2. Alternating Minimization
If you have a guess for the signal, you can solve for the best permutation using a linear assignment algorithm (like the Hungarian method). Once you have a permutation, you can refine your signal estimate using standard least squares. Locally Permuted Low Rank Column-wise Sensing uses this "Perm-AltGDMin" approach to recover low-rank matrices from scrambled observations, showing that alternating between discrete sorting and continuous optimization can converge quickly to the truth.
3. Soft Matching and Optimal Transport
Instead of picking one "hard" permutation, we can treat the correspondence as a probability distribution. Tsung-Hui Chang and colleagues in Low-rank Matrix Recovery With Unknown Correspondence use entropic optimal transport to turn the discrete search into a smooth optimization problem. Similarly, Abubakar Abid and James Y. Zou propose a Stochastic EM for Shuffled Linear Regression that samples likely permutations, which provides better stability than trying to find a single "best" match in noisy data.
The All-or-Nothing Limit
Is it always possible to "un-shuffle" data? Recent work suggests there is a sharp "phase transition" in these problems. In The Phase Transition Phenomenon of Shuffled Regression, Hang Zhang and Ping Li show that as the signal-to-noise ratio (SNR) increases, there is a specific point where the probability of recovering the correct permutation jumps from zero to one.
Interestingly, having "diverse" data—such as multiple measurements of the same underlying signal—drastically lowers the required SNR. As shown in Optimal Estimator for Linear Regression with Shuffled Labels, even a small amount of repetition or structural complexity (like sparsity) acts as a "fingerprint" that makes the hidden alignment much easier to spot.
Beyond Single Subspaces
While early work focused on simple linear models, the field is moving toward more complex structures. Lei Xie and Jicong Fan 0001 have extended these ideas to Multi-Subspace Matrix Recovery from Permuted Data, where data points might belong to different categories, each with its own hidden structure. This suggests that even when data is completely anonymized and scrambled, the underlying geometric "shape" of the information is often enough to reconstruct the lost connections.