Relaxations of the optimality requirement on the thresholding greedy algorithm for bases of Banach spaces

The theory of nonlinear approximation has been motivated by vast applications such as increasing computational efficiency in processing large data sets and providing useful tools in image compression and numerical computation. For the last two decades, a topic that has attracted much attention is to evaluate the performance of approximations to a vector (signal) by nonlinear algorithms. In 1999, Koyagin and Temlyakov gave an early formalization of such an algorithm, called the Thresholding Greedy Algorithm (TGA). The TGA is adaptive to the signal $x$ to be approximated, i.e., it chooses the largest coefficients of $x$ with respect to a given basis of a Banach space. A basis is said to be greedy if an $m$-term approximation produced by the TGA is essentially the best $m$-term approximation that one can possibly obtain. While greedy bases are desirable, the greedy requirement is a strong notion, which excludes many classical Banach spaces such as \ell_p\oplus \ell_q (1\leqslant p < q \leqslant \infty), \left(\oplus_n=1^\infty \ell_pⁿ\right)_\ell1 (1 < p\leqslant\infty), \left(\oplus_n=1^\infty\ell_pⁿ\right)_c0 (1\leqslant p<\infty), and \left(\oplus \ell_p\right)_\ellq (1\leqslant p\neq q < \infty). In 2003, Dilworth, Kalton, Kutzarova, and Temlyakov introduced the almost greedy property, which is slightly weaker but much more common than the greedy property. In particular, a basis is said to be almost greedy if the TGA gives essentially the best $m$-term projection as an approximation. Our first goal is to loosen the greedy requirement to study greedy properties of more bases. We introduce a family of functions $\mathcal{G}$, which includes functions like cx^γ, where c,γ\in (0, 1), and define a basis to be $f$-greedy if an $m$-term approximation by the TGA gives essentially the best $f(m)$-term approximation. Correspondingly, we have the $f$-almost greedy property. We characterize $f$-(almost) greedy bases, give examples, and prove the unexpected equivalence: for a non-identity function $f$, a basis is $f$-greedy if and only if it is $f$-almost greedy. We then move on to investigate the relation between the so-called Property (A) and the $1$-greedy property. Here a basis is $1$-greedy if the distance between a vector $x$ and an $m$-term approximation by the TGA is at most the distance between $x$ and any $m$-term linear combination of basis vectors. For the $1$-almost greedy property, we replace linear combinations by projections. In 2017, Albiac and Ansorena showed that Property (A) is equivalent to the $1$-almost greedy property and asked for a stronger result: whether Property (A) is equivalent to the $1$-greedy property. We answer this question negatively by giving a renorming of \ell₁ such that the canonical basis has Property (A) but is not $1$-greedy. Finally, we study the consecutive (almost) greedy property, where the linear combinations and projections only involve basis vectors with consecutive indices. We show that a basis is almost greedy if and only if it is consecutive almost greedy. This is a rather surprising result since the order-independent notion of being almost greedy can be characterized by an order-dependent property. However, we do not have such an equivalence in the greedy case. Specifically, a consecutive greedy basis does not necessarily possess unconditionality, a consequence of being greedy. In the same theme, we give a new characterization of the so-called partially greedy bases.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Chu, Hung Viet

Contributors dc:contributor

• Oikhberg, Timur
• Berná, Pablo M
• Kutzarova, Denka
• Boca, Florin

• Thresholding Greedy Algorithm
• Optimality

Statement dc:rights

• Copyright 2023 Hung Viet Chu

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/120234

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F120234