Super greedy type algorithms and applications in compressed sensing

In this manuscript we study greedy-type algorithms such that at a greedy step we pick several dictionary elements contrary to a single dictionary element in standard greedy-type algorithms. We call such greedy algorithms super greedy type algorithms. In the general setting, we propose several new greedy algorithms which are Super Greedy Algorithm (SGA), Orthogonal Super Greedy Algorithm (OSGA), and Orthogonal Super Greedy Algorithm with Thresholding (OSGAT) as well as their weak versions. The central question to be studied is what, if any, are the advantages of super greedy type algorithms over the standard greedy type algorithms. This question is answered by studying their performance (rate of convergence) under M-coherent dictionaries. Some new phenomena are found. For instance, Orthogonal Super Greedy Algorithm has the same convergence rate compared to Orthogonal Greedy Algorithm (OGA) with respect to incoherent dictionaries. However, OSGA is computationally simpler than the standard Orthogonal Greedy Algorithm. The greedy approximation is already in serious numerical use, such as image/video processing, solution of operator equations, and etc. For instance, greedy approximation serves as one of the fundamental tools in sparse signal recovery. Using the super-greedy idea, we build new recovery algorithms in Compressed Sensing (CS) which are Orthogonal Multi Matching Pursuit (OMMP) and Orthogonal Multi Matching Pursuit with Thresholding Pruning (OMMPTP). The performances of there two algorithms are analyzed under Restricted Isometry Property (RIP) conditions.