TY - GEN

T1 - Sparse Recovery with Shuffled Labels

T2 - 2021 IEEE International Symposium on Information Theory, ISIT 2021

AU - Zhang, Hang

AU - Li, Ping

N1 - Publisher Copyright:
© 2021 IEEE.

PY - 2021/7/12

Y1 - 2021/7/12

N2 - This paper considers the sparse recovery with ner-muted labels, i.e., \boldsymbol{y}={\Pi}^{\ast}\boldsymbol{X}{\beta}^{\ast}+\boldsymbol{w} where \boldsymbol{y} \in \mathbb{R}^{n}, \mathbf{\Pi} \in \mathbb{R}^{n \times n}, \boldsymbol{X} \in \mathbb{R}^{n \times p}, {\beta}^{\ast} \in \mathbb{R}^{p}, \boldsymbol{w} \in \mathbb{R}^{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 signal-to-noise ratio (SNR) for the correct recovery of the permutation matrix and the support set \text{supp}({\beta}^{\ast}), more specifically n \gtrsim k \log p and \log (\text{SNR}) \gtrsim \log n+\frac{k \log p}{n}. Then we confirm the tightness of these bounds by giving an exhaustive-search based estimators with matching orders. For the computational aspect, we propose a computationally-efficient estimator, 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.

AB - This paper considers the sparse recovery with ner-muted labels, i.e., \boldsymbol{y}={\Pi}^{\ast}\boldsymbol{X}{\beta}^{\ast}+\boldsymbol{w} where \boldsymbol{y} \in \mathbb{R}^{n}, \mathbf{\Pi} \in \mathbb{R}^{n \times n}, \boldsymbol{X} \in \mathbb{R}^{n \times p}, {\beta}^{\ast} \in \mathbb{R}^{p}, \boldsymbol{w} \in \mathbb{R}^{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 signal-to-noise ratio (SNR) for the correct recovery of the permutation matrix and the support set \text{supp}({\beta}^{\ast}), more specifically n \gtrsim k \log p and \log (\text{SNR}) \gtrsim \log n+\frac{k \log p}{n}. Then we confirm the tightness of these bounds by giving an exhaustive-search based estimators with matching orders. For the computational aspect, we propose a computationally-efficient estimator, 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.

UR - http://www.scopus.com/inward/record.url?scp=85115103994&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115103994&partnerID=8YFLogxK

U2 - 10.1109/ISIT45174.2021.9517866

DO - 10.1109/ISIT45174.2021.9517866

M3 - Conference contribution

AN - SCOPUS:85115103994

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1760

EP - 1765

BT - 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 12 July 2021 through 20 July 2021

ER -