TY - JOUR ID - 1605 TI - A Sharp Sufficient Condition for Sparsity Pattern Recovery JO - Journal of AI and Data Mining JA - JADM LA - en SN - 2322-5211 AU - Shaeiri, Z. AU - Karami, M. R. AU - Aghagolzadeh, A. AD - Department of Electrical and Computer Engineering, Babol Noshirvani University of Technology, Babol, Iran. Y1 - 2020 PY - 2020 VL - 8 IS - 1 SP - 13 EP - 23 KW - Sparsity Pattern Recovery KW - Information-Theoretic Limits KW - Joint-Typicality Decoder KW - Compressed Sensing DO - 10.22044/jadm.2019.6908.1810 N2 - Sufficient number of linear and noisy measurements for exact and approximate sparsity pattern/support set recovery in the high dimensional setting is derived. Although this problem as been addressed in the recent literature, there is still considerable gaps between those results and the exact limits of the perfect support set recovery. To reduce this gap, in this paper, the sufficient condition is enhanced. A specific form of a Joint Typicality decoder is used for the support recovery task. Two performance metrics are considered for the recovery validation; one, which considers exact support recovery, and the other which seeks partial support recovery. First, an upper bound is obtained on the error probability of the sparsity pattern recovery. Next, using the mentioned upper bound, sufficient number of measurements for reliable support recovery is derived. It is shown that the sufficient condition for reliable support recovery depends on three key parameters of the problem; the noise variance, the minimum nonzero entry of the unknown sparse vector and the sparsity level. Simulations are performed for different sparsity rate, different noise variances, and different distortion levels. The results show that for all the mentioned cases the proposed methodology increases convergence rate of upper bound of the error probability of support recovery significantly which leads to a lower error probability bound compared with previously proposed bounds. UR - https://jad.shahroodut.ac.ir/article_1605.html L1 - https://jad.shahroodut.ac.ir/article_1605_e950e1a27358f8e45517a579eac3ed42.pdf ER -