In shuffled regression, also called unlabeled sensing, we observe inputs and outputs whose row-to-row pairing has been scrambled by an unknown permutation. We must recover both the pairing and the regression coefficients. The best guarantees today come from one-shot estimators, which build a single matching score from the data and solve one assignment problem. Their theory needs the coefficient matrix to have high stable rank: its energy must be spread over many directions rather than concentrated in a few. When the energy is concentrated, these guarantees fail.
This proposal asks whether that requirement is intrinsic to the problem or an artifact of estimating the coefficients only once. We will compare one-shot estimators against an oracle that knows the true coefficients. We will then prove, using leave-one-out analysis, that a few rounds of alternating minimization without data splitting close the gap between the two. Alternating minimization is the loop "fit coefficients given the pairing, re-pair given the coefficients." Leave-one-out analysis is a proof technique that compares the real algorithm with copies run on data missing one observation, which restores the independence that standard concentration bounds need.
The prize is concrete. It is the first multi-step convergence theory for the iterative method practitioners actually run. It also gives an honest map of which parts of the stable-rank barrier iteration can remove and which it cannot.
Core Claim
The model is $Y = \Pi^* X B^* + W$. Here $X \in \mathbb{R}^{n\times p}$ holds the inputs, $B^* \in \mathbb{R}^{p\times m}$ is the unknown coefficient matrix with $m$ response columns, $\Pi^*$ is an unknown $n\times n$ permutation, and $W$ is noise. The stable rank is
$$\rho(B^*) = \frac{\|B^*\|_F^2}{\|B^*\|_2^2},$$
which is the ratio of total energy to energy in the top direction. It ranges from 1 to $\min(p,m)$.
Stable rank enters recovery in two separate places, and current proofs mix them together.
The first place is intrinsic. Even an oracle that knows $B^*$ must tell apart the predicted rows $B^{*\top}x_j$ under noise. For Gaussian inputs, the chance that two predicted rows nearly coincide is a small-ball probability, and that probability improves as $\rho$ grows. The inachievability results of The Benefits of Diversity apply even to known $B^*$: they show exact recovery at $m=1$ needs signal-to-noise ratio (SNR) polynomial in $n$. That part of the barrier no algorithm can remove.
The second place is the proxy. One-shot methods replace $B^*$ with a matching score built from $Y^\top X$ or $YY^\top XX^\top$. Cross-row interference terms in that score concentrate only when energy is spread across many columns. This affects Optimal Estimator for Unlabeled Linear Regression, Greed is Good, and One-Step Estimator for Permuted Sparse Recovery.
We conjecture, and aim to prove, that no-split alternating minimization started from a one-shot estimate reaches the oracle's recovery threshold as a function of $\rho$. If true, whatever stable-rank requirement remains is intrinsic. We also conjecture that the set of starting pairings from which iteration succeeds, measured in number of mismatched rows, grows with $\rho$. This would turn the stable-rank dependence into a statement about how far from the truth the algorithm can safely start.
Research Program
The analysis needs one design choice to be tractable. In the re-pairing step we use row-wise greedy selection instead of a global linear assignment problem. Each response row $y_i$ is matched to the input row $x_j$ whose prediction $B_t^\top x_j$ is nearest. This is the selection rule of Greed is Good, applied repeatedly. A global assignment couples all rows, so leaving one row out can change every match. Greedy selection keeps each row's decision local, which is what leave-one-out arguments need. A single assignment-problem rounding at the end restores a valid permutation. We will test separately whether the greedy choice costs accuracy.
The algorithm alternates two steps: least squares for $B_{t+1}$ given the current matching, and greedy re-matching given $B_{t+1}$. For each row $i$ we define an auxiliary trajectory. It runs the identical algorithm with $y_i$ and its true partner $x_{\pi^*(i)}$ replaced by independent copies. The auxiliary coefficient estimate $B_t^{(i)}$ has never seen row $i$, so the matching decision for $y_i$ made with $B_t^{(i)}$ can be bounded with ordinary concentration.
Two quantities then need control. The first is the stability gap $\|B_t - B_t^{(i)}\|$, following the decomposition in Implicit Regularization in Nonconvex Statistical Estimation. The second is how a small coefficient error propagates to matching errors. That propagation is governed by the small-ball behavior that depends on $\rho$.
The target result is a recursion on the fraction of mismatched rows $h_t/n$:
$$\frac{h_{t+1}}{n} \le \epsilon_{\mathrm{orc}}(\rho, \mathrm{SNR}) + \kappa(\rho, p/n)\,\frac{h_t}{n}.$$
Here $\epsilon_{\mathrm{orc}}$ is the per-row error rate of the oracle matcher, and $\kappa$ is a contraction factor. The factor $\kappa$ comes from how $h_t$ mismatched rows perturb the least-squares fit. It should fall below 1 once $h_t/n$ is under a threshold that grows with $\rho$. If the recursion holds, iteration converges to the oracle's error level whenever the starting point lies inside that threshold.
This departs from prior work in three ways. Alternating minimization for generalized rank one matrix sensing tracks alternating minimization with leave-one-out tools, but it has no permutation, is rank-one, and splits samples. The alternating-minimization papers by Abbasi et al. (2025, 2022; Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing) analyze only the initialization and never parameterize the problem by stable rank. Zhang and Li use leave-one-out arguments only for a single step.
Because it is an honest limit, we do not claim to close the $m=1$ gap for exact recovery. At $m=1$ the target is the fraction of mismatched rows, where the oracle's error rate is the correct benchmark.
Baselines
The naive reference is ordinary least squares that ignores the shuffle and treats the identity as the pairing. It shows how much any matching buys.
The upper reference is the oracle: one assignment-problem solve using the true $B^*$. It defines the intrinsic threshold we claim iteration reaches.
The strongest existing competitors are the one-shot estimators. The first is the assignment-problem proxy of Optimal Estimator for Unlabeled Linear Regression. It is the strongest because it is within a $\log\log n$ factor of the lower bound when $\rho$ is high, which is exactly the regime where we must show no loss. The second is the non-oracle greedy estimator of Greed is Good, which is also our initializer. That makes the comparison with and without iteration exact.
We also run two iterative competitors. One is the ADMM heuristic of The Benefits of Diversity. The other is Abbasi et al.'s alternating minimization with collapsed or identity initialization, which is the strongest empirical method on real linked-regression data.
Two ablations isolate our ingredients. The first is sample-split alternating minimization run on the same data, which isolates the value of reusing data. The second is assignment-problem re-matching instead of greedy re-matching, which tests whether our tractability choice costs accuracy.
Fairness rules apply to all methods. Every method sees identical data draws and identical noise. Iterative methods get the same iteration cap and the same stopping rule. ADMM gets a tuning grid of equal size to ours, and the noise variance is supplied to every method or to none.
No reported numeric result was found on Lacuna for exact-recovery probability of any one-shot estimator at a specified SNR and stable rank. The file reports only qualitative sharp phase transitions at $n=500$ and $n=1000$. Likewise, no reported result was found on Lacuna for the $R^2$ of AltMin-r/AltMin-k on ames, air-qty, ftp, or scm. We will therefore rerun all baselines ourselves.
Beating the strongest one-shot baseline means two things. At low $\rho$, the SNR at which exact recovery reaches 50% must shift measurably toward the oracle's. At high $\rho$, it must be no worse.
Why not just…?
Why not just use the one-shot estimators, which are already near-optimal? This is the real threat, and the first experiment settles it. If the one-shot phase-transition curves already coincide with the oracle's across low and high $\rho$, then the stable-rank requirement in their proofs is a proof artifact rather than an algorithmic gap. In that case iteration buys nothing statistically. We would redirect the project toward tightening one-shot proofs instead. We expect a gap at low $\rho$ because the proxy's interference terms concentrate only with spread energy. That expectation is the hypothesis being tested, not an assumption.
Why not just split the sample across iterations? Splitting makes the proof easy but scales the required sample size with the number of iterations. In shuffled regression it also breaks the global pairing, since each batch sees only part of the candidate rows. Alternating minimization for generalized rank one matrix sensing names the no-split analysis as the open goal because practitioners reuse data. Our split ablation will show how much recovery is lost at matched $n$.
Why not just run alternating minimization and skip the theory, given that it already works on real data? The Abbasi et al. results show empirical gains but give no account of when the loop converges. Zhang and Li explicitly argue that such loops get trapped in local minima. The two camps disagree, and only an analysis of the starting-point threshold as a function of $\rho$ can say which regime each observation came from. The theory's predictions are directly checkable, as described below.
Why not just sort by leverage scores or use spectral seriation? Denoising linear models with permuted data establishes leverage-score sorting only without noise. Matrix Reordering for Noisy Disordered Matrices shows spectral seriation needs signal of order $\sigma n^3$, against the $\sigma\sqrt{n\log n}$ that is information-theoretically sufficient. We include spectral sorting only as a sanity check on the synthetic data.
Proposed Experiments
We start from the synthetic Gaussian shuffled-regression setup used across the Zhang–Li papers, with $n \in \{500, 1000\}$. We set $B^* = U\,\mathrm{diag}(s)\,V^\top$ with power-law singular values $s_k = k^{-\alpha}$ at fixed $p$ and $m$. Sweeping $\alpha$ moves $\rho$ from about 1 up to $\min(p,m)$ without changing $m$, which separates the effect of stable rank from the effect of the number of responses. We vary SNR and the fraction of permuted rows up to fully dense permutations. We also repeat the sweep with uniform and heavy-tailed inputs, since Abbasi et al. report that spectral methods fail off-Gaussian. Metrics are exact-recovery probability, fraction of mismatched rows, and relative coefficient error.
The first decisive check plots the 50%-recovery SNR against $\rho$ for three methods: oracle, one-shot, and our iterated method. The gap between oracle and one-shot is the quantity the proposal is about. The iterated curve must close it.
The second check tests the proof mechanism directly. Leave-one-out trajectories are cheap to simulate, so we compute $\|B_t - B_t^{(i)}\|$ for sampled rows $i$ and verify that it stays small and scales as the analysis predicts. We also compare the empirical mismatch trajectory $h_t$ with the recursion above, in the spirit of the sharp predictions of Verchand et al.
The third check measures the starting-point threshold. We initialize at controlled mismatch fractions and record the largest fraction from which iteration still reaches the oracle error. The prediction is that this threshold increases with $\rho$.
On real data we use ames, air-qty, ftp, scm, and scs with the Abbasi et al. linked-regression protocol, reporting $R^2$ and relative error. For each dataset we also compute the stable rank of the fitted coefficients, to test whether our method's advantage over one-shot methods is concentrated in the low-$\rho$ datasets as the theory predicts.
References
- The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing From Multiple Measurement Vectors
- Optimal Estimator for Unlabeled Linear Regression
- Greed is good: correspondence recovery for unlabeled linear regression
- One-Step Estimator for Permuted Sparse Recovery
- Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
- Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization
- Alternating minimization algorithm for unlabeled sensing and linked linear regression
- Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing
- Denoising Linear Models with Permuted Data
- Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms