Permutation Recovery in Unlabeled Sensing

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 29 papers19 conceptsfrozen 2026-10-04

In standard linear regression, we assume a direct correspondence between an input $x_i$ and its observed label $y_i$. But what happens if the labels are shuffled? This scenario, often called the Broken Sample Problem or Unlabeled Sensing, arises when data collection processes lose track of the link between measurements and their sources—such as in multi-target tracking, archaeological dating, or de-anonymized database linkage.

Recent research has transformed this from a seemingly impossible combinatorial nightmare into a solvable statistical problem. The key insight is that the "diversity" of the signal allows us to treat the unknown permutation as a recoverable parameter rather than just noise.

The Geometry of Shuffled Data

If you have a single observation and a single label, and you lose the connection between them, there is no way to recover the truth. However, as Hang Zhang, Ping Li, and their colleagues demonstrate in Optimal Estimator for Linear Regression with Shuffled Labels, the problem changes fundamentally when we have Multiple Measurement Vectors (MMV).

When we observe multiple signals associated with the same underlying permutation, each signal acts as a "vote" for the correct ordering. While a single shuffled label might accidentally fit a wrong input, it is highly unlikely that a sequence of labels across multiple dimensions will all accidentally fit the wrong inputs simultaneously.

Diversity and the Stable Rank

The feasibility of recovery depends on how "distinct" the signals are. If all your data points look nearly identical, shuffling them doesn't change the outcome much, making the original order impossible to find.

To quantify this, researchers like Martin Slawski and Hang Zhang point to the stable rank of the signal matrix. In Permutation Recovery from Multiple Measurement Vectors in Unlabeled Sensing, they show that a higher stable rank—meaning the signal energy is spread across many singular values rather than concentrated in a few—acts as a safeguard.

High signal diversity (high stable rank) provides two main benefits:

  1. Lower SNR Requirements: As diversity increases, the Signal-to-Noise Ratio (SNR) required for perfect recovery drops. In fact, Hang Zhang shows that with enough diversity, the SNR threshold becomes constant, independent of the number of samples.
  2. Uniqueness: It ensures that the correct permutation is the only one that can explain the data, preventing incorrect mappings from matching the observed signal even in the presence of noise.

From Outliers to One-Step Estimators

There are two primary ways to solve this problem computationally:

1. The Sparse Representation Approach

In A Sparse Representation-Based Approach to Linear Regression with Partially Shuffled Labels, Mostafa Rahmani and Martin Slawski treat the shuffling as a form of outlier detection. If only a fraction of the labels are shuffled, the errors can be modeled as a sparse vector. By minimizing the $L_1$ norm of these errors, the model can simultaneously identify which labels were swapped and estimate the true regression parameters.

2. The One-Step Estimator

For cases where the labels are completely shuffled, Hang Zhang and Ping Li developed a "one-step estimator." Introduced in Optimal Estimator for Unlabeled Linear Regression, this method is designed to be computationally efficient—matching the speed of an "oracle" who already knows the permutation—while remaining statistically near-optimal.

This approach was further extended to the high-dimensional regime ($n \ll p$) in One-Step Estimator for Permuted Sparse Recovery. They proved that even when you have more features than samples, the "fingerprint" left by multiple measurements allows for accurate recovery of both the sparse signal and the hidden permutation.

Why It Works: The Intuition

The core takeaway from this body of work is that complexity is a feature, not a bug. In traditional sensing, we often want simple, low-rank structures. But in unlabeled sensing, complexity (in the form of signal diversity and high stable rank) is what makes the data identifiable. The more "unique" each observation is across multiple dimensions, the more "friction" there is against incorrect permutations, allowing researchers to untangle the shuffled labels and recover the underlying truth.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 7 papers
  2. Version 1 · 2026-10-04 · 9 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_stable_rank_dependency_0ac0778a,
  title = {stable rank dependency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stable-rank-dependency/rdr_0ac0778a48bf4d0588c38203773d5197},
  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_permutation_recovery_in_unlabeled_sensin_0ac0778a_v1,
  title = {Permutation Recovery in Unlabeled Sensing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/permutation-recovery-in-unlabeled-sensing/rdr_0ac0778a48bf4d0588c38203773d5197/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}