| Abstract |
This paper considers the sparse recovery with permuted labels, i.e., $\by = \bPi^{\natural} \bX \bbeta^{\natural} + \bw$, where $\by \in \RR^n$, $\bPi\in \RR^{n\times n}$, $\bX\in \RR^{n\times p}$, $\bbeta^{\natural}\in \RR^p$, $\bw \in \RR^n$ denote the sensing result, unknown permutation matrix, design matrix, $k$-sparse covariates, and additive noise, respectively. The investigation is performed from both the statistical and the computational perspectives. For the statistical aspect, we first establish the statistical lower bounds on the measurement number $n$ and the \emph{signal-to-noise ratio} ($\mathsf{SNR}$) for the correct recovery of the permutation matrix and the support set $\mathsf{supp}(\bbeta^{\natural})$, more specifically, $n \gtrsim k\log p$ and $\log(\mathsf{SNR}) \gtrsim \log n + \frac{k\log p}{n}$. Then we confirm the tightness of these bounds by giving a exhaustive-search based estimators with matching orders. For the computational aspect, we propose a computationally-efficient estimators, namely, M-Lasso to recover both the permutation matrix and the sparse covariates. Numerical experiments are provided to verify the correctness and efficiency of the proposed estimator.
|
