# Sparse Recovery with Shuffled Labels: Statistical Limits and Practical Estimators

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 20 Mar 2023.

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

- [Outlier-robust estimation of a sparse linear model using ℓ1-penalized Huber's M-estimator](https://mlsanity.com/paper/1904.06288/) (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)
- [A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data](https://mlsanity.com/paper/1907.07148/) (2019)
- [Signal Recovery from Unlabeled Samples](https://mlsanity.com/paper/1701.08701/) (2017)
- [The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing from Multiple Measurement Vectors](https://mlsanity.com/paper/1909.02496/) (2019)
- [Regression with Label Permutation in Generalized Linear Model](https://mlsanity.com/paper/2206.11775/) (2022)

## Abstract (arXiv)

This paper considers the sparse recovery with shuffled labels, i.e., by = bPitrue bX bbetatrue + bw, where by ∈ RRn, bPi∈ RRn× n, bX∈ RRn× p, bbetatrue∈ RRp, bw ∈ RRn denote the sensing result, the unknown permutation matrix, the design matrix, the sparse signal, and the additive noise, respectively. Our goal is to reconstruct both the permutation matrix bPitrue and the sparse signal bbetatrue. We investigate this problem from both the statistical and computational aspects. From the statistical aspect, we first establish the minimax lower bounds on the sample number n and the signal-to-noise ratio (snr) for the correct recovery of permutation matrix bPitrue and the support set supp(bbetatrue), to be more specific, n gtrsim klog p and logsnr gtrsim log n + fracklog pn. Then, we confirm the tightness of these minimax lower bounds by presenting an exhaustive-search based estimator whose performance matches the lower bounds thereof up to some multiplicative constants. From the computational aspect, we impose a parsimonious assumption on the number of permuted rows and propose a computationally-efficient estimator accordingly. Moreover, we show that our proposed estimator can obtain the ground-truth (bPitrue, supp(bbetatrue)) under mild conditions. Furthermore, we provide numerical experiments to corroborate our claims.