On performance of greedy algorithms

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 m=12(M−1+1) by proving a Lebesgue-type inequality for arbitrary signals. Additionally, we present a dictionary with coherence MM and a 12(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 m−12.