Tuning Free Orthogonal Matching Pursuit
This addresses the practical limitation in compressive sensing and robust regression where tuning parameters are often unavailable, though it is incremental as it modifies existing algorithms.
The paper tackles the problem of sparse signal recovery in noisy linear regression by developing tuning-free versions of Orthogonal Matching Pursuit (TF-OMP) and Greedy Algorithm for Robust De-noising (TF-GARD), which eliminate the need for prior knowledge of sparsity or noise variance. Results show TF-OMP performs competitively with OMP using such knowledge, and TF-GARD achieves comparable performance to GARD.
Orthogonal matching pursuit (OMP) is a widely used compressive sensing (CS) algorithm for recovering sparse signals in noisy linear regression models. The performance of OMP depends on its stopping criteria (SC). SC for OMP discussed in literature typically assumes knowledge of either the sparsity of the signal to be estimated $k_0$ or noise variance $σ^2$, both of which are unavailable in many practical applications. In this article we develop a modified version of OMP called tuning free OMP or TF-OMP which does not require a SC. TF-OMP is proved to accomplish successful sparse recovery under the usual assumptions on restricted isometry constants (RIC) and mutual coherence of design matrix. TF-OMP is numerically shown to deliver a highly competitive performance in comparison with OMP having \textit{a priori} knowledge of $k_0$ or $σ^2$. Greedy algorithm for robust de-noising (GARD) is an OMP like algorithm proposed for efficient estimation in classical overdetermined linear regression models corrupted by sparse outliers. However, GARD requires the knowledge of inlier noise variance which is difficult to estimate. We also produce a tuning free algorithm (TF-GARD) for efficient estimation in the presence of sparse outliers by extending the operating principle of TF-OMP to GARD. TF-GARD is numerically shown to achieve a performance comparable to that of the existing implementation of GARD.