On the optimality of the Orthogonal Greedy Algorithm for μ-coherent dictionaries

被引：13

作者：

Livshitz, E. D. ^{[1
]}

机构：

[1] Moscow MV Lomonosov State Univ, Moscow 119992, Russia

来源：

JOURNAL OF APPROXIMATION THEORY | 2012年 / 164卷 / 05期

基金：

俄罗斯基础研究基金会;

关键词：

Orthogonal Greedy Algorithms; Orthogonal Matching Pursuit; Best m-term approximation; Lebesgue-type inequalities; CONSTRUCTIONS;

D O I：

10.1016/j.jat.2012.01.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this article, we continue to study the performance of Greedy Algorithms. We show that the Orthogonal Greedy Algorithm (Orthogonal Matching Pursuit) provides an almost optimal approximation on the first [mu(-1)/20] steps for mu-coherent dictionaries. (C) 2012 Elsevier Inc. All rights reserved.

引用

页码：668 / 681

页数：14

共 11 条

[1] SIMPLE CONSTRUCTIONS OF ALMOST K-WISE INDEPENDENT RANDOM-VARIABLES [J].

ALON, N ;

GOLDREICH, O ;

HASTAD, J ;

PERALTA, R .

RANDOM STRUCTURES & ALGORITHMS, 1992, 3 (03) :289-304

[2] Deterministic constructions of compressed sensing matrices [J].

DeVore, Ronald A. .

JOURNAL OF COMPLEXITY, 2007, 23 (4-6) :918-925

[3] On Lebesgue-type inequalities for greedy approximation [J].

Donoho, D. L. ;

Elad, M. ;

Temlyakov, V. N. .

JOURNAL OF APPROXIMATION THEORY, 2007, 147 (02) :185-195

[4] Stable recovery of sparse overcomplete representations in the presence of noise [J].

Donoho, DL ;

Elad, M ;

Temlyakov, VN .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (01) :6-18

[5]

Gilbert AC, 2003, SIAM PROC S, P243

[6]

Gribonval R., 2004, P INT C IND COMP ANA

[7]

Kashin B.S., 1975, Usp. Mat. Nauk, V30, P251

[8]

Livshits ED, 2010, MATH NOTES+, V87, P774, DOI [10.1134/S0001434610050159, 10.4213/mzm8722]

[9] On the size of incoherent systems [J].

Nelson, J. L. ;

Temlyakov, V. N. .

JOURNAL OF APPROXIMATION THEORY, 2011, 163 (09) :1238-1245

[10] On performance of greedy algorithms [J].

Temlyakov, Vladimir N. ;

Zheltov, Pavel .

JOURNAL OF APPROXIMATION THEORY, 2011, 163 (09) :1134-1145

← 1 2 →