Orthogonal Matching Pursuit Algorithm for 1D Discrete Signal Reconstruction in Compressed Sensing

Orthogonal Matching Pursuit (OMP) is a greedy algorithm used in compressed sensing for reconstructing sparse signals. The core principle involves iteratively selecting basis vectors that exhibit maximum correlation with the current residual, progressively approximating the original signal through orthogonal projections.

The OMP algorithm operates under the assumption that signals are sparse in some transform domain (such as Fourier or wavelet bases). During each iteration, the algorithm selects the column from the measurement matrix that demonstrates the highest correlation with the current residual, adds it to the support set, and updates the signal estimate using least squares minimization. Key implementation steps include: - Correlation computation between residual and measurement matrix columns - Support set expansion with the selected atom index - Least squares solution for signal approximation on the current support - Residual update using orthogonal projection The process repeats until meeting stopping criteria (e.g., reaching preset sparsity level or achieving sufficiently small residual).

Compared to basic Matching Pursuit (MP), OMP incorporates orthogonalization of selected basis vectors at each iteration, preventing redundant selection of the same atoms and significantly improving convergence rate and reconstruction accuracy. This method is particularly effective for recovering 1D discrete signals (such as audio or sensor data) when the number of measurements is substantially smaller than the signal length, leveraging sparsity to achieve high-probability reconstruction.

Practical applications require the measurement matrix to satisfy the Restricted Isometry Property (RIP), and the relationship between signal sparsity and measurement count must meet certain conditions to guarantee reconstruction quality. Due to its simplicity and efficiency, OMP remains one of the classical algorithms in compressed sensing research, with implementations typically involving matrix operations and iterative optimization loops.