On performance of greedy algorithms

We show that the Orthogonal Greedy Algorithm (OGA) for dictionaries in a Hilbert space with small coherence M performs almost as well as the best m-term approximation for all signals with sparsity close to the best theoretically possible threshold m = 1/2(M(-1) + 1) by proving a Lebesgue-type inequality for arbitrary signals. Additionally, we present a dictionary with coherence M and a 1/2(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 m-term approximation beyond the saturation limit of m(-1/2). (C) 2011 Elsevier Inc. All rights reserved.