Unlabeled Sensing and Regression with Unknown Correspondence

This direction is split into other directions: unlabeled sensing. Its last version stays readable and citable here.

Version 1 of 178 papers102 conceptsfrozen 2026-10-04

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.

Papers in this version

Showing 60 of 78 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_unlabeled_sensing_and_regression_with_un_6998a865,
  title = {Unlabeled Sensing and Regression with Unknown Correspondence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unlabeled-sensing-and-regression-with-unknown-correspondence/rdr_6998a865bfcb4bd8b59c2972bd6fee96},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_unlabeled_sensing_and_regression_with_un_6998a865_v1,
  title = {Unlabeled Sensing and Regression with Unknown Correspondence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unlabeled-sensing-and-regression-with-unknown-correspondence/rdr_6998a865bfcb4bd8b59c2972bd6fee96/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}