All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD4-S4-T3.3
Paper Title Sparse Recovery with Shuffled Labels: Statistical Limits and Practical Estimators
Authors hang zhang, Georgia Institute Of Technology, Georgia; Ping Li, Baidu Research, United States
Session D4-S4-T3: Sparse Recovery
Chaired Session: Thursday, 15 July, 23:00 - 23:20
Engagement Session: Thursday, 15 July, 23:20 - 23:40
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.