Error-Correction for Sparse Support Recovery Algorithms

This article proposes LiRE, a low complexity algorithm designed to efficiently correct errors made by any given baseline compressed sensing support recovery algorithms. LiRE takes as input an estimate \mathrm{s}_{\text{in of the true support \mathrm{s}^{\ast} of an m-sparse d-dimensional signal x observed through n linear measurements, and outputs a refined support estimate \mathrm{s}_{\text{out of size m. Sufficient conditions are established in the noiseless setup under which LiRE recovers all missed true features, i.e., \mathrm{s}_{\text{out\supseteq \mathrm{s}^{\ast}. Experimental results with Gaussian design matrices show that LiRE reduces the number of measurements needed for perfect support recovery via CoSaMP, BP, and OMP by up to 15%, 25%, and 40%, respectively, depending on the level of sparsity. Interestingly, adding LiRE to OMP 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 support recovery or to operate with a smaller number of measurements, at the cost of a relatively small computational overhead. Finally, with a random initialization LiRE becomes a standalone algorithm with OMP-like complexity, and whose reconstruction performance lies between OMP and BP.