Optimal Estimator for Linear Regression with Shuffled Labels

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.