Dynamic Orthogonal Matching Pursuit for Signal Reconstruction

Orthogonal matching pursuit (OMP) is one of the mainstream algorithms for signal reconstruction/approximation. It plays a vital role in the development of compressed sensing theory, and it also acts as a driving force for the development of other heuristic methods for signal reconstruction. In this paper, we propose the so-called dynamic orthogonal matching pursuit (DOMP) and its two enhanced versions which are more efficient than OMP in signal reconstruction from a numerical point of view, and we provide a rigorous analysis for these algorithms in terms of the restricted isometry property (RIP) of the sensing matrix. The main result claims that the reconstruction error via the proposed algorithms can be controlled and measured with the number of iterations, sparsity level of the signal and the noise level of the measurements. The analysis in this paper sufficiently exploits the structure of the DOMP and an auxiliary convex optimization model (called approximation counterpart) to establish a mild RIP-based performance result for DOMP and its enhanced versions. Dramatically different from existing results for OMP-like algorithms, the results established for the algorithms proposed in this paper do not need any traditional assumptions imposed on the smallest nonzero element of the target signal which is unknown before being actually reconstructed. Moveover, the finite convergence of the algorithms for a class of large-scale compressed sensing problems is also discussed.