Sparse Recovery with Shuffled Labels: Statistical Limits and Practical Estimators

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.