Greedy algorithm with gaps

T. Oikhberg

doi:10.1016/j.jat.2017.10.006

Greedy algorithm with gaps

T. Oikhberg

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

We generalize the well-known greedy approximation algorithm, by allowing gaps in the approximating sequence. We give examples of bases which are “quasi-greedy with gaps,” in spite of failing to be quasi-greedy in the usual sense. However, we also show that for some classical bases (such as the normalized Haar basis in L₁, and the trigonometric basis in L_p for p≠2), the greedy algorithm may diverge, even if gaps are introduced into the approximating sequence.

Original language	English (US)
Pages (from-to)	176-190
Number of pages	15
Journal	Journal of Approximation Theory
Volume	225
DOIs	https://doi.org/10.1016/j.jat.2017.10.006
State	Published - Jan 2018

Keywords

Basis
Greedy algorithm

ASJC Scopus subject areas

Analysis
Numerical Analysis
General Mathematics
Applied Mathematics

Online availability

10.1016/j.jat.2017.10.006

Library availability

Discover UIUC Full Text

Cite this

@article{ac63170c8a2c41de87238ca3b19eed3e,

title = "Greedy algorithm with gaps",

abstract = "We generalize the well-known greedy approximation algorithm, by allowing gaps in the approximating sequence. We give examples of bases which are “quasi-greedy with gaps,” in spite of failing to be quasi-greedy in the usual sense. However, we also show that for some classical bases (such as the normalized Haar basis in L1, and the trigonometric basis in Lp for p≠2), the greedy algorithm may diverge, even if gaps are introduced into the approximating sequence.",

keywords = "Basis, Greedy algorithm",

author = "T. Oikhberg",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier Inc.",

year = "2018",

month = jan,

doi = "10.1016/j.jat.2017.10.006",

language = "English (US)",

volume = "225",

pages = "176--190",

journal = "Journal of Approximation Theory",

issn = "0021-9045",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Greedy algorithm with gaps

AU - Oikhberg, T.

PY - 2018/1

Y1 - 2018/1

N2 - We generalize the well-known greedy approximation algorithm, by allowing gaps in the approximating sequence. We give examples of bases which are “quasi-greedy with gaps,” in spite of failing to be quasi-greedy in the usual sense. However, we also show that for some classical bases (such as the normalized Haar basis in L1, and the trigonometric basis in Lp for p≠2), the greedy algorithm may diverge, even if gaps are introduced into the approximating sequence.

AB - We generalize the well-known greedy approximation algorithm, by allowing gaps in the approximating sequence. We give examples of bases which are “quasi-greedy with gaps,” in spite of failing to be quasi-greedy in the usual sense. However, we also show that for some classical bases (such as the normalized Haar basis in L1, and the trigonometric basis in Lp for p≠2), the greedy algorithm may diverge, even if gaps are introduced into the approximating sequence.

KW - Basis

KW - Greedy algorithm

UR - http://www.scopus.com/inward/record.url?scp=85033583445&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85033583445&partnerID=8YFLogxK

U2 - 10.1016/j.jat.2017.10.006

DO - 10.1016/j.jat.2017.10.006

M3 - Article

AN - SCOPUS:85033583445

SN - 0021-9045

VL - 225

SP - 176

EP - 190

JO - Journal of Approximation Theory

JF - Journal of Approximation Theory

ER -

Greedy algorithm with gaps

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this