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

Chu, Hung Viet

Permalink

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

Description

Title

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

Author(s)

Chu, Hung Viet

Issue Date

2023-04-07

Director of Research (if dissertation) or Advisor (if thesis)

• Oikhberg, Timur
• Berná, Pablo M

Doctoral Committee Chair(s)

Kutzarova, Denka

Committee Member(s)

Boca, Florin

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Thresholding Greedy Algorithm
• Optimality

Abstract

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^n\right)_{\ell_1} (1 < p\leqslant\infty)$, $\left(\oplus_{n=1}^\infty\ell_p^n\right)_{c_0} (1\leqslant p<\infty)$, and $\left(\oplus \ell_p\right)_{\ell_q} (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^{\gamma}$, where $c,\gamma\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_1$ 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.

Graduation Semester

2023-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Hung Viet Chu

Owning Collections