Fast Orthogonal Matching Pursuit through Successive Regression
This work addresses computational bottlenecks in sparse signal recovery methods, offering faster processing for applications like signal processing and compressed sensing, though it is incremental as it builds directly on existing OMP frameworks.
The paper tackled the computational inefficiency of Orthogonal Matching Pursuit (OMP) and its generalized version (gOMP) for sparse signal recovery by proposing fast algorithms that reduce orthogonal projection complexity, resulting in significantly reduced computation time while maintaining similar approximation error.
Orthogonal Matching Pursuit (OMP) has been a powerful method in sparse signal recovery and approximation. However, OMP suffers computational issues when the signal has a large number of non-zeros. This paper advances OMP and its extension called generalized OMP (gOMP) by offering fast algorithms for the orthogonal projection of the input signal at each iteration. The proposed modifications directly reduce the computational complexity of OMP and gOMP. Experiment results verified the improvement in computation time. This paper also provides sufficient conditions for exact signal recovery. For general signals with additive noise, the approximation error is at the same order as OMP (gOMP), but is obtained within much less time.