| Sbornik: Mathematics |
|
|
|
|
|
Rate of convergence of Thresholding Greedy Algorithms V. N. Temlyakovabcd a Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia b Lomonosov Moscow State University, Moscow, Russia c Moscow Center of Fundamental and Applied Mathematics, Moscow, Russia d University of South Carolina, Columbia, SC, USA
Bibliographic databases:
     § 1. IntroductionThis paper is a follow-up to the very recent paper [14], where we found the rate of convergence of some standard greedy algorithms with respect to arbitrary dictionaries. The new ingredient of [14] was that we bounded the error of approximation by the product of both the norm of $f$ and the $A_1$-norm of $f$. Typically, only the $A_1$-norm of $f$ is used. In this paper we focus on a special class of dictionaries, namely, on various types of bases — greedy bases, unconditional bases, and quasi-greedy bases. We study the rate of convergence of the classical Thresholding Greedy Algorithm with respect to bases in the style of [14]. We consider here approximation in uniformly smooth real Banach spaces. For a Banach space $X$ we define the modulus of smoothness by
$$
\begin{equation*}
\rho(u):=\rho(u,X):=\sup_{\|x\|=\|y\|=1}\biggl(\frac{1}{2}(\|x+uy\|+\|x-uy\|)-1\biggr).
\end{equation*}
\notag
$$
A uniformly smooth Banach space is one with the property We consider here the case $X=L_p$. Let $\Omega$ be a compact subset of $\mathbb{R}^d$ with a probability measure $\mu$. By the $L_p$-norm, $1\leqslant p< \infty$, of a function defined on $\Omega$ we understand
$$
\begin{equation*}
\|f\|_p:=\|f\|_{L_p(\Omega,\mu)}:=\biggl(\int_\Omega |f|^p\,d\mu\biggr)^{1/p}.
\end{equation*}
\notag
$$
By the $L_\infty$-norm we understand the uniform norm of continuous functions:
$$
\begin{equation*}
\|f\|_\infty:=\max_{\mathbf x\in\Omega} |f(\mathbf x)|
\end{equation*}
\notag
$$
and with a slight abuse of notation we write sometimes $L_\infty(\Omega)$ for the space $\mathcal{C}(\Omega)$ of continuous functions on $\Omega$. It is well known (see, for instance, [3], Lemma B.1) that in the case $X=L_p$, $1\leqslant p < \infty$, we have
$$
\begin{equation}
\rho(u,L_p) \leqslant \begin{cases} \dfrac{u^p}{p} & \text{if } 1\leqslant p\leqslant 2, \\ \dfrac{(p-1)u^2}2 & \text{if } 2\leqslant p<\infty. \end{cases}
\end{equation}
\tag{1.1}
$$
We say that a set $\mathcal{D}$ of elements (functions) from $X$ is a dictionary if each $g\in \mathcal{D}$ has a norm bounded by one ($\|g\|\leqslant 1$) and $\operatorname{\overline{span}} \mathcal{D} =X$. We define the best $m$-term approximation with regard to $\mathcal{D}$ as follows:
$$
\begin{equation*}
\sigma_m(f):=\sigma_m(f,\mathcal D)_X:=\inf_{g_1,\dots,g_m} \inf_{c_k} \biggl\|f -\sum_{k=1}^m c_kg_k\biggr\|_X,
\end{equation*}
\notag
$$
where the infimum is taken over the coefficients $c_k$ and the sets of $m$ elements $g_1,\dots,g_m$, $g_i\in\mathcal{D}$, $i=1,\dots,m$. Let $\mathcal{D}^\pm := \{\pm g\colon g\in \mathcal{D}\}$. We denote the closure of the convex hull of $\mathcal{D}^\pm$ by $A_1(\mathcal{D})$. With $f\in X$ we associate the following norm:
$$
\begin{equation*}
\|f\|_{A_1(\mathcal D)}:=\inf \biggl\{M\colon \frac fM\in A_1(\mathcal D)\biggr\}.
\end{equation*}
\notag
$$
Clearly, $\|f\|_X\leqslant \|f\|_{A_1(\mathcal{D})}$. The following result is a corollary of known results on greedy approximation (see [14], Remark 3.2). Proposition 1.1. Let $X$ be a uniformly smooth Banach space such that ${\rho(u,X) \leqslant \gamma u^q}$, $1<q\leqslant 2$. Then for any dictionary $\mathcal{D}$ and any $\alpha \in [0,1]$ we have for all $f\in X$ such that $\|f\|_{A_1(\mathcal{D})}<\infty$, $f\neq0$. Set $p^* := \min(p,2)$. Then Proposition 1.1 and relation (1.1) imply the following corollary. Corollary 1.1. Let $1<p<\infty$. Then for any dictionary $\mathcal{D}\subset L_p(\Omega,\mu)$ and any $\alpha \in [0,1]$ we have for all $f\in L_p(\Omega,\mu)$ such that $\|f\|_{A_1(\mathcal{D})} <\infty$, $f\neq 0$. Let a Banach space $X$ with (Schauder) basis $\Psi=\{\psi_k\}_{k=1}^\infty$, be given. We assume that $0<c_0\leqslant \|\psi_k\|_X\leqslant 1$, $k=1,2,\dots$, and consider the following theoretical greedy algorithm. Given an element $f\in X$, we consider the expansion For an element $f\in X$ we say that a permutation $\varrho$ of the positive integers is decreasing if
$$
\begin{equation}
|c_{k_1}(f,\Psi) |\geqslant |c_{k_2}(f,\Psi) | \geqslant \dotsb,
\end{equation}
\tag{1.5}
$$
where $\varrho(j)=k_j$, $j=1,2,\dots$, and we write $\varrho \in D(f)$. If the inequalities in (1.5) are strict, then $D(f)$ consists of only one permutation. We define the $m$th greedy approximant of $f$ with regard to the basis $\Psi$ corresponding to a permutation ${\varrho \in D(f)}$, by the formula
$$
\begin{equation*}
G_m(f):=G_m(f,\Psi):=G_m(f,\Psi,\varrho):=\sum_{j=1}^m c_{k_j}(f,\Psi)\psi_{k_j}.
\end{equation*}
\notag
$$
The above algorithm $G_m(\,\cdot\,,\Psi)$ is a simple algorithm, which describes the theoretical scheme for the $m$-term approximation of an element $f$. This algorithm is called the Thresholding Greedy Algorithm (TGA) or simply the Greedy Algorithm (GA). In order to understand the efficiency of this algorithm we compare its accuracy with the best-possible accuracy when an approximant is a linear combination of $m$ terms from $\Psi$. The best we can achieve with the algorithm $G_m$ is or the slightly weaker inequality
$$
\begin{equation}
\|f-G_m(f,\Psi,\varrho)\|_X \leqslant G\sigma_m(f,\Psi)_X,
\end{equation}
\tag{1.6}
$$
for all elements $f\in X$, and with a constant $G=C(X,\Psi)$ independent of $f$ and $m$. It is clear that, when $X=H$ is a Hilbert space and $\mathcal B$ is an orthonormal basis, we have
$$
\begin{equation*}
\|f-G_m(f,\mathcal B,\varrho)\|_H=\sigma_m(f,\mathcal B)_H.
\end{equation*}
\notag
$$
We consider the following asymptotic characteristic of the TGA with respect to a fixed basis $\Psi$:
$$
\begin{equation*}
\gamma_m(\alpha,X,\Psi):=\sup_{f\in X\colon \|f\|_{A_1(\Psi)}<\infty,\,f\neq 0}\, \sup_{\varrho\in D(f)} \frac{\|f-G_m(f,\Psi,\varrho)\|_X}{\|f\|_X^{1-\alpha} \|f\|_{A_1(\Psi)}^\alpha}, \qquad \alpha\in [0,1].
\end{equation*}
\notag
$$
We mostly concentrate on the case $X=L_p$, $1\leqslant p\leqslant \infty$. In this case we write $\gamma_m(\alpha,p,\Psi)$. The following concept of a greedy basis was introduced in [6]. Definition 1.1. We call a basis $\Psi$ a greedy basis if for every $f\in X$ there exists a permutation $\varrho \in D(f)$ such that for a constant $C$ independent of $f$ and $m$. It is known (see [6]) that for a greedy basis $\Psi$ inequality (1.7) holds for all permutations $\varrho \in D(f)$. Therefore, Definition 1.1 and Corollary 1.1 imply the following bounds for greedy bases. Theorem 1.1. Let $1<p<\infty$. Then for any greedy basis $\Psi$ of $L_p(\Omega,\mu)$ and any $\alpha \in [0,1]$ we have In this paper we extend Theorem 1.1 in different directions. In § 3 we consider the Haar basis, which is a greedy basis for the $L_p$, $1<p<\infty$ (see [9]). We find the sharp order of the $\gamma_m(\alpha,L_p([0,1],\mu),\Psi)$ in the case when $\Psi$ is the Haar basis $\mathcal{H}_p$ and $\mu=\lambda$ is the Lebesgue measure. These bounds are better than the corresponding bounds in Theorem 1.1 in the case $2<p<\infty$. The reader can find results on greedy approximation of smooth multivariate functions with respect to bases similar to the multivariate Haar basis in [10] and [11]. We consider bases which are not greedy. In § 2 we find the sharp order of the quantity $\gamma_m(\alpha,L_p(\mathbb{T}^d,\lambda),\Psi)$ in the case when $\Psi$ is the trigonometric system. The reader can find a survey of the results on the rate of the best $m$-term trigonometric approximations of smooth multivariate functions in [13], Ch. 9. It is known (see [6]) that greedy bases are exactly those that are unconditional and democratic (see the definitions in § 3 below). In § 3 (see Theorems 3.1 and 3.2) we prove that Theorem 1.1 holds under the assumption that $\Psi$ is an unconditional basis. In § 3.2 we discuss a wider class of bases than the class of unconditional bases, quasi-greedy bases. It turns out that Theorem 1.1 can be extended to the class of quasi-greedy bases (see Theorem 3.5 below). Finally, in § 3.2 we prove that some error bounds can be improved for a subclass of the quasi-greedy bases, namely, for uniformly bounded quasi-greedy bases. We use $C$, $C(p,d)$ and so on, to denote various constants, with arguments indicating dependence on other parameters. We use the following symbols for brevity. For two nonnegative sequences $a=\{a_n\}_{n=1}^\infty$ and $b=\{b_n\}_{n=1}^\infty$, the relation, or order inequality, $a_n \ll b_n$ means that there is a number $C(a,b)$ such that, for all $n$, we have $ a_n\leqslant C(a,b)b_n$, and the relation $a_n\asymp b_n$ means that $a_n\ll b_n$ and $b_n\ll a_n$. § 2. Trigonometric systemIn this section we consider the case $X=L_p({\mathbb T}^d,\lambda)$, $1\leqslant p \leqslant \infty$, $\lambda$ is the normalized Lebesgue measure on $\mathbb{T}^d$ and $\Psi ={\mathcal T}^d := \{e^{i(\mathbf{k},\mathbf{x})}\}_{\mathbf{k}\in {\mathbb Z}^d}$ is the trigonometric system. It is convenient for us to deal with the complex trigonometric system. Results of this section hold for the real trigonometric system as well. Moreover, note that we can use general results for real Banach spaces and real trigonometric system and derive from these results the corresponding results for the complex trigonometric system. We define
$$
\begin{equation*}
\|f\|_{A_1(\mathcal T^d)}:=\sum_{\mathbf k\in \mathbb Z^d} |\widehat f(\mathbf k)|, \qquad \widehat f(\mathbf k):=(2\pi)^{-d}\int_{\mathbb T^d} f(\mathbf x)e^{-i(\mathbf k,\mathbf x)}\,d\mathbf x.
\end{equation*}
\notag
$$
The following theorem is known (see [8] and [12], p. 25, Theorem 2.2.1). We begin with the case $2\leqslant p< \infty$. Proof. The upper bound follows from Theorem 2.1 and Corollary 1.1. Now we prove the lower bound. Clearly, it is sufficient to carry out the proof in the case $d=1$. We use the Rudin–Shapiro polynomials (see, for instance, [12], Appendix, § 7.4)
$$
\begin{equation}
{\mathcal R}_m(x)=\sum_{|k| \leqslant m} \epsilon_k e^{ikx}, \qquad \epsilon_k=\pm 1, \quad x \in \mathbb T,
\end{equation}
\tag{2.1}
$$
which satisfy the estimate for an absolute constant $C_1$. For $s = \pm 1$ set Let $s = \pm 1$ be such that $|\Lambda_s| > |\Lambda_{-s}|$. Then $|\Lambda_{-s}|\leqslant m$. Let $G_m(\mathcal{R}_m)$ be a realization of the TGA as applied to $f=\mathcal{R}_m$ with all frequencies in $\Lambda_{-s}$ and maybe with some frequencies in $\Lambda_s$. Set $f_m := \mathcal{R}_m - G_m(\mathcal{R}_m)$. Then all the frequencies of $f_m$ are in $\Lambda_s$, and therefore By the Nikol’skii inequality for trigonometric polynomials (see [12], Appendix, p. 253, Theorem 7.5.4) the relation (2.3) implies that
$$
\begin{equation}
\|f_m\|_p \geqslant C_2m^{-1/p}\|f_m\|_\infty \geqslant C_2m^{1-1/p} .
\end{equation}
\tag{2.4}
$$
Clearly, we have Comparing (2.2), (2.4) and (2.5) we obtain the required estimate in the case ${2 \leqslant p < \infty}$. The theorem is proved. The following corollary can be of independent interest. Corollary 2.1. Let $2\leqslant p< \infty$. Then for any $f\in L_p$ and each $m\in \mathbb{N}$ we have This follows from Theorem 2.2 for $\alpha = 2h(p)$ and from the observation that the constant in the upper bound of Theorem 2.2 can depend only on $p$. We proceed to the case $1\leqslant p\leqslant 2$. Proof. We begin with the upper bounds. In the case $1<p\leqslant 2$ we can follow the lines of the proof of Theorem 2.2 and apply Theorem 2.1 and Corollary 1.1. This gives
$$
\begin{equation*}
\gamma_m(\alpha,p,\mathcal T^d) \leqslant C(p) m^{h(p)-\alpha/p'}, \qquad p':=\frac{p}{p-1}.
\end{equation*}
\notag
$$
It is clear that for all $\alpha\in(0,1]$ and $p<2$ we have Therefore, we need a different argument. Set $f_m:= f-G_m(f,\mathcal{T}^d)$. Then by Theorem 2.1 we obtain We now need the following well-known simple lemma from [7], p. 92 (see [2], § 7.4, for a historical discussion).
Lemma 2.1. Let $a_1\geqslant a_2\geqslant \dotsb \geqslant a_M\geqslant 0$ and $1\leqslant q\leqslant p\leqslant \infty$. Then for all $m\leqslant M$ we have By Lemma 2.1, for $q=1$ and $p=2$ we obtain
$$
\begin{equation}
\|f_m\|_p \leqslant \|f_m\|_2 \leqslant m^{-1/2}\|f\|_{A_1(\mathcal T^d)}.
\end{equation}
\tag{2.7}
$$
Writing $\|f_m\|_p = \|f_m\|_p^{1-\alpha}\|f_m\|_p^\alpha$ and using (2.6) and (2.7) we obtain the upper bound with an absolute constant as an extra factor. We now prove the lower bounds. We use the de la Vallée Poussin kernels (see, for instance, [12], Appendix, § 7.4) for $m=1,2,\dots$:
$$
\begin{equation}
\mathcal V_m(x):=\frac {1}{m} \sum_{l=m}^{2m-1} \mathcal D_l(x) , \qquad \mathcal D_l(x):= \sum_{|k|\leqslant l} e^{ikx}, \qquad x \in \mathbb T.
\end{equation}
\tag{2.8}
$$
It is known (see, for instance, [12], Appendix, p. 246, (7.4.14)) that
$$
\begin{equation}
\|\mathcal V_m\|_p \leqslant Cm^{1-1/p} , \qquad m=1,2,\dots , \quad 1 \leqslant p \leqslant \infty .
\end{equation}
\tag{2.9}
$$
We use the notations from the above proof of Theorem 2.2. Let $G_m(\mathcal{V}_m)$ be a realization of the TGA as applied to $f=\mathcal{V}_m$ with all frequencies in $\Lambda_{-s}$ and maybe with some frequencies in $\Lambda_s$. Set $f_m := \mathcal{V}_m - G_m(\mathcal{V}_m)$. Then a lower bound for $\|f_m\|_p$ follows from the relations
$$
\begin{equation*}
m \leqslant |\langle f_m,{\mathcal R}_m\rangle | \leqslant \|f_m\|_p \|{\mathcal R}_m\|_{p'} \leqslant C_1m^{1/2}\|f_m\|_p .
\end{equation*}
\notag
$$
We obtain Clearly, we have Note that it is easy to check that, actually, $\|\mathcal V_{m}\|_{A_1(\mathcal{T})} = 3m$. Relations (2.9)–(2.11) imply the required inequality in the case $1 \leqslant p \leqslant 2$. The proof of Theorem 2.3 is now complete. Corollary 2.2. Let $1\leqslant p\leqslant 2$. Then for any $f\in L_p$ and each $m\in \mathbb{N}$ we have § 3. Unconditional and quasi-greedy basesWe recall that we assume that $\Psi :=\{\psi_n\}_{n=1}^\infty$ is a (Schauder) basis of a Banach space $X$ which satisfies the condition $\|\psi_n\|_X \leqslant 1$, $n=1,2,\dots$ . 3.1. Unconditional basesThere are different equivalent definitions of the concept of unconditional basis (see, for instance, [12], § 1.4). It is convenient for us to use the following two equivalent definitions. We use the representation
It is well known that for an unconditional basis $\Psi$ of the space $L_p(\Omega,\mu)$, ${1\!<\!p\!<\!\infty}$, we have the following properties. U1. There are two positive constants $C_i(\Psi,p)$, $i=1,2$, such that for any ${f\in L_p(\Omega,\mu)}$ we have
$$
\begin{equation*}
C_1(\Psi,p) \|f\|_p \leqslant \|S(f,\Psi)\|_p \leqslant C_2(\Psi,p) \|f\|_p, \qquad S(f,\Psi):=\biggl( \sum_{n=1}^\infty |c_n(f)\psi_n|^2\biggr)^{1/2}.
\end{equation*}
\notag
$$
U2. Property U1 implies the following inequalities. Let $p^* := \min(p,2)$; then for ${f\in L_p(\Omega,\mu)}$ we have
$$
\begin{equation*}
\|f\|_p \leqslant C_3(\Psi,p) \biggl(\sum_{n=1}^\infty \|c_n(f)\psi_n\|_p^{p^*}\biggr)^{1/p^*}, \qquad 1<p<\infty.
\end{equation*}
\notag
$$
Theorem 3.1. Let $2\leqslant p < \infty$, and let $\Psi$ be an unconditional basis of $L_p(\Omega,\mu)$. Then Proof. By definition (I), for $f_m := f-G_m(f,\Psi)$ we have From property U2 we obtain
$$
\begin{equation}
\|f_m\|_p \leqslant C_3(\Psi,p) \biggl(\sum_{n\notin \Lambda_m(f)} \|c_n(f)\psi_n\|_p^{2}\biggr)^{1/2} \leqslant C_3(\Psi,p) \biggl(\sum_{n\notin \Lambda_m(f)} |c_n(f)|^{2}\biggr)^{1/2},
\end{equation}
\tag{3.2}
$$
where $\Lambda_m(f)$ is such that
$$
\begin{equation*}
\min_{n\in \Lambda_m(f)}|c_n(f)| \geqslant \max_{n\notin \Lambda_m(f)}|c_n(f)|.
\end{equation*}
\notag
$$
Therefore, by Lemma 2.1 inequality (3.2) implies that
$$
\begin{equation}
\|f_m\|_p \leqslant C_3(\Psi,p) m^{-1/2}\|f\|_{A_1(\Psi)}.
\end{equation}
\tag{3.3}
$$
Writing $\|f_m\|_p = \|f_m\|_p^{1-\alpha}\|f_m\|_p^\alpha$ and using (3.1) and (3.3) we obtain the inequality required in Theorem 3.1. The theorem is proved. Theorem 3.2. Let $1< p \leqslant 2$, and let $\Psi$ be an unconditional basis of $L_p(\Omega,\mu)$. Then Proof. This proof goes along the lines of the proof of Theorem 3.1. We only point out where we use another argument. Instead of (3.2), by property U2 we obtain
$$
\begin{equation}
\|f_m\|_p \leqslant C_3(\Psi,p) \biggl(\sum_{n\notin \Lambda_m(f)} \|c_n(f)\psi_n\|_p^{p}\biggr)^{1/p} \leqslant C_3(\Psi,p) \biggl(\sum_{n\notin \Lambda_m(f)} |c_n(f)|^{p}\biggr)^{1/p}.
\end{equation}
\tag{3.4}
$$
By Lemma 2.1 for $q=1$, inequality (3.4) implies that
$$
\begin{equation}
\|f_m\|_p \leqslant C_3(\Psi,p) m^{-(1-1/p)}\|f\|_{A_1(\Psi)}.
\end{equation}
\tag{3.5}
$$
Writing $\|f_m\|_p = \|f_m\|_p^{1-\alpha}\|f_m\|_p^\alpha$ and using (3.1) and (3.5) we obtain the inequality required in Theorem 3.2. The theorem is proved. Let $\mathcal{H} :=\{H_k\}_{k=1}^\infty$ denote the Haar basis on $[0,1)$ normalized in $L_2([0,1],\lambda)$ with respect to the Lebesgue measure $\lambda$: $H_1 =1$ on $[0,1)$ and for $k=2^n +l$, $n=0,1,\dots$ and $l=1,2,\dots,2^n$,
$$
\begin{equation*}
H_k=\begin{cases} 2^{n/2}, & x \in [(2l-2)2^{-n-1}, (2l-1)2^{-n-1}), \\ -2^{n/2}, & x \in [(2l-1)2^{-n-1}, 2l2^{-n-1}), \\ 0 & \text{otherwise}. \end{cases}
\end{equation*}
\notag
$$
We denote by $\mathcal{H}_p :=\{H_{k,p}\}_{k=1}^\infty$ the Haar basis $\mathcal{H}$ renormalized in $L_p([0,1],\lambda)$. It is well known that the Haar basis $\mathcal{H}_p$ is an unconditional basis for the $L_p([0,1],\lambda)$, $1<p<\infty$ (see, for instance, [5]). Now we show that Theorem 3.1 can be improved for the Haar basis. Proof. The Haar basis is an unconditional basis, and therefore for $1<p<\infty$ Now we use Lemma 3.1 (see below), which holds for a quasi-greedy basis (this is a weaker condition than the unconditionality of a basis). By Lemma 3.1 we obtain
$$
\begin{equation}
\|f_m\|_p \leqslant C_2(p) \sum_{n=m+1}^\infty a_n(f)\varphi(n)\frac{1}{n},
\end{equation}
\tag{3.7}
$$
where $\varphi(n)$ is the fundamental function of the Haar basis $\mathcal{H}_p$. It was proved in [9] (see also [12], p. 35, Lemma 2.3.3) that
$$
\begin{equation}
\varphi(n,\mathcal H_p,L_p([0,1],\lambda)) \leqslant C_3(p) n^{1/p}, \qquad 1<p<\infty.
\end{equation}
\tag{3.8}
$$
Relations (3.7) and (3.8) imply that
$$
\begin{equation}
\|f_m\|_p \leqslant C_4(p) m^{1/p-1}\|f\|_{A_1(\mathcal H_p)}.
\end{equation}
\tag{3.9}
$$
Bounds (3.6) and (3.9) imply the upper bound in Theorem 3.3.
We now prove the lower bounds. Given $m\in \mathbb{N}$, set Then by (3.8)
$$
\begin{equation}
\|f\|_p \leqslant C_3(p) (2m)^{1/p}, \qquad 1<p<\infty.
\end{equation}
\tag{3.10}
$$
For any realization $G_m(f,\mathcal{H}_p)$ of the TGA, by Lemma 2.3.4 from [12], p. 35, we obtain
$$
\begin{equation}
\|f-G_m(f,\mathcal H_p)\|_p \geqslant C_5(p) m^{1/p}.
\end{equation}
\tag{3.11}
$$
Clearly, The combination of relations (3.10)–(3.12) proves the lower bounds in Theorem 3.3. The theorem is proved. We say that $\Psi =\{\psi_k\}_{k=1}^\infty$ is $L_p$-equivalent to $\Phi =\{\phi_k\}_{k=1}^\infty$ if for any finite set $\Lambda$ and any coefficients $c_k$, $k\in \Lambda$, we have
$$
\begin{equation}
C_1(p,\Psi,\Phi) \biggl\|\sum_{k\in \Lambda}c_k\phi_k\biggr\|_{p} \leqslant \biggl\|\sum_{k\in \Lambda}c_k\psi_k\biggr\|_{p} \leqslant C_2(p,\Psi,\Phi) \biggl\|\sum_{k\in \Lambda}c_k\phi_k\biggr\|_{p}
\end{equation}
\tag{3.13}
$$
for two positive constants $C_1(p,\Psi,\Phi)$ and $C_2(p,\Psi,\Phi)$ which can depend on $p$, $\Psi$ and $\Phi$. For sufficient conditions on $\Psi$ to be $L_p$-equivalent to $\mathcal{H}_p$, see [4] and [1]. Remark 3.1. Theorem 3.3 holds for any basis $\Psi$, which is $L_p$-equivalent to the Haar basis $\mathcal{H}_p$. 3.2. Quasi-greedy basesAs above, let $X$ be an infinite-dimensional separable Banach space with norm $\|\,{\cdot}\,\|:=\|\,{\cdot}\,\|_X$, and let $\Psi:=\{\psi_k\}_{k=1}^{\infty}$ be a semi-normalized basis of $X$ ($0<c_0\leqslant\|\psi_k\|\leqslant 1$, $k\in {\mathbb N}$). In this subsection we concentrate on a wider class of bases than unconditional bases, namely, quasi-greedy bases. The concept of quasi-greedy basis was introduced in [6]. The reader can find a detailed discussion of quasi-greedy bases in [12], Ch. 3. Definition 3.1. A basis $\Psi$ is called a quasi-greedy basis of $X$ if there exists a constant $C=C(\Psi,X)$ such that Subsequently, Wojtaszczyk [16] proved that these are precisely the bases for which the TGA merely converges, that is, We now formulate some known results, which are useful in our applications. Given an element $f\in X$, we consider the expansion Let the sequence $k_j$, $j=1,2,\dots$, of positive integers be such that We use the notation for the decreasing rearrangement of the coefficients of $f$.The following theorem is borrowed from [15] (see also [12], p. 70, Theorem 3.2.10). We note that in the case $p=2$ Theorem 3.4 was proved in [16]. Theorem 3.4. Let $\Psi=\{\psi_k\}_{k=1}^\infty$ be a quasi-greedy basis of the space $L_p$, ${1\!<\!p\!<\!\infty}$. Then there exist positive constants $C_i=C_i(p,\Psi)$, $i=1,\dots,4$, such that for each $f\in L_p$ we have and We define the fundamental function $\varphi(m):=\varphi(m,\Psi,X)$ of a basis $\Psi$ in $X$ by
$$
\begin{equation*}
\varphi(m,\Psi,X):=\sup_{|A|\leqslant m}\biggl\|\sum_{k\in A}\psi_k\biggr\|.
\end{equation*}
\notag
$$
Definition 3.2. We say that a basis $\Psi =\{\psi_k\}_{k=1}^\infty$ is a democratic basis of $X$ if there exists a constant $D:=D(X,\Psi)$ such that for any two finite sets of indices $P$ and $Q$ of the same cardinality $|P|=|Q|$ we have The following lemma was proved in [12], p. 72, in the same way as in Theorem 3.4. Theorem 3.5. Let $1<p<\infty$. Then for any quasi-greedy basis $\Psi$ of $L_p(\Omega,\mu)$ and any $\alpha \in [0,1]$ we have Proof. The proof is based on Theorem 3.4. By Definition 3.1 of a quasi-greedy basis for $f_m :=f- G_m(f,\Psi)$ we have By Theorem 3.4, in the case $2\leqslant p <\infty$ we obtain
$$
\begin{equation}
\|f_m\|_p\leqslant C_2 \sum_{n=m+1}^\infty n^{-1/2}a_n(f) \leqslant C_2m^{-1/2}\|f\|_{A_1(\Psi)}
\end{equation}
\tag{3.17}
$$
and for $1<p\leqslant 2$
$$
\begin{equation}
\|f_m\|_p\leqslant C_4 \sum_{n=m+1}^\infty n^{1/p-1}a_n(f) \leqslant C_4m^{1/p-1}\|f\|_{A_1(\Psi)}.
\end{equation}
\tag{3.18}
$$
Combining bounds (3.16)–(3.18) we obtain (3.15). The theorem is proved. We now discuss a special subclass of quasi-greedy bases, namely, the uniformly bounded quasi-greedy bases. The existence of uniformly bounded quasi-greedy bases in $L_p([0,1],\lambda)$, $1<p<\infty$, is known (see [12], p. 83, Theorem 3.3.5, and p. 76, Theorem 3.2.20). Theorem 3.6. Let $1<p<\infty$. Then for any uniformly bounded quasi-greedy basis $\Psi$ of $L_p(\Omega,\mu)$ and any $\alpha \in [0,1]$ we have Proof. The upper bounds can be proved in the same way as Theorem 3.5. Note that in the case $2\leqslant p<\infty$ the upper bounds in Theorem 3.6 follow directly from Theorem 3.5. In the case $1<p\leqslant 2$, instead of Theorem 3.4 we use the following proposition.
Proposition 3.1 (see [12], p. 77, Proposition 3.2.22). Let $\Psi$ be a uniformly bounded quasi-greedy basis $\Psi=\{\psi_j\}_{j=1}^\infty$ in $L_p$, $1<p<\infty$. Then for $f\in L_p$ we have Now we prove the lower bounds. This proof is based on the following proposition. Proposition 3.2 (see [12], p. 76, Proposition 3.2.21). Let $\Psi$ be a uniformly bounded quasi-greedy basis $\Psi=\{\psi_j\}_{j=1}^\infty$ in $L_p$, $1<p<\infty$. Then $\Psi$ is democratic with fundamental function $\varphi(m,\Psi,L_p)\asymp m^{1/2}$. Proposition 3.2 means (see Definition 3.2 above) that there exist two positive constants $c'(p,\Psi)$ and $C'(p,\Psi)$ such that for any index subset $\Lambda$, $|\Lambda|=m$, we have
$$
\begin{equation}
c'(p,\Psi) m^{1/2} \leqslant \biggl\|\sum_{k\in \Lambda} \psi_k\biggr\|_p \leqslant C'(p,\Psi) m^{1/2}.
\end{equation}
\tag{3.21}
$$
As an example we take
$$
\begin{equation*}
f:=\sum_{k=1}^{2m} \psi_k \quad\text{and}\quad G_m(f,\Psi):=\sum_{k=1}^{m}\psi_k.
\end{equation*}
\notag
$$
Then we have
$$
\begin{equation*}
\|f\|_p \leqslant C'(p,\Psi)(2m)^{1/2}, \quad \|f-G_m(f,\Psi)\|_p \geqslant c'(p,\Psi)m^{1/2} \quad\text{and}\quad \|f\|_{A_1(\Psi)} \leqslant2m.
\end{equation*}
\notag
$$
Combining the above relations we obtain the required lower bounds. Theorem 3.6 is proved. Remark 3.2. In the case $2\leqslant p<\infty$ the lower bounds of Theorem 3.6 show that Theorem 3.5 is sharp in this case. § 4. A criterion for good rate of approximationWe prove here necessary and sufficient conditions on a basis $\Psi$ which provide a good rate of approximation for elements of $A_1(\Psi)$. We define the following property of a basis $\Psi$. An unconditional bound with parameters $a$ and $K$We say that a basis $\Psi$ of $X$ satisfies an unconditional bound with parameters $a$ and $K$ (($\mathrm{UB}(a,K)$)) if for each finite set $\Lambda\subset \mathbb{N}$ and each choice of signs $\epsilon_k=\pm 1$, $k\in\Lambda$, we have
$$
\begin{equation}
\biggl\|\sum_{k\in\Lambda} \epsilon_k\psi_k\biggr\|_X \leqslant K|\Lambda|^a.
\end{equation}
\tag{4.1}
$$
It is clear that our condition $\|\psi_k\|_X\leqslant 1$, $k=1,2,\dots$, guarantees that $\Psi$ satisfies $\mathrm{UB}(1,1)$. We restrict ourselves to $a\in [0,1)$. Obviously, an orthonormal basis of a Hilbert space satisfies $\mathrm{UB}(1/2,1)$. There are nontrivial examples of $\mathrm{UB}(a,K)$-bases. For instance, it is known (see [9], [12], Ch. 2, and [13], Ch. 8) that for $1<p<\infty$ the univariate Haar basis normalized in $L_p$ satisfies $\mathrm{UB}(1/p,C(p))$. The reader can find a discussion of results on sparse approximation, including some historical comments, in [13], Ch. 9. Theorem 4.1. (A) Let $b\in (0,1]$. Suppose that $\Psi$ is such that for any $f\in A_1(\Psi)$ there exists a permutation $\varrho \in D(f)$ with the property Then $\Psi$ satisfies $\mathrm{UB}(1-b,2)$. (B) Assume that $\Psi$ satisfies $\mathrm{UB}(a,K)$, $a\in [0,1)$. Then for any $f\in A_1(\Psi)$ and any permutation $\varrho \in D(f)$ we have Proof. First we prove part (A). We introduce some notation. For $m\in\mathbb{N}$ let $V(m)$ denote the vertex set of the unit cube $[-1,1]^m$. In other words $V(m)$ consists of all vectors $\mathbf{v} = (v_1,\dots,v_m)$ such that $v_j$ takes values $1$ or $-1$ for $j=1,\dots,m$. For $\Lambda =\{k_j\}_{j=1}^m \subset \mathbb{N}$ and $\mathbf{v} \in V(m)$ set Given $\Lambda$ and $\mathbf{v}$, consider the function where $\delta>0$, $Q\subset \mathbb{N}$ is such that $|Q|=m$ and $\Lambda\cap Q =\varnothing$, and $\mathbf{u}$ is any vector in $V(m)$, for instance, $\mathbf{u}=(1,\dots,1)$. Then $((2+\delta)m)^{-1} f\in A_1(\Psi)$, Taking into account that $\delta>0$ is arbitrary, we complete the proof of part (A).
Second we prove part (B). The proof is based on the following lemma. Lemma 4.1. Let $\Psi=\{\psi_k\}_{k=1}^\infty$ be a basis of $X$ satisfying $\mathrm{UB}(a,K)$. Then for each $f\in X$ we have where the $a_n(f)$ were defined in (3.14). Proof. Without loss of generality assume that $f$ is normalized in such a way that $a_1(f)< 1$. Set $\mathcal{N}_s:=\{n\colon a_n(f)\geqslant 2^{-s}\}$, $s\in \mathbb{N}$, and $N_s:=|\mathcal{N}_s|$. Note that for small $s$ the sets $\mathcal{N}_s$ can be empty. Clearly, for nonempty $\mathcal{N}_s$ we have $\mathcal{N}_s=[1,N_s]$. We have
$$
\begin{equation}
\|f\|_X \leqslant \sum_{s=1}^\infty\biggl\|\sum_{n\in {\mathcal N}_s\setminus{\mathcal N}_{s-1}}c_{k_n}(f)\psi_{k_n} \biggr\|_X.
\end{equation}
\tag{4.4}
$$
Our assumption that $\Psi$ satisfies $\mathrm{UB}(a,K)$ implies that for any finite $\Lambda\subset \mathbb{N}$ and any coefficients $b_k$, $k\in \Lambda$, we have
$$
\begin{equation}
\biggl\|\sum_{k\in\Lambda} b_k\psi_k\biggr\|_X \leqslant \Bigl(\max_{k\in\Lambda}|b_k|\Bigr) K|\Lambda|^a.
\end{equation}
\tag{4.5}
$$
Indeed, let $\Lambda = \{k_j\}_{j=1}^n$ and
$$
\begin{equation*}
\mathbf w=(w_1,\dots,w_n), \qquad w_j:=b_{k_j}\Bigl(\max_{k\in\Lambda}|b_k|\Bigr)^{-1}, \qquad j=1,\dots,n.
\end{equation*}
\notag
$$
Then $\mathbf{w} \in [-1,1]^n$, and therefore $\mathbf{w}$ is a convex combination of elements of $V(n)$. This proves (4.5). Using (4.5), from (4.4) we derive
$$
\begin{equation}
\|f\|_X\leqslant 2K\sum_{s=1}^\infty2^{-s} |{\mathcal N}_s\setminus{\mathcal N}_{s-1}|^a
\end{equation}
\tag{4.6}
$$
and
$$
\begin{equation}
\|f\|_X \leqslant 2K\sum_{s=1}^\infty 2^{-s}N_s^{a} \leqslant 2K\sum_{s=1}^\infty2^{-s}\sum_{n=1}^{N_s}n^{a-1}= 2K\sum_{n=1}^\infty n^{a-1}\sum_{s\colon N_s\geqslant n} 2^{-s}.
\end{equation}
\tag{4.7}
$$
Set Then
$$
\begin{equation*}
\sum_{s\colon N_s\geqslant n} 2^{-s} \leqslant 2^{-s(n)+1}.
\end{equation*}
\notag
$$
Note that for all $s$ such that $N_s\geqslant n$ we have Therefore, from (4.7) we find that This completes the proof of Lemma 4.1. Now we complete the proof of part (B). We have
$$
\begin{equation*}
\|f-G_m(f,\Psi,\varrho)\|_X=\biggl\|\sum_{n=m+1}^\infty c_{k_n}(f)\psi_{k_n}\biggr\|_X
\end{equation*}
\notag
$$
and we continue by Lemma 4.1:
$$
\begin{equation*}
\biggl\|\sum_{n=m+1}^\infty c_{k_n}(f)\psi_{k_n}\biggr\|_X\leqslant 4K\sum_{n=m+1}^\infty n^{a-1}a_n(f) \leqslant 4K m^{a-1}\|f\|_{A_1(\Psi)}.
\end{equation*}
\notag
$$
The proof of Theorem 4.1 is now complete. AcknowledgementThe author is grateful to the referee for helpful comments and suggestions.
Citation in format AMSBIB
\Bibitem{Tem24} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|