One-Step Estimator for Permuted Sparse Recovery

This paper considers the unlabeled sparse recovery under multiple measurements, i.e., Y = , W 2 R n⇥m represents the observations, missing (or incomplete) correspondence information, sensing matrix, sparse signals, and additive sensing noise, respectively. Different from the previous works on multiple measurements (m > 1) which all focus on the sufficient samples regime, namely, n > p, we consider a sparse matrix B and investigate the insufficient samples regime (i.e., n ⌧ p) for the first time. To begin with, we establish the lower bound on the sample number and signalto-noise ratio (SNR) for the correct permutation recovery. Then, we present a simple yet effective estimator. Under mild conditions, we show that our estimator can restore the correct correspondence information with high probability. Numerical experiments are presented to corroborate our theoretical claims.