OMP Algorithm for Compressed Sensing: Signal Recovery via Orthogonal Matching Pursuit

This article explores the implementation of 1-D compressed sensing using the Orthogonal Matching Pursuit (OMP) algorithm. The method requires the number of measurements M to satisfy M>=K*log(N/K), where K denotes signal sparsity and N represents the signal length, facilitating near-perfect reconstruction of the original signal. The algorithm operates through iterative atom selection from the sensing matrix based on maximum correlation with the residual, followed by orthogonal projection to update coefficients. Key implementation steps include: - Initializing residual with the measurement vector - Iteratively selecting dictionary atoms maximizing inner products with residuals - Solving least-squares problems to update sparse coefficients - Computing new residuals through orthogonal projection The implementation was developed by Wei Sha from the University of Hong Kong's Department of Electrical Engineering (contact: wsha@eee.hku.hk). The reference work is "Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit" by Joel A. Tropp and Anna C. Gilbert, published in IEEE TRANSACTIONS ON INFORMATION THEORY, December 2007, Volume 53, Issue 12. This article provides comprehensive insights into the algorithm's implementation methodology and its advantages in computational efficiency and reconstruction accuracy for sparse signal recovery.