Information Rank, Not Stable Rank, Governs Unshuffling

Suppose you measure many signals at once through a known linear sensor, but the rows of your output arrive scrambled, so you no longer know which output row belongs to which input row. This is unlabeled sensing. Its central fact is that having several measurement vectors at once can make the scrambling recoverable at modest noise levels. The current theory says the benefit depends on the signal's stable rank: its total energy divided by the energy in its strongest direction. We argue that stable rank is the wrong quantity. What decides whether rows can be matched is a noise-calibrated count, information rank. Each signal direction contributes the logarithm of its own signal-to-noise ratio, and directions buried in noise contribute nothing.

The difference matters most for real signals, whose spectra usually decay. Images, gene panels and sensor arrays tend to have one dominant direction and a long tail of weaker ones. Their stable rank is about 1, and existing theory reads this as reverting to the hopeless single-vector case. Information rank predicts something else: an exponentially decaying spectrum needs only a top signal-to-noise ratio that grows like $e^{O(\sqrt{\log n})}$, not polynomially in the sample size $n$. When the signal must be estimated from the scrambled data itself and the number of measurement vectors is comparable to $n$, high-dimensional PCA inconsistency sets in. Directions below a known spectral detection threshold become invisible to any spectral estimate. We predict that this, not stable rank, opens a gap between what is statistically possible and what practical algorithms achieve.

Core Claim

The model is $Y = \Pi^* X B^* + W$. Here $Y \in \mathbb{R}^{n\times m}$ are the observed outputs, $\Pi^*$ is an unknown row permutation, $X\in\mathbb{R}^{n\times p}$ is a known Gaussian sensing matrix with standard normal entries, $B^*\in\mathbb{R}^{p\times m}$ is the signal with singular values $\sigma_1 \ge \sigma_2 \ge \dots$, and $W$ is Gaussian noise of variance $\sigma^2$ per entry.

Consider the simplest possible error: swapping rows $i$ and $j$. The swap goes unnoticed when $\|(x_i - x_j)B^*\|^2$ is comparable to the noise. This quantity is a weighted chi-square whose weights are the $\sigma_k^2$. The chance that it is small is roughly a product over directions of $\min(1,\sigma/\sigma_k)$. A union bound over the $n^2$ pairs then suggests the threshold

$$\mathcal{I}(B^*,\sigma) \;=\; \sum_k \tfrac12 \log\!\Big(1+\frac{\sigma_k^2}{\sigma^2}\Big) \;\gtrsim\; 2\log n \quad\text{(exact recovery)}, \qquad \mathcal{I} \gtrsim \log n \quad\text{(almost exact)}.$$

This single expression reproduces the two anchor results in the literature.

For one measurement vector it gives a required signal-to-noise ratio of $n^4$ for exact recovery and $n^2$ for almost exact recovery. These are exactly the sharp thresholds proved in Sharp Information-Theoretic Thresholds for Shuffled Linear Regression for the regime where the dimension $p$ is small relative to $n$.

For $r$ equal directions it gives a requirement of $n^{4/r}$. This falls to a constant once $r \asymp \log n$, which is the constant-SNR result of The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing From Multiple Measurement Vectors under its stable-rank condition $\rho(B^*)=\Omega(\log n)$.

The two notions part ways on decaying spectra. Take $\sigma_k^2 = \sigma^2 S q^k$, with top signal-to-noise ratio $S$ and decay rate $q<1$. Stable rank stays near $1/(1-q)$. Information rank instead grows like $(\log S)^2/\log(1/q)$, so the required $S$ is subpolynomial in $n$. The claim that low stable rank "reverts to the single-vector difficulty" is therefore a sufficient-condition artifact, not a property of the problem. Testing that claim is the first contribution.

The second contribution concerns the case where $B^*$ is unknown. The matrix $Y^\top Y$ does not depend on $\Pi^*$, because $\Pi^{*\top}\Pi^* = I$. For Gaussian $X$, $Y^\top Y/n \approx B^{*\top}B^* + \sigma^2 I$, which is a spiked covariance in dimension $m$ estimated from $n$ samples. When $m/n \to \gamma>0$, the direction-$k$ spike becomes undetectable below the threshold $\sigma_k^2/\sigma^2 = \sqrt{\gamma}$. This is the phase transition behind high-dimensional PCA inconsistency, discussed in Information-theoretically optimal sparse PCA. Detected directions just above the threshold are estimated only partially.

We conjecture that efficient methods with unknown $B^*$ are governed by a detectable information rank $\mathcal{I}_{\det}$: the same sum restricted to directions above $\sqrt{\gamma}$, with each term discounted by its estimation quality. Signal directions lying between the noise floor and the detection edge would then help an oracle that knows $B^*$ but not practical algorithms.

Research Program

The theoretical work has two parts.

The first part makes the oracle threshold rigorous. With $B^*$ known, the maximum-likelihood permutation is a linear assignment problem solved exactly by the Hungarian algorithm. We will bound the probability that a permutation cycle goes unnoticed using the weighted chi-square tail. We will also prove a matching lower bound by planting transpositions, following the cycle-decomposition argument of the sharp-threshold paper. The aim is to show that $\mathcal{I}$ replaces stable rank in both directions, up to constants. The proofs will also show whether the extra technical conditions in the diversity paper, such as its Hamming-distance restrictions, are needed.

The second part analyzes estimation with unknown $B^*$. It relies on one fact: denoising $Y$ by shrinking its singular values commutes with row permutations. The SVD of $\Pi Z$ is $\Pi$ times the SVD of $Z$. Spectral denoising can therefore happen before unscrambling.

The algorithm built on this has three steps. First, estimate the noise level and the detectable rank from the bulk edge of $Y$'s singular value distribution. Second, apply singular-value shrinkage that is optimal for the spiked model and project $Y$ onto the detected right subspace. Third, run the bi-convex alternation from the diversity paper on the projected data: assignment steps for $\Pi$ and least-squares steps for $B$.

Choosing the rank with the bulk edge, rather than by permutation-based noise floors, is deliberate. Permutation methods for factor analysis and PCA shows a shadowing effect: a primary factor more than about 35 times the noise can hide a secondary factor at 6 times the noise. Decaying spectra are exactly this situation. That paper constrains our design rather than supplying it.

We will analyze how the alignment between the estimated subspace and the true one enters the assignment step. This yields a formula for $\mathcal{I}_{\det}$ that we can then test.

Finally, we extend the picture to the sparse regime $n \ll p$ handled by One-Step Estimator for Permuted Sparse Recovery. Its Top-1 thresholded proxy $X^\top Y$ also depends only on how energy spreads across directions, and we ask whether $\mathcal{I}$ predicts its phase transition better than stable rank does.

Baselines

The naive reference point uses no permutation correction at all. It either assumes the identity permutation or fits least squares directly to the scrambled rows. Every method must beat it by a wide margin to be meaningful.

The upper reference is the oracle Hungarian assignment with the true $B^*$. It is the exact maximum-likelihood permutation, so it measures what is statistically possible. It is also how we test the oracle half of the theory.

The strongest existing method for unknown $B^*$ is the bi-convex alternating method of The Benefits of Diversity. It is the only cited algorithm designed for the dense-permutation, many-measurement-vector setting we study. In the sparse regime the strongest competitor is the One-Step Estimator with Top-1 thresholding followed by Lasso. For permutations that move only $k$ rows, we add alternating minimization with structured initialization. It is built for exactly that permutation class and would be the natural pick of a practitioner.

All methods will see identical draws of $X$, $B^*$, $W$ and $\Pi^*$. They will share the same iteration cap and receive the same hyperparameter grid size, tuned on held-out random seeds.

No reported result found on Lacuna for the numerical exact-recovery rates of the bi-convex method or the One-Step Estimator on any benchmark. The cited papers report phase-transition shapes and asymptotic thresholds, not tabulated accuracies. We will therefore rerun both baselines rather than quote them. Beating them means one of two things: a lower empirical 50%-recovery signal-to-noise ratio, measured over at least 50 trials per grid point, on spectra whose stable rank is $O(1)$; or a higher fraction of matched rows at a fixed signal-to-noise ratio on real-image spectra.

Three ablations isolate the key ingredient. We compare the full pipeline with (a) no denoising, (b) hard truncation at the bulk edge instead of shrinkage, and (c) rank chosen by parallel analysis instead of the bulk edge.

Why not just…?

Why not just keep stable rank, or the trace-based effective rank used in Oja's Algorithm for Streaming Sparse PCA, and tighten the constants? Both are ratios of energies and ignore the noise level. Two signals with identical stable rank can have very different numbers of directions above the noise. The decisive test fixes stable rank and varies information rank. If recovery curves collapse onto stable rank instead, our claim is wrong.

Why not just count the singular values above the noise floor? This is the real threat, since it is simpler and likely captures most of the effect. The information rank differs by weighting each direction by $\log(\sigma_k^2/\sigma^2)$. That weighting is what predicts the subpolynomial $e^{O(\sqrt{\log n})}$ scaling for decaying spectra; a pure count predicts a different curve. We will fit both proxies, plus stable rank, to the empirical thresholds. If the count explains as much variance across spectra, we will adopt it and say so.

Why not just run the existing bi-convex or One-Step methods on the raw outputs? They may already exploit the weak tail directions, in which case denoising is cosmetic. Ablation (a) settles this. Our prediction is specific: the benefit of denoising appears only when the number of measurement vectors is proportional to $n$, because only then does noise across many output columns swamp the assignment cost. If that interaction does not show up, the algorithmic half of the proposal collapses to the theory alone.

Why not just estimate the subspace with robust PCA, as in Unlabeled Principal Component Analysis? That pipeline treats scrambled samples as outliers against a set of clean inliers. Here every row is scrambled, so no inliers exist. It is also unnecessary: the Gram matrix $Y^\top Y$ is already permutation-invariant, so plain spectral estimation suffices.

Proposed Experiments

The synthetic study uses the Gaussian sensing benchmark from the cited multi-vector papers. The sensing matrix has $n$ up to 2000 and $p = n/20$. The signal matrix has prescribed spectra of three kinds: flat over $r$ directions, exponentially decaying with $q \in \{0.5, 0.8, 0.95\}$, and power-law. Its singular vectors are random.

For each spectrum we sweep the top signal-to-noise ratio and record two quantities: the probability of exact recovery and the fraction of correctly matched rows. We do this for the oracle and for every baseline.

The first decisive check plots the log of the required top signal-to-noise ratio against $\log n$ for fixed decay $q$. Information rank predicts a $\sqrt{\log n}$ curve. A polynomial reading, as stable-rank theory implies, predicts a straight line.

The second decisive check pairs spectra with matched stable rank but information ranks that differ by a factor of three. We test whether their thresholds differ.

The third check varies $m/n$ from 0.05 to 2. Here we measure the gap between the oracle and the practical algorithms, and test whether it tracks $\mathcal{I} - \mathcal{I}_{\det}$ as we predict.

On real spectra, we form $B^*$ from vectorized MNIST digits and from Extended Yale B faces, following their use in the One-Step and unlabeled-PCA papers. We pair these with Gaussian $X$ and controlled noise. This tests whether information rank, computed from each image matrix's own decaying spectrum, predicts when unscrambling succeeds. Its prediction is compared against stable rank. For the sparse regime we repeat the MNIST setting of the One-Step paper with $n \ll p$, measuring permutation accuracy and reconstruction error.

The proposal fails if any of three things happens. Stable rank or the plain count fits the recovery thresholds as well as information rank. The $\sqrt{\log n}$ scaling does not appear for decaying spectra. Or practical algorithms cross threshold below the detection edge, using directions our theory says they cannot see.