# Optimal Estimator for Linear Regression with Shuffled Labels

arXiv: https://arxiv.org/abs/2310.01326 · HTML: https://mlsanity.com/paper/2310.01326/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 38 references that are in the map.
- First posted on arXiv 2 Oct 2023.

## Builds on (most cited first, 15 of 15)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Linear Regression with Sparsely Permuted Data](https://mlsanity.com/paper/1710.06030/) (2017)
- [Linear regression without correspondence](https://mlsanity.com/paper/1705.07048/) (2017)
- [The Likelihood Ratio Test in High-Dimensional Logistic Regression Is Asymptotically a Rescaled Chi-Square](https://mlsanity.com/paper/1706.01191/) (2017)
- [A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data](https://mlsanity.com/paper/1907.07148/) (2019)
- [Denoising Linear Models with Permuted Data](https://mlsanity.com/paper/1704.07461/) (2017)
- [Linear Regression with Shuffled Labels](https://mlsanity.com/paper/1705.01342/) (2017)
- [Signal Recovery from Unlabeled Samples](https://mlsanity.com/paper/1701.08701/) (2017)
- [Permutations Unlabeled beyond Sampling Unknown](https://mlsanity.com/paper/1812.00498/) (2018)
- [Low-rank Matrix Recovery With Unknown Correspondence](https://mlsanity.com/paper/2110.07959/) (2021)
- [Permuted and Unlinked Monotone Regression in ℝd: an approach based on mixture modeling and optimal transport](https://mlsanity.com/paper/2201.03528/) (2022)
- [Regression with Label Permutation in Generalized Linear Model](https://mlsanity.com/paper/2206.11775/) (2022)

## Abstract (arXiv)

This paper considers the task of linear regression with shuffled labels, i.e., mathbf Y = mathbf Pi mathbf X mathbf B + mathbf W, where mathbf Y ∈ mathbb Rn× m, mathbf Pi ∈ mathbb Rn× n, mathbf X∈ mathbb Rn× p, mathbf B ∈ mathbb Rp× m, and mathbf W∈ mathbb Rn× m, respectively, represent the sensing results, (unknown or missing) corresponding information, sensing matrix, signal of interest, and additive sensing noise. Given the observation mathbf Y and sensing matrix mathbf X, we propose a one-step estimator to reconstruct (mathbf Pi, mathbf B). From the computational perspective, our estimator's complexity is O(n3 + np2m), which is no greater than the maximum complexity of a linear assignment algorithm (e.g., O(n3)) and a least square algorithm (e.g., O(np2 m)). From the statistical perspective, we divide the minimum snr requirement into four regimes, e.g., unknown, hard, medium, and easy regimes; and present sufficient conditions for the correct permutation recovery under each regime: (i) snr ≥ Omega(1) in the easy regime; (ii) snr ≥ Omega(log n) in the medium regime; and (iii) snr ≥ Omega((log n)c0· n^c1/srank(mathbf B)) in the hard regime (c0, c1 are some positive constants and srank(mathbf B) denotes the stable rank of mathbf B). In the end, we also provide numerical experiments to confirm the above claims.