On A Class of Greedy Sparse Recovery Algorithms
This work addresses sparse signal recovery, a key problem in signal processing and machine learning, by introducing incremental improvements to greedy algorithms for better accuracy and robustness.
The authors tackled sparse signal recovery by proposing a novel greedy approach that directly works in the solution space, leading to algorithms that significantly outperform classical methods like OMP and BP in recovery accuracy while maintaining similar computational complexity, with extensive simulations showing superior performance in accuracy and robustness.
Sparse signal recovery deals with finding the sparsest solution of an under-determined linear system $\vx = \mQ\vs$. In this paper, we propose a novel greedy approach to addressing the challenges from such a problem. Such an approach is based on a characterization of solutions to the system, which allows us to work on the sparse recovery in the $\vs$-space directly with a given measure. With $l_2$-based measure, an orthogonal matching pursuit (OMP)-type algorithm is proposed, which significantly outperforms the classical OMP algorithm in terms of recovery accuracy while maintaining comparable computational complexity. An $l_1$-based algorithm, denoted as $\text{Alg}_{GL1}$, is derived. Such an algorithm significantly outperforms the classical basis pursuit (BP) algorithm. Combining with the CoSaMP-strategy for selecting atoms, a class of high performance greedy algorithms is also derived. Extensive numerical simulations on both synthetic and image data are carried out, with which the superior performance of our proposed algorithms is demonstrated in terms of sparse recovery accuracy and robustness against numerical instability of the system matrix $\mQ$ and disturbance in the measurement $\vx$.