Error-Correction for Sparse Support Recovery Algorithms

• Published in: IEEE transactions on information theory 2022-11, Vol.68 (11), p.7396-7409
• Main Authors: Mehrabi, Mohammad, Tchamkerten, Aslan
• Format: Article
• Language: English
• Subjects: Algorithms; Compressed sensing; Computational complexity; Computer Science; Costs; Error correction; feature selection; Greedy algorithms; high dimension; Information Theory; linear model; Matched pursuit; Matching; Matching pursuit algorithms; Reconstruction algorithms; Recovery; Robustness; support recovery; Support vector machines
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2022.3188459

Consider the compressed sensing setup where the support \mathbf {s}^{\ast} of an m -sparse d -dimensional signal \mathbf {x} is to be recovered from n linear measurements with a given algorithm. Suppose that the measurements are such that the algorithm does not guarantee perfect support recovery and that true features may be missed. Can they efficiently be retrieved? We address this question through a simple error-correction module referred to as LiRE. LiRE takes as input an estimate \mathbf {s}_{\text {in}} of the true support \mathbf {s}^{\ast} , and outputs a refined support estimate \mathbf {s}_{\text {out}} . We establish sufficient conditions under which LiRE is guaranteed to recover the entire support, that is \mathbf {s}_{\text {out}}\supseteq \mathbf {s}^{\ast} . These conditions imply, for instance, that in high dimension LiRE can correct a sublinear in m number of errors made by Orthogonal Matching Pursuit (OMP). The computational complexity of LiRE is {\mathcal{O}}(m n d) . Experimental results with random Gaussian design matrices show that LiRE substantially reduces the number of measurements needed for perfect support recovery via Compressive Sampling Matching Pursuit, Basis Pursuit (BP), and OMP. Interestingly, adding LiRE to OMP yields a support recovery procedure that is more accurate and significantly faster than BP. This observation carries over in the noisy measurement setup where the combination of LiRE and OMP is faster and more accurate than LASSO. Finally, as a standalone support recovery algorithm with a random initialization, experiments show that LiRE's support recovery performance lies between OMP and BP. These results show that LiRE can be used g