On performance of greedy algorithms Original Research Article

We show that the Orthogonal Greedy Algorithm (OGA) for dictionaries in a Hilbert space with small coherence MM performs almost as well as the best mm-term approximation for all signals with sparsity close to the best theoretically possible threshold View the MathML sourcem=12(M−1+1) by proving a Lebesgue-type inequality for arbitrary signals. Additionally, we present a dictionary with coherence MM and a View the MathML source12(M−1+1)-sparse signal for which OGA fails to pick up any atoms from the support, showing that the above threshold is sharp. We also show that the Pure Greedy Algorithm (PGA) matches the rate of convergence of the best mm-term approximation beyond the saturation limit of View the MathML sourcem−12.