On performance of greedy algorithms

JOURNAL OF APPROXIMATION THEORY

卷:163

Article

Temlyakov, Vladimir N.¹  Zheltov, Pavel¹ 

[1] Univ S Carolina, Dept Math, Columbia, SC 29208 USA

关键词: Additive-type Lebesgue inequality;    Greedy algorithm;    Orthogonal matching pursuit;    m-term approximation;    Incoherent dictionary;    Coherence;    Orthogonal greedy algorithm;    Sparse representation;   

DOI  :  10.1016/j.jat.2011.03.009

来源: Elsevier

【 摘 要 】

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.

【 授权许可】

Free