Effective Stable Rank: When Noise Fakes the Diversity That Unshuffling Needs

Suppose you observe many measurements of the same hidden linear system, but the rows of your data have been shuffled, so you no longer know which input produced which output. This is unlabeled sensing, sometimes called shuffled regression: responses $Y = \Pi X B + W$, where $X$ is a known $n\times p$ input matrix, $B$ is an unknown $p\times m$ signal matrix whose $m$ columns are the separate measurement channels, $W$ is noise, and $\Pi$ is an unknown row shuffle. Recent theory says that having many channels makes unshuffling dramatically easier. The required signal-to-noise ratio drops from growing with $n$ to a constant, provided $B$ has high stable rank: its energy, $\|B\|_F^2/\|B\|_2^2$, is spread over many directions rather than one. Our claim is that this condition is stated for the wrong matrix. Practical algorithms never see $B$. They see a noisy estimate of it, and when $p$ is comparable to $n$, that estimate behaves like a high-dimensional sample covariance. Its weak directions are pure noise. Worse, noise inflates its stable rank, so the matrix looks "diverse" exactly when the diversity is fake.

We propose to define and test an effective stable rank: the stable rank of only those parts of $B$ that rise above the random-matrix detection threshold, each weighted by how well it can actually be estimated. We will show that this quantity, not the nominal stable rank, predicts where practical unshuffling succeeds or fails. We will then build a denoised version of the standard one-shot estimator from it, together with a check that can be computed from the shuffled data alone and that forecasts, before any matching is attempted, whether recovery will succeed.

Core Claim

The multi-channel theory of The Benefits of Diversity and Greed is good proves that high stable rank of $B$ lowers the noise level at which the shuffle can be recovered. The first paper proves this with an oracle that knows $B$ or through a joint optimization; the second proves it with a non-oracle greedy estimator built from $Y^\top X$. One-Step Estimator for Permuted Sparse Recovery makes the same point for sparse $B$ when $n \ll p$. It uses a "Top-1" thresholding of $X^\top Y$ and then solves a linear assignment problem, which is the polynomial-time problem of choosing the best one-to-one pairing given a fixed cost matrix. All three list low stable rank as their main failure case.

Our observation is that the non-oracle input to the matching step is a spiked random matrix. Write $\hat B = X^\top Y/n$. For Gaussian $X$, this equals $cB + E$, where $c$ is roughly one minus the shuffled fraction, and $E$ is a $p\times m$ matrix of approximately independent entries with variance $\tau^2/n$. The level $\tau^2$ depends on the signal energy and the noise variance. A singular value $\theta_i$ of $cB$ leaves any trace in $\hat B$ only if

$$\theta_i > \tau\,(pm)^{1/4}/\sqrt{n},$$

which is the rectangular analogue of the eigenvector phase transition in high-dimensional PCA (Information-theoretically optimal sparse PCA). Below this threshold, the estimated singular vector is asymptotically orthogonal to the true one. Above it, the estimated singular vector retains a predictable cosine $\kappa_i<1$ with the truth, a value that random matrix theory supplies. We define the effective stable rank as

$$\rho_{\mathrm{eff}}(B) = \sum_{i:\,\theta_i>\text{threshold}} \frac{\kappa_i^2\theta_i^2}{\kappa_1^2\theta_1^2}.$$

We conjecture that the recovery thresholds of non-oracle estimators, including greedy, one-step, and one-shot matching, depend on $\rho_{\mathrm{eff}}$ wherever the existing theorems depend on $\rho(B)$. When $p/n\to 0$, the two quantities coincide, which is consistent with prior results. When $p/n$ is non-negligible, they separate sharply. A matrix $B$ with a slowly decaying spectrum can have large $\rho(B)$ but $\rho_{\mathrm{eff}}\approx 1$, and the existing guarantees then say nothing true about it.

This reframes the open problem of "low stable rank" in a more useful way. In high dimensions, the obstacle is often estimation-induced low stable rank rather than a truly collinear signal. That kind of obstacle can be diagnosed, and part of it can be corrected.

Research Program

The program has three parts.

Theory. We will first extend the leave-one-out analysis of Greed is good to the proportional regime $p/n\to\gamma>0$. The goal is a recovery threshold for one-shot assignment in terms of $\rho_{\mathrm{eff}}$, applied both to the raw $\hat B$ and to a spectrally denoised $\tilde B$. For the denoised estimator, $\tilde B$ keeps the singular vectors of $\hat B$, sets every singular value below the threshold to zero, and replaces each surviving singular value with its asymptotically optimal shrunken value. This is the matrix analogue of what the one-step paper's Top-1 rule does coordinate-wise. The claim to prove is that the raw estimator's threshold is governed by the nominal energy including noise, which misleads, while the denoised estimator's threshold is governed by $\rho_{\mathrm{eff}}$.

Diagnostic. The Gram matrix $Y^\top Y = B^\top X^\top \Pi^\top \Pi X B + \dots$ does not depend on $\Pi$ at all. So $Y^\top Y/n - \sigma^2 I$ is an unbiased, shuffle-free estimate of $B^\top B$. After correcting its spectrum for high-dimensional spreading, it yields estimates of the $\theta_i$, and from them the threshold and $\rho_{\mathrm{eff}}$. This gives a certificate computed before any matching is run: it predicts whether a given dataset is unshufflable by one-shot methods. No paper in the file uses this invariance as a diagnostic.

Algorithm. The denoised estimator runs in three steps: form $\tilde B$, solve one linear assignment with the Hungarian algorithm on the cost matrix $\langle y_i, \tilde B^\top x_j\rangle$, and refit $B$. The same $\tilde B$ also serves as a warm start for alternating minimization. That is the setting where Regression with Label Permutation in GLM and Alternating minimization for unlabeled sensing report sensitivity to initialization.

We deliberately keep the Gaussian-design assumption at first. Moving to correlated designs is a follow-up, and the Gram-matrix diagnostic makes it natural, since it would then estimate $B^\top\Sigma_X B$.

Baselines

The naive reference fits least squares on the shuffled data as if no shuffle existed. Regularization for Shuffled Data Problems documents that this kind of estimator badly overshoots the true slopes. Beating it is necessary but uninformative. The oracle reference solves the linear assignment with the true $B$, following The Benefits of Diversity. It is an upper bound, and our method should close most of the gap between the raw non-oracle estimator and this oracle.

The strongest direct competitors are the two non-oracle estimators built on raw cross-correlations. One is greedy matching on $Y^\top X$ from Greed is good. The other is the Top-1 one-step estimator from One-Step Estimator, used in the sparse-$B$ variants. They are the strongest competitors because they are the only polynomial-time methods in the file with non-oracle guarantees that depend on stable rank. We also include the bi-convex joint optimization solved by ADMM from The Benefits of Diversity as the strongest iterative joint method.

All methods receive identical $(X, Y)$ draws and the same noise level $\sigma^2$, which is either known or estimated from the bulk of the $Y^\top Y$ spectrum for everyone. Iterative methods get the same wall-clock budget and the same number of alternations. Every tuning parameter, including Top-1 versus Top-$k$ and the ADMM penalty, is tuned on held-out synthetic draws with an equal budget. For none of these baselines does the file report a numerical permutation-recovery figure on a shared benchmark. The one-step method's MNIST result is described only qualitatively ("reconstructed the original digits where standard methods failed"). So no reported result was found on Lacuna for exact-recovery rate on these protocols, and we will rerun every baseline ourselves.

Beating the baselines means a statistically significant rightward shift of the noise level at which exact recovery reaches 50% probability, in the regime $p/n\ge 0.2$ with slowly decaying spectra. The same shift should be absent, or negligible, when $p/n\to 0$, as the theory predicts.

Two ablations isolate the key ingredient. The first is truncated SVD at the true rank. The second is truncated SVD at a rank chosen by an elbow heuristic. Both separate "removing noise directions" from "choosing the cutoff and the shrinkage by random-matrix theory."

Why not just…?

Why not just keep the top-$r$ singular directions of $X^\top Y$? This is the real threat. If $r$ is known, hard truncation captures most of the benefit, and optimal shrinkage typically adds only a modest amount near the threshold. We will not argue otherwise. The contribution then rests on two things. The first is the location of the cutoff: the threshold depends on $p$, $m$, $n$, and $\tau$ in a way no fixed rank heuristic tracks as $p/n$ varies. The second is the $\rho_{\mathrm{eff}}$ characterization itself. The oracle-rank truncation ablation settles this directly. If it matches our estimator everywhere, we will report the algorithmic gain as nil and present the method as a principled rank selector plus theory.

Why not just run more alternating-minimization iterations from the raw estimate? Alternation can repair a mediocre starting point. Regression with Label Permutation in GLM reports, however, that it gets trapped without accurate warm starts once many rows are shuffled. We test this by running alternation from both the raw and the denoised starting points with equal budgets. The prediction is that the two converge to the same answer when $\rho_{\mathrm{eff}}$ is high, and differ when the raw estimate's inflated stable rank misleads the first assignment.

Why not just use Top-1 or sparse thresholding, which already denoises? Top-1 removes noise coordinate by coordinate. It is optimal when $B$ is sparse, as shown in One-Step Estimator, but it has no mechanism for a dense $B$ whose structure lives in its singular directions. In the sparse variants we will compare Top-1, spectral denoising, and their composition. We expect Top-1 to win for very sparse $B$ and spectral denoising to win for dense, low-effective-rank $B$, and the experiment will show whether that crossover exists.

Why not just check $\rho(B)$ directly? Nobody observes $B$. The naive plug-in, the stable rank of $\hat B$, is precisely the noise-inflated quantity that our thesis says is misleading. Its failure as a predictor is one of our decisive checks.

Proposed Experiments

The synthetic protocol follows the permuted Gaussian sensing setups of the multi-channel papers. We vary $n\in\{200,500,1000\}$, $p/n\in\{0.05,0.2,0.5,1\}$, $m\in\{\log n, \sqrt n, n\}$, and the shuffled fraction from sparse to fully dense. The spectrum of $B$ takes one of three shapes: flat, geometric decay, or "few strong spikes plus many sub-threshold ones." The key design is paired matrices $B$ with identical $\rho(B)$ but very different $\rho_{\mathrm{eff}}$. Metrics are exact-recovery probability, fraction of correctly matched rows, and relative error of $B$ after refitting, averaged over 100 draws per cell.

For real signals, we use MNIST digit images as columns of $B$, following the one-step paper's use of MNIST. Natural images have decaying spectra, which makes them a realistic test of the low-effective-rank regime. We will also run the DJIA weekly indicators (Regression with Label Permutation in GLM) with synthetic Gaussian $X$, as a correlated-signal case.

Three checks decide the question. First, recovery-probability curves from all spectrum shapes should collapse onto one curve when plotted against noise level scaled by $\rho_{\mathrm{eff}}$, and should not collapse when scaled by $\rho(B)$. Second, the shuffle-free Gram-matrix diagnostic should predict one-shot success on held-out draws substantially better than the stable rank of $\hat B$, measured by area under the ROC curve. Third, the denoised estimator should shift the 50%-recovery noise threshold beyond the raw greedy and one-step estimators in the proportional regime while matching them as $p/n\to 0$. If the first check fails, the effective-stable-rank thesis is wrong and we will say so. If only the third fails against oracle-rank truncation, the paper becomes a theory-and-diagnostic contribution rather than an algorithmic one.