| Paper ID | D4-S4-T3.2 |
| Paper Title |
Error-Correction for Sparse Support Recovery Algorithms |
| Authors |
Mohammad Mehrabi, University of Southern California, United States; Aslan Tchamkerten, Institut Polytechnique de Paris, France |
| 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 article proposes LiRE, an algorithm designed to efficiently correct errors made by any given baseline compressed sensing support recovery algorithms. LiRE takes as input an estimate s_{in} of the true support s^* of an m-sparse d-dimensional signal x observed through n linear measurements and outputs a refined support estimate s_{out} of size m. Sufficient conditions are established in the noiseless setup under which LiRE recovers all missed true features, that is s_{out} contains s^*. Experimental results with Gaussian design matrices show that LiRE reduces the number of measurements needed for perfect support recovery via Compressive Sampling Matching Pursuit, Basis Pursuit, and Orthogonal Matching Pursuit by up to 15%, 25%, and 40%, respectively, depending on the level of sparsity. Interestingly, adding LiRE to Orthogonal Matching Pursuit yields a support recovery algorithm that is more accurate and significantly faster than Basis Pursuit. This conclusion carries over in the noisy measurement setup with the combination of LiRE and OMP against LASSO. These results suggest that LiRE may be used generically, on top of any baseline support recovery algorithm, to boost the percentage of support recovery or to operate with a smaller number of measurements, at the cost of a relatively small computational overhead.
|
