The paper presents a fully data-driven version of the Orthogonal Matching Pursuit (OMP) algorithm for recovering the support of a sparse signal from noisy linear measurements. The OMP algorithm is an iterative greedy method that selects at each step the column of the measurement matrix most correlated with the current residual. The algorithm is equipped with explicit stopping rules to determine when to terminate. Under the mutual incoherence condition and a minimum magnitude condition on the nonzero components of the signal, the OMP algorithm can recover the exact support of the signal with high probability.
The paper also considers the problem of identifying significant components in the presence of small nonzero components. It shows that the OMP algorithm can select all significant components before possibly selecting incorrect ones. With modified stopping rules, the algorithm can ensure that no zero components are selected.
The paper compares the performance of OMP with other methods, such as $\ell_1$ minimization, and shows that OMP has a weaker condition on the minimum magnitude of the nonzero components. This, combined with its computational simplicity, makes OMP an appealing method for support recovery. The results are presented under both bounded noise and Gaussian noise cases. In the Gaussian noise case, the algorithm is shown to recover the true support with high probability under certain conditions. The paper also discusses the theoretical foundations of the OMP algorithm, including its stopping rules and properties, and provides proofs for the main results. The analysis shows that OMP is effective in recovering the support of a sparse signal under various noise conditions.The paper presents a fully data-driven version of the Orthogonal Matching Pursuit (OMP) algorithm for recovering the support of a sparse signal from noisy linear measurements. The OMP algorithm is an iterative greedy method that selects at each step the column of the measurement matrix most correlated with the current residual. The algorithm is equipped with explicit stopping rules to determine when to terminate. Under the mutual incoherence condition and a minimum magnitude condition on the nonzero components of the signal, the OMP algorithm can recover the exact support of the signal with high probability.
The paper also considers the problem of identifying significant components in the presence of small nonzero components. It shows that the OMP algorithm can select all significant components before possibly selecting incorrect ones. With modified stopping rules, the algorithm can ensure that no zero components are selected.
The paper compares the performance of OMP with other methods, such as $\ell_1$ minimization, and shows that OMP has a weaker condition on the minimum magnitude of the nonzero components. This, combined with its computational simplicity, makes OMP an appealing method for support recovery. The results are presented under both bounded noise and Gaussian noise cases. In the Gaussian noise case, the algorithm is shown to recover the true support with high probability under certain conditions. The paper also discusses the theoretical foundations of the OMP algorithm, including its stopping rules and properties, and provides proofs for the main results. The analysis shows that OMP is effective in recovering the support of a sparse signal under various noise conditions.