[edit]
One-Step Estimator for Permuted Sparse Recovery
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:41244-41267, 2023.
Abstract
This paper considers the unlabeled sparse recovery under multiple measurements, i.e., Y=Π♮XB♮+W, where Y∈Rn×m,Π♮∈Rn×n,X∈Rn×p,B♮∈Rp×m,W∈Rn×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 signal-to-noise ratio (SNR) for the correct permutation recovery. Moreover, 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.