text:
\section{Introduction}

This paper deals with sparse approximation. Driven by applications in biology, medicine, and engineering approximation problems are formulated in very high dimensions, which bring to the fore new phenomena.  One aspect of the high-dimensional context is a focus on  sparse signals (functions). The main motivation for the study of sparse signals is that many real world signals can be well approximated by sparse ones. A very important step in solving multivariate problems with large dimension
occurred  during last 20 years. Researchers began to use sparse
representations as a way to model the corresponding function classes. This approach
automatically implies a need for nonlinear approximation, in particular, for greedy approximation. We give a brief description of a sparse approximation problem. In a general setting we are working in a Banach space $X$ with a redundant system of elements ${\mathcal D}$ (dictionary ${\mathcal D}$). There is a solid justification of importance of a Banach space setting in numerical analysis in general and in sparse approximation in particular (see, for instance, \cite{Tbook}, Preface, and \cite{ST}).
An element (function, signal) $f\in X$ is said to be $K$-sparse with respect to ${\mathcal D}$ if
it has a representation $f=\sum_{i=1}^Kx_ig_i$,   $g_i\in {\mathcal D}$, $i=1,\dots,K$. The set of all $K$-sparse elements is denoted by $\Sigma_K({\mathcal D})$. For a given element $f_0$ we introduce the error of best $m$-term approximation
$$
\sigma_m(f_0,{\mathcal D}) := \inf_{f\in\Sigma_m({\mathcal D})} \|f_0-f\|.
$$
Here are two fundamental problems of sparse approximation.

{\bf P1. Exact recovery.} Suppose we know that $f_0\in \Sigma_K({\mathcal D})$. How can we recover it?

{\bf P2. Approximate recovery.}   How to design a practical algorithm that builds $m$-term approximations comparable to
best $m$-term approximations?

It is known that in both of the above problems greedy-type algorithms play a fundamental role. We discuss one of them
here. There are two special cases of the above general setting of the sparse approximation problem.

(I). Instead of a Banach space $X$ we consider a Hilbert space $H$. Approximation is still with respect to a redundant dictionary ${\mathcal D}$.

(II). We approximate in a Banach space $X$ with respect to a basis $\Psi$ instead of a redundant dictionary ${\mathcal D}$.

This section discusses setting (I) and the corresponding generalizations to the Banach space setting.   Section 4 addresses setting (II). We begin our discussion with the Orthogonal Greedy Algorithm (OGA) in a Hilbert space. The Orthogonal Greedy Algorithm is called the Orthogonal Matching Pursuit (OMP) in signal processing. We will use the name Orthogonal Matching Pursuit for this algorithm in this paper. It is natural to compare performance of the OMP with the best $m$-term approximation with regard to a dictionary ${\mathcal D}$.  We  recall some notations and
definitions from the theory of greedy algorithms. Let $H$ be a
real Hilbert space with an inner product
$\langle\cdot,\cdot\rangle $ and the norm $\|x\|:=\langle x,x
\rangle^{1/2}$. We say a set ${\mathcal D}$ of functions (elements) from $H$
is a dictionary if each $g\in {\mathcal D}$ has a unit norm $(\|g\|=1)$ and the closure of
$\operatorname{span} {\mathcal D}$ is $H.$   Let a sequence $\tau = \{t_k\}_{k=1}^\infty$,
$0\le t_k \le 1$, be given. The following greedy algorithm was
defined in \cite{T1} under the name Weak Orthogonal Greedy Algorithm (WOGA).

 {\bf Weak Orthogonal Matching Pursuit (WOMP).} Let $f_0$ be given. Then for each $m\ge 1$ we inductively define:

(1) $\varphi_m  \in {\mathcal D}$ is any element satisfying
$$
|\langle f_{m-1},\varphi_m\rangle | \ge t_m
\sup_{g\in {\mathcal D}} |\langle f_{m-1},g\rangle |.
$$

(2) Let $H_m := \operatorname{span} (\varphi_1,\dots,\varphi_m)$ and let
$P_{H_m}(\cdot)$ denote an operator of orthogonal projection onto $H_m$.
Define
$$
G_m(f_0,{\mathcal D}) := P_{H_m}(f_0).
$$

(3) Define the residual after $m$th iteration of the algorithm
$$
f_m := f_0-G_m(f_0,{\mathcal D}).
$$

In the case $t_k=1$, $k=1,2,\dots$,   WOMP is called the Orthogonal
Matching Pursuit (OMP). In this paper we only consider the case $t_k=t$, $k=1,2,\dots$, $t\in(0,1]$.

The theory of the WOMP is well developed (see \cite{Tbook}). In first results on performance of the WOMP in problems {\bf P1} and {\bf P2}
researchers imposed the incoherence assumption on a dictionary ${\mathcal D}$. The reader can find detailed discussion of these results in \cite{Tbook}, Section 2.6 and \cite{L}. Recently,  exact recovery results and Lebesgue-type inequalities for the WOMP under assumption that ${\mathcal D}$ satisfies Restricted Isometry Property (RIP) introduced in compressed sensing theory (see Definition \ref{RIP-def} below) have been proved (see \cite{Z}, \cite{F}, \cite{WS}).
A breakthrough result in this direction was obtained by Zhang \cite{Z}. In particular, he proved that if $\delta^{{RIP}}_{31K}({\mathcal D})<1/3$ then the OMP recovers exactly all $K$-sparse signals within  $30K$ iterations. In other words, $f_{30K}=0$. It is interesting and difficult problem to improve the constant $30$. There are several papers devoted to this problem (see \cite{F} and \cite{WS}).
In this paper we develop Zhang's technique in two directions: (1) to obtain exact recovery with high probability of random $K$-sparse signals

 within $\lceil K(1+\epsilon)\rceil$ iterations of the OMP
 and (2) to obtain recovery results and the Lebesgue-type inequalities in the Banach space setting.

In Section 2 we prove exact recovery results under RIP conditions on a dictionary combined with assumptions on the sparse signal to be recovered (see Theorem \ref{T2.1}). We prove that the corresponding assumptions on a sparse signal are satisfied with high probability if it is a random signal. In particular, we prove the following theorem.
\begin{Theorem}\label{T1.1} For any $\epsilon>0$ there exist $\delta=\delta(\epsilon)>0$ and $K_0 = K_0(\epsilon)$ such that for any dictionary ${\mathcal D}$, $\delta^{{RIP}}_{2K}({\mathcal D})<\delta$, $K\ge K_0$, the following statement holds. Let $f_0\in\Sigma_K({\mathcal D})$ and its nonzero coefficients are uniformly distributed on $[-1,1]$ independent random variables. Then $f_{\lceil K(1+\epsilon)\rceil}=0$ with  probability greater than $1-\operatorname{exp}(-C(\epsilon)K)$.
\end{Theorem}
This theorem shows that in a probabilistic sense the OMP is almost optimal for exact recovery.

Sections 3 is devoted to the Banach space setting.
Let $X$ be a Banach space with norm $\|\cdot\|:=\|\cdot\|_X$. As in the case of Hilbert spaces we say that a set of elements (functions) ${\mathcal D}$ from $X$ is a dictionary  if each $g\in {\mathcal D}$ has norm   one ($\|g\|=1$),
and the closure of $\operatorname{span} {\mathcal D}$ is $X$.
For a nonzero element $g\in X$ we let $F_g$ denote a norming (peak) functional for $g$:
$$
\|F_g\|_{X^*} =1,\qquad F_g(g) =\|g\|_X.
$$
The existence of such a functional is guaranteed by the Hahn-Banach theorem.

Let
$\tau := \{t_k\}_{k=1}^\infty$ be a given weakness sequence of  nonnegative numbers $t_k \le 1$, $k=1,\dots$. We define the Weak Chebyshev Greedy Algorithm (WCGA) (see \cite{T15}) as a generalization for Banach spaces of the Weak Orthogonal Matching Pursuit.  We study in detail the WCGA in this paper.

 {\bf Weak Chebyshev Greedy Algorithm (WCGA).}
Let $f_0$ be given. Then for each $m\ge 1$ we have the following inductive definition.

(1) $\varphi_m :=\varphi^{c,\tau}_m \in {\mathcal D}$ is any element satisfying
$$
|F_{f_{m-1}}(\varphi_m)| \ge t_m\sup_{g\in{\mathcal D}}  | F_{f_{m-1}}(g)|.
$$

(2) Define
$$
\Phi_m := \Phi^\tau_m := \operatorname{span} \{\varphi_j\}_{j=1}^m,
$$
and define $G_m := G_m^{c,\tau}$ to be the best approximant to $f_0$ from $\Phi_m$.

(3) Let
$$
f_m := f^{c,\tau}_m := f_0-G_m.
$$

In Section 3 we prove the Lebesgue-type inequalities for the WCGA. A very important advantage of the WCGA  is its convergence and rate of convergence properties. The WCGA is well defined for all $m$. Moreover, it is known (see \cite{T15} and \cite{Tbook}) that the WCGA with $\tau=\{t\}$ converges for all $f_0$ in all uniformly smooth Banach spaces with respect to any dictionary. That is, when $X$ is a real Banach space and the modulus of smoothness of $X$ is defined as follows
\begin{equation*}
\rho(u):=\frac{1}{2}\sup_{x,y;\|x\|= \|y\|=1}\left|\|x+uy\|+\|x-uy\|-2\right|,
\end{equation*}
then the uniformly smooth Banach space is the one with $\rho(u)/u\to 0$ when $u\to 0$.

For notational convenience we consider here a countable dictionary ${\mathcal D}=\{g_i\}_{i=1}^\infty$. For a given $f_0$, let the sparse element (signal)
 $$
 f:=f^\epsilon=\sum_{i\in T}x_ig_i
 $$
 be such that $\|f_0-f^\epsilon\|\le \epsilon$ and $|T|=K$. For $A\subset T$ denote
 $$
 f_A:=f_A^\epsilon := \sum_{i\in A}x_ig_i.
 $$

  We use the following two assumptions.

 {\bf A1. Nikol'skii-type inequality.} The sparse element $f=\sum_{i\in T}x_ig_i$ satisfies Nikol'skii-type $\ell_1X$ inequality with parameter $r$ if
 \begin{equation*}
 \sum_{i\in A} |x_i| \le C_1|A|^{r}\|f_A\|,\quad A\subset T,\quad r\ge 1/2.
 \end{equation*}

{\bf A2. Incoherence property.}  The sparse element $f=\sum_{i\in T}x_ig_i$ has incoherence property with parameters $D$ and $U$ if for any $A\subset T$ and any $\Lambda$, such that $A\cap \Lambda =\emptyset$ and $|A|+|\Lambda| \le D$, we have for any $\{c_i\}$
\begin{equation*}
\|f_A-\sum_{i\in\Lambda}c_ig_i\|\ge U^{-1}\|f_A\|.
\end{equation*}

 The main result of Section 3 is the following.
 \begin{Theorem}\label{T1.5} Let $X$ be a Banach space with $\rho(u)\le \gamma u^2$. Suppose $K$-sparse $f^\epsilon$ satisfies {\bf A1}, {\bf A2} and $\|f_0-f^\epsilon\|\le \epsilon$. Then the WCGA with weakness parameter $t$ applied to $f_0$ provides
$$
\|f_{C(t,\gamma,C_1)U^2\ln (U+1) K^{2r}}\| \le C\epsilon\quad\text{for}\quad K+C(t,\gamma,C_1)U^2\ln (U+1) K^{2r}\le D
$$
with an absolute constant $C$.
\end{Theorem}

  Theorem \ref{T1.5} provides a corollary for Hilbert spaces that gives sufficient conditions somewhat weaker than the known RIP conditions on ${\mathcal D}$ for the Lebesgue-type inequality to hold. We formulate it as a theorem.
 \begin{Theorem}\label{T1.6} Let $X$ be a Hilbert space. Suppose $K$-sparse $f^\epsilon$ satisfies  {\bf A2} and $\|f_0-f^\epsilon\|\le \epsilon$. Then the WOMP with weakness parameter $t$ applied to $f_0$ provides
$$
\|f_{C(t,U) K}\| \le C\epsilon\quad\text{for}\quad K+C(t,U) K\le D
$$
with an absolute constant $C$.
\end{Theorem}
Theorem \ref{T1.6} implies the following corollary.
 \begin{Corollary}\label{C1.0} Let $X$ be a Hilbert space. Suppose any $K$-sparse $f$ satisfies   {\bf A2}.   Then the WOMP with weakness parameter $t$ applied to $f_0$ provides
$$
\|f_{C(t,U) K}\| \le C\sigma_K(f_0,{\mathcal D})\quad\text{for}\quad K+C(t,U) K\le D
$$
with an absolute constant $C$.
\end{Corollary}

We show in Sections 3 that the RIP condition with parameters $D$ and $\delta$ implies the $(D,D)$ unconditionality with
$U=(1+\delta)^{1/2}(1-\delta)^{-1/2}$. Therefore, Corollary \ref{C1.0} reads as follows in this case.

 \begin{Corollary}\label{C1.1'} Let $X$ be a Hilbert space. Suppose ${\mathcal D}$ satisfies RIP condition with parameters $D$ and $\delta$.   Then the WOMP with weakness parameter $t$ applied to $f_0$ provides
$$
\|f_{C(t,\delta) K}\| \le C\sigma_K(f_0,{\mathcal D})\quad\text{for}\quad K+C(t,\delta) K\le D
$$
with an absolute constant $C$.
\end{Corollary}

  We   emphasize that in Theorem \ref{T1.5} we impose our conditions on an individual function $f^\epsilon$. It may happen that the dictionary does not satisfy assumptions of $\ell_1X$ inequality and $(K,D)$-unconditionality (see Section 3) but the given $f_0$ can be approximated by $f^\epsilon$ which does satisfy assumptions {\bf A1} and {\bf A2}. Even in the case of a Hilbert space our approach adds something new to the study based on the RIP. First of all, Theorem \ref{T1.6} shows that it is sufficient to impose assumption {\bf A2} on an individual $f^\epsilon$ in order to obtain exact recovery and the Lebesgue-type inequality results. Second, Corollary \ref{C1.0} shows that the condition {\bf A2}, which is weaker than the RIP condition, is sufficient for exact recovery and the Lebesgue-type inequality results. Third, Corollary \ref{C1.1'} shows that even if we impose our assumptions in terms of RIP we do not need to assume that $\delta < \delta_0$. In fact, the result works for all $\delta<1$ with parameters depending on $\delta$.

  \section{Almost optimality of the OMP}

  We prove Theorem \ref{T1.1} in this section. For the readers convenience we use notations which are standard in signal processing.
Let ${\mathcal D}=\{\phi_i\}_{i=1}^N$ be a dictionary in ${\mathbb R}^M$, $M<N$. By $\Phi$ denote an $M\times N$ matrix, consisting of elements of ${\mathcal D}$ ($\phi_i\in {\mathbb R}^M$ is the $i$-th column of $\Phi$). We say that ${\mathbf x}\in {\mathbb R}^N$ is $S$-sparse if ${\mathbf x}$ has at most $S$ nonzero coordinates.

\begin{Definition}\label{RIP-def}
A matrix $\Phi$ satisfies $RIP(S,\delta)$ if the inequality
\begin{equation}\label{RIP-ineq}
(1-\delta)\|{\mathbf x}\|^2 \le \|\Phi {\mathbf x}\|^2\le (1+\delta)\|{\mathbf x}\|^2
 \end{equation}
 holds for all $S$-sparse ${\mathbf x}\in{\mathbb R}^N$.
 The minimum of all constants $\delta$, satisfying (\ref{RIP-ineq}),
 is called the isometric constant $\delta_S(\Phi) = \delta_S({\mathcal D}) = \delta^{{RIP}}_S({\mathcal D})$.
\end{Definition}

In this section we study the OMP and use the ``compressed sensing notation'' for the residual of the OMP. Set
\begin{equation*}
 {\mathbf r}^m := f_m,\ m\ge 0.
\end{equation*}
Consider the set
\begin{equation*}
\Omega=\{1,\ldots,N\}.
\end{equation*}
Since $f_0\in\Sigma_K({\mathcal D})$, there exists an  ${\mathbf x} = (x_1,x_2,\ldots, x_N)$, $\operatorname{supp}{\mathbf x} = T$, $T\subset\Omega$, $|T| = K$ such that
\begin{equation*}
{\mathbf r}^0=f_0= \Phi{\mathbf x}.
\end{equation*}
Denote by $T^m$ the set of indices of $\phi_i$ picked by the OMP after $m$ iterations.
According to the definition of the OMP for every $m
\ge 0$ we choose ${\mathbf x}^m\in{\mathbb R}^N$, satisfying the following relations
\begin{equation}\label{Tmdef}
 \operatorname{supp}{\mathbf x}^m \subset T^m,\quad |T^m| = m,\text{ while }{\mathbf r}^m\ne 0,
\end{equation}
\begin{equation*}
G_m(f,{\mathcal D}) = \Phi{\mathbf x}^m,
\end{equation*}
\begin{equation}\label{rmPhi}
{\mathbf r}^m = \Phi{\mathbf x}-
\Phi{\mathbf x}^m.
\end{equation}
Let $N({\mathbf x},\nu)$ be the minimal integer such that
\begin{equation}\label{N-def}
\|{\mathbf x}_\Lambda\|^2 >\nu, \text { for all }\Lambda \subset T,\ |\Lambda| \ge N({\mathbf x},\nu) + 1.
\end{equation}

\begin{Theorem}\label{T2.1} There exists an absolute constant $\widehat C$ such that for any $\delta$, $0<\delta < 0.001$, an integer $K \ge K_0 = K_0(\delta)$, and a dictionary ${\mathcal D}$, $\delta^{{RIP}}_{2K}({\mathcal D})<\delta$ the following statement holds.The OMP recovers exactly every $K$-sparse signal ${\mathbf x}$, $\|{\mathbf x}\|_\infty\le 1$, within  $K + 6N({\mathbf x}, \widehat C\delta^{1/2}K)$ iterations, in other words, ${\mathbf r}^{K + 6N({\mathbf x}, \widehat C\delta^{1/2}K)}=0$.
\end{Theorem}
Here is a direct corollary of Theorem \ref{T2.1}.
\begin{Corollary}\label{C2.1} Let $K$-sparse ${\mathbf x}$ be such that $|x_i|=1$, $i\in T$, $|T|=K$. Then under assumptions of Theorem \ref{T2.1} the OMP recovers ${\mathbf x}$ exactly within $(1+ 6\widehat C\delta^{1/2})K$ iterations.
\end{Corollary}
\begin{proof}
Set
\begin{equation*}
\Gamma^m:=T\setminus T^m.
\end{equation*}
 We fix
 \begin{equation}\label{a-def}
a := \delta^{1/2}.
\end{equation}
Consider $m\in{\mathbb Z}_+ $ such that
\begin{equation}\label{bas-ineq-l}
 |T^m| +[aK] = m+[aK] \le K.
 \end{equation}
Assume that $K\ge K_0 = K_0(a) \ge 1/a$.
Let $z^m$ be the maximal number, satisfying the following inequality
\begin{equation}\label{zl-def}
\left|\{i\in \Gamma^m:|x_i| \ge z^m\}\right| \ge [aK],\ \left|\{i\in \Gamma^m: |x_i| \le z^m\}\right| \ge |\Gamma^m|- [aK].
\end{equation}
In other words $z^m$ is the $[aK]$th largest element out of $\{|x_i|\}_{i\in \Gamma^m}$. We use the following lemma.

\begin{Lemma}\label{lm-main}
Under (\ref{bas-ineq-l})  the following inequality is valid:
\begin{equation*}
\|{\mathbf r}^m\|^2 - \|{\mathbf r}^{m+1}\|^2 \ge (z^m)^2(1-C_1 a).
 \end{equation*}
\end{Lemma}

\begin{proof}
According to (\ref{zl-def}), we can choose sets
\begin{equation}\label{Tl+cardinality}
\Gamma^m_+ \subset \Gamma^m,\quad |\Gamma^m_+| = [aK]
\end{equation}
and
\begin{equation}\label{Tl-def}
\Gamma^m_-:=\Gamma\setminus \Gamma^m_+
\end{equation}
with the following property
\begin{equation}\label{Tl+def}
\min_{i\in T^m_+}|x_i|\ge  z^m \ge \max_{i\in \Gamma^m_-}|x_i|.
\end{equation}
Consider ${\mathbf w}\in{\mathbb R}^N$ such that
\begin{equation}\label{w-def}
{\mathbf w}_{T\cap T^m\cup \Gamma^m_+} = {\mathbf x}_{T\cap T^m\cup \Gamma^m_+},\quad {\mathbf w}_{\Omega\setminus(T\cap T^m\cup \Gamma^m_+)} = 0.
\end{equation}
We use several well-known properties of the OMP:
\begin{equation}\label{WS-1}
\|{\mathbf r}^m\|^2 - \|{\mathbf r}^{m+1}\|^2 \ge \sup_{\phi\in{\mathcal D}}\<{\mathbf r}^m,\phi\>^2,
 \end{equation}
\begin{equation}\label{Prp-1}
\sup_{\phi\in{\mathcal D}}|\<{\mathbf r}^m,\phi\>|\ge \frac{|\<r^m,\Phi{\mathbf u}\>|}{\|{\mathbf u}\|_1},\quad {\mathbf u}\in{\mathbb R}^{\mathbb N},
 \end{equation}
\begin{equation}\label{Prp-2}
\<{\mathbf r}^m, \Phi{{{\mathbf u}}}\> = 0, \mbox{ if }\operatorname{supp}{{{\mathbf u}}}\subset T^m.
 \end{equation}
 In particular
 \begin{equation}\label{Prp-3}
\<{\mathbf r}^m, \Phi{\mathbf x}^m\> = 0.
 \end{equation}
 Using (\ref{Prp-1}) for ${\mathbf u} = {\mathbf w}_{\Omega\setminus T^m}$, we can estimate
\begin{eqnarray*}
|\sup_{\phi\in{\mathcal D}}\<{\mathbf r}^m,\phi\>| & \ge & \frac{|\<{\mathbf r}^m,\Phi{\mathbf w}_{\Omega\setminus T^m}\>|}{\|{\mathbf w}_{\Omega\setminus T^m}\|_1} \stackrel{(\ref{Prp-2})}{=} \frac{|\<{\mathbf r}^m,\Phi{\mathbf w}\>|}{\|{\mathbf w}_{\Omega\setminus T^m}\|_1}\\
& \stackrel{(\ref{Prp-3})}{=} &
\frac{|\<{\mathbf r}^m,\Phi({\mathbf w}-{\mathbf x}^m)\>|}{\|{\mathbf w}_{\Omega\setminus T^m}\|_1} \ge \frac{|\<{\mathbf r}^m,\Phi({\mathbf w}-x^m)\>|}{\|{\mathbf w}_{\Omega\setminus T^m}\|_0^{1/2}\|{\mathbf w}_{\Omega\setminus T^m}\|_2}.
 \end{eqnarray*}
Applying (\ref{Tl+cardinality}) and (\ref{w-def}), we obtain from the above inequality
\begin{equation}\label{WS-2mdf}
|\sup_{\phi\in{\mathcal D}}\<{\mathbf r}^m,\phi\>| \ge
\frac{|\<{\mathbf r}^m,\Phi({\mathbf w}-x^m)\>|}{(|\Gamma^m_+|)^{1/2}\|{\mathbf w}_{\Omega\setminus T^m}\|_2} \ge \frac{|\<{\mathbf r}^m,\Phi({\mathbf w}-x^m)\>|}{(aK)^{1/2}\|{\mathbf w}_{\Omega\setminus T^m}\|_2}.
 \end{equation}
We estimate
\begin{eqnarray*}
\|{\mathbf r}^m\|^2  & = & \|\Phi({\mathbf x}-{\mathbf x}^m)\|^2 \stackrel{RIP}{\ge} (1-\delta)\|{\mathbf x}-{\mathbf x}^m\|^2\ge(1-\delta)\|({\mathbf x}-{\mathbf x}^m)_{\Gamma^m}\|^2 \\
&= & (1-\delta)\|{\mathbf x}_{\Gamma^m}\|^2
= (1-\delta)\|{\mathbf x}_{\Gamma^m_+\cup \Gamma^m_-}\|^2
\\
& = &
(1-\delta)(\|{\mathbf x}_{\Gamma^m_+}\|^2 + \|{\mathbf x}_{\Gamma^m_-}\|^2)\stackrel{(\ref{Tl+def}),(\ref{Tl+cardinality})}{\ge} (1-\delta)((z^m)^2[aK] + \|{\mathbf x}_{\Gamma^m_-}\|^2),
 \end{eqnarray*}
and
\begin{equation*}
\|\Phi({\mathbf w}-{\mathbf x})\|^2\stackrel{(\ref{w-def})}{=}\|\Phi{\mathbf x}_{\Gamma^m_-}\|^2\stackrel{RIP}{\le} (1+\delta)\|{\mathbf x}_{\Gamma^m_-}\|^2.
 \end{equation*}
Combining two last inequalities, we obtain, for sufficiently large $K_0=K_0(a)=K_0(\epsilon)$,
\begin{eqnarray}
\|{\mathbf r}^m\|^2 - \|\Phi({\mathbf w}-{\mathbf x})\|^2 & \ge & (1-\delta)(z^m)^2[aK] -2\delta \|{\mathbf x}_{\Gamma^m_-}\|^2 \nonumber \\
& \stackrel{(\ref{Tl+def})}{\ge} & (1-\delta)(z^m)^2[aK] - 2\delta (z^m)^2|\Gamma^m_-| \nonumber \\
& \stackrel{(\ref{Tl-def})}{\ge} &
 (1-\delta)(z^m)^2[aK] - 2\delta (z^m)^2K \nonumber\\
 &\ge & (1-2\delta)(z^m)^2(aK) - 2\delta (z^m)^2K \nonumber\\
& = &(z^m)^2aK((1-2\delta)-\frac{2\delta}{a}) \nonumber\\
& \stackrel{(\ref{a-def})}{\ge} &  (z^m)^2aK(1- 4a). \label{diff-est}
 \end{eqnarray}

Following the technique from~\cite{WS}
we have
\begin{eqnarray}
|\<{\mathbf r}^m,\Phi({\mathbf w}-{\mathbf x}^m)\>| & = &
\frac{1}{2}\left|\|\Phi({\mathbf w}-{\mathbf x}^m)\|_2^2+ \|{\mathbf r}^m\|^2 -  \|\Phi({\mathbf w}-{\mathbf x}^m) - r^m\|^2\right|\nonumber\\
& \stackrel{(\ref{rmPhi})}{=}&
\frac{1}{2}\left|\|\Phi({\mathbf w}-{\mathbf x}^m)\|_2^2+ (\|{\mathbf r}^m\|^2 - \|\Phi({\mathbf w}-{\mathbf x})\|^2)\right|\nonumber\\
& \stackrel{(\ref{diff-est})}{\ge}&
\left(\|\Phi({\mathbf w}-{\mathbf x}^m)\|_2^2(z^m)^2aK(1-4a)\right)^{1/2}\nonumber \\
& = & \|\Phi({\mathbf w}-{\mathbf x}^m)\|_2 z^m(aK(1-4a))^{1/2}\nonumber\\
& \stackrel{RIP}{\ge} & (1-\delta)^{1/2}\|{\mathbf w}-{\mathbf x}^m\|z^m(aK(1-4a))^{1/2}\nonumber\\
& \ge & \|{\mathbf w}-{\mathbf x}^m\|z^m(aK)^{1/2}(1-c_1 a)\nonumber\\
& \ge &
\|({\mathbf w}-{\mathbf x}^m)_{\Omega\setminus T^m}\|z^m(aK)^{1/2}(1-c_1 a) \stackrel{(\ref{Tmdef})}{=}\nonumber\\
& = &\|{\mathbf w}_{\Omega\setminus T^m}\|z^m(aK)^{1/2}(1-c_1 a). \label{WS-3}
  \end{eqnarray}

Substituting  (\ref{WS-3}) in (\ref{WS-2mdf}) and (\ref{WS-1}), we finally get
\begin{eqnarray*}
\|{\mathbf r}^m\|^2 - \|{\mathbf r}^{m+1}\|^2 & \ge & \frac{\<{\mathbf r}^m,\Phi({\mathbf w}-{\mathbf x}^m)\>^2}{aK\|{\mathbf w}_{\Omega\setminus T^m}\|_2^2}\ge\frac{\|{\mathbf w}_{\Omega\setminus T^m}\|^2(z^m)^2aK(1-c_1a)^2}{aK\|{\mathbf w}_{\Omega\setminus T^m}\|_2^2}\\
& \ge &
(z^m)^2(1- C_1a).
 \end{eqnarray*}
 \end{proof}

 We continue to prove Theorem \ref{T2.1}.
Without loss of generality we may assume that $T=\{1,\ldots, K\}$ and that the sequence $\{|x_i|\}_{i = 1}^K$ decreases.
Then using the inequality $|T\cap T^m|\le m$ and the definition (\ref{zl-def}), we have
 \begin{equation*}
 z^m\ge |x_{m + [aK]}|\ge |x_{m + 1 + [aK]}|.
 \end{equation*}
Applying Lemma~\ref{lm-main}, we have for $m\ge 1$, $m + [aK] \le K$,
\begin{equation}\label{fromLmMain}
 \|{\mathbf r}^{m-1}\|^2 - \|{\mathbf r}^{m}\|^2 \ge (z^{m-1})^2(1-C_1a)\ge x_{m+[aK]}^2(1-C_1a).
 \end{equation}

First we bound $\|{\mathbf r}^K\|$ from above
 \begin{eqnarray}\label{rKUpper}
 \|{\mathbf r}^K\|^2 & = & \|{\mathbf r}^0\|^2 - \sum_{m = 1}^K\left(\|{\mathbf r}^{m-1}\|^2 - \|{\mathbf r}^{m}\|^2\right)\nonumber\\
   & \stackrel{({\mathbf r}^0=\Phi{\mathbf x})}{=} & \|\Phi {\mathbf x}\|^2 - \sum_{m=1}^K\left(\|{\mathbf r}^{m-1}\|^2 - \|{\mathbf r}^{m}\|^2\right)\nonumber \\
   & \stackrel{RIP}{\le} &
(1+\delta)\sum_{i=1}^K x_i^2 - \sum_{m=1}^{K-[aK]}\left(\|{\mathbf r}^{m-1}\|^2 - \|{\mathbf r}^{m}\|^2\right)\nonumber\\
 & \stackrel{(\ref{fromLmMain})}{\le} & (1+\delta)\sum_{i=1}^K x_i^2 - \sum_{m=1}^{K-[aK]}x_{m+[aK]}^2(1-C_1a)\nonumber\\
& \le & (1+\delta)\sum_{i=1}^K x_i^2 - \sum_{i=1 + [aK]}^{K}x_{i}^2(1-C_1a)\nonumber\\
& \le &
(\delta + C_1a) \sum_{i=1}^K x_i^2  +\sum_{i=1}^{[aK]} x_i^2 \nonumber \\
&\stackrel{|x_i|\le 1}{\le}& (\delta + C_1a)K + [aK] \le KC_2 a \stackrel{(\ref{a-def})}{=}KC_2\delta^{1/2} .
 \end{eqnarray}
Then using RIP, we can estimate $\|{\mathbf r}^K\|$ from below
 \begin{equation}\label{rKLower}
 \|{\mathbf r}^K\|^2 \ge (1-\delta)\sum_{i\in T\setminus T^K}x_i^2.
  \end{equation}
Set
\begin{equation*}
\widehat C:=\frac{C_2}{1-\delta}.
  \end{equation*}
Combining this definition with (\ref{rKUpper}) and (\ref{rKLower}), we obtain
 \begin{equation*}
\sum_{i\in T\setminus T^K}x_i^2 \le \widehat C K\delta^{1/2}.
  \end{equation*}
Thus, using (\ref{N-def}), we conclude that
 \begin{equation}\label{TTK-ineq}
|T\setminus T^K|\le N({\mathbf x},\widehat C K\delta^{1/2}).
  \end{equation}

It is known that (see Lemma 1.2 from \cite{CT} and Lemma 1 from \cite{CWX})
\begin{equation*}
 \delta_{2S}(\Phi)\le 3 \delta_{S}(\Phi).
\end{equation*}
Then the condition $\delta < 0.001$ implies that
 \begin{equation}\label{dt10K}
 \delta_{10K}(\Phi)\le \delta_{16K}(\Phi) \le 27 \delta_{2K}(\Phi)   \le 27\delta\le 0.03.
\end{equation}
Now we can apply the improvement of Zhang's theorem
obtained by Wang and Shim (\cite{WS}, Theorem 3.1). It claims that
under (\ref{dt10K}) we have
 \begin{equation*}
{\mathbf r}^{K + 6 |T\setminus T^K|} = 0,
\end{equation*}
Therefore, taking into account (\ref{TTK-ineq}), we finally get
 \begin{equation*}
{\mathbf r}^{K + 6 N({\mathbf x},\widehat C K\delta^{1/2})} = 0.
\end{equation*}

\end{proof}

As corollaries of Theorem~\ref{T2.1} we obtain Theorem~\ref{T1.1} and the following result.

\begin{Theorem}\label{T2.2} For any $\epsilon_1,\epsilon_2>0$ there exist $\delta=\delta(\epsilon_1,\epsilon_2)>0$ and $K_0 = K_0(\epsilon_1,\epsilon_2)$ such that for any dictionary ${\mathcal D}$, $\delta^{{RIP}}_{2K}({\mathcal D})<\delta$, $K\ge K_0$, the following statement holds. If ${\mathbf r}^0=f_0 \in\Sigma_K({\mathcal D})$ and its nonzero coefficients belong to $[-1,1]\setminus(-\epsilon_1,\epsilon_1)$, then ${\mathbf r}^{\lceil K(1+\epsilon_2)\rceil}=0$.
\end{Theorem}

\begin{proof}
It is clear that for any $\Lambda\subset T$ we have
 \begin{equation*}
\|{\mathbf x}_\Lambda\|^2 \ge \epsilon_1^2|\Lambda|.
\end{equation*}
Hence according to~(\ref{N-def}) we get
 \begin{equation*}
N({\mathbf x},\nu) \le\frac{\nu}{\epsilon_1^2}.
\end{equation*}
Then
 \begin{equation*}
6N({\mathbf x},\widehat C K \delta^{1/2}) \le K6\frac{\widehat C \delta^{1/2}}{\epsilon_1^2}.
\end{equation*}
Thus, to complete the proof it remains to choose $\delta=\delta(\epsilon_1,\epsilon_2)$ such that
 \begin{equation*}
6\frac{\widehat C \delta^{1/2}}{\epsilon_1^2} \le \epsilon_2.
\end{equation*}
\end{proof}

\begin{Lemma}\label{lm-prob} Assume that $p<1$ and numbers $x_i$, $1\le i\le K$, $K\ge K_0(p)$  are uniformly distributed on $[-1,1]$ independent random variables. Then
\begin{equation*}
\left|\{i: |x_i| <p\}\right| \le 2pK
\end{equation*}
 with  probability greater than $1-\operatorname{exp}(-C(p)K)$.
\end{Lemma}
\begin{proof}
For $i$, $1\le i\le K$, we set $\xi_i=0$, if $|x_i|\ge p$, and $\xi_i = 1$, otherwise.
So $\xi_i$ has Bernoulli distribution with
\begin{equation*}
\texttt{P}\{\xi_i=1\} = p,\quad \texttt{P}\{\xi_i=0\}=1-p,\quad \texttt{E}\xi_i = p.
\end{equation*}
By Hoeffding's inequality (see, for instance, \cite{Tbook}, p. 197) we obtain
$$
\texttt{P}\left\{\left|\frac{1}{K}\sum_{i=1}^K\xi_i-p\right|\ge p\right\} \le 2\operatorname{exp}(-Kp^2/2).
$$
Clearly,
$$
|\{i:  |x_i| <p\}| = \sum_{i=1}^K \xi_i.
$$
Therefore,
\begin{equation*}
\texttt{P}\left\{\left|\{i: |x_i| <p\}\right| \le 2p\right\}=\texttt{P}\left\{\frac{1}{K}\sum_{i=1}^K\xi_i\le 2p\right\} \ge 1- 2\operatorname{exp}(-Kp^2/2).
\end{equation*}

\end{proof}

We now give a proof of Theorem~\ref{T1.1} from the Introduction.
\begin{proof}
Let
\begin{equation*}
\varkappa := \varkappa(\delta):= \widehat C \delta^{1/2}.
\end{equation*}
According to Lemma~\ref{lm-main} with probability greater than $1-\operatorname{exp}(-C(\delta)K)$ we have
\begin{equation}\label{derivedfromprob}
\left|\{i: |x_i| <\varkappa^{1/3}\}\right| \le 2\varkappa^{1/3}K
\end{equation}
To prove the theorem we need to estimate $N({\mathbf x},\varkappa K)$. Consider $\Lambda\subset T$ such that
\begin{equation*}
\|{\mathbf x}_\Lambda\|^2\le\varkappa K.
\end{equation*}
Then we estimate
\begin{eqnarray*}
|\Lambda|& = & |\{i\in\Lambda: |x_i| < \varkappa^{1/3}\}| + |\{i\in\Lambda: |x_i| \ge \varkappa^{1/3}\}|\\
& \le &
|\{i\in\Lambda: |x_i| < \varkappa^{1/3}\}| +\frac{\varkappa K}{(\varkappa^{1/3})^2} \stackrel{(\ref{derivedfromprob})}{\le}
2\varkappa^{1/3}K + \varkappa^{1/3}K=3\varkappa^{1/3}K.
\end{eqnarray*}
Therefore, by definition (\ref{N-def}) we have
\begin{equation*}
  N({\mathbf x},\varkappa K)\le 3\varkappa^{1/3}K= 3(\widehat C)^{1/3}\delta^{1/6}K.
\end{equation*}
To complete the proof it remains to apply Theorem~\ref{T2.1} for $\delta<0.001$ providing
\begin{equation*}
N({\mathbf x},\varkappa K) <\epsilon K/6.
\end{equation*}

\end{proof}

\section{Lebesgue-type inequalities}

 We discuss here the Lebesgue-type inequalities for the WCGA with $\tau =\{t\}$, $t\in(0,1]$.   We repeat the above assumptions {\bf A1} and {\bf A2} with remarks on the corresponding properties of dictionaries.
 For a given $f_0$ let sparse element (signal)
 $$
 f:=f^\epsilon=\sum_{i\in T}x_ig_i
 $$
 be such that $\|f_0-f^\epsilon\|\le \epsilon$ and $|T|=K$. For $A\subset T$ denote
 $$
 f_A:=f_A^\epsilon := \sum_{i\in A}x_ig_i.
 $$

 Here are two assumptions that we will use.

 {\bf A1.} We say that $f=\sum_{i\in T}x_ig_i$ satisfies the Nikol'skii-type $\ell_1X$ inequality with parameter $r$ if
 \begin{equation}\label{C1}
 \sum_{i\in A} |x_i| \le C_1|A|^{r}\|f_A\|,\quad A\subset T,\quad r\ge 1/2.
 \end{equation}
 We say that a dictionary ${\mathcal D}$ has the Nikol'skii-type $\ell_1X$ property with parameters $K$, $r$   if any $K$-sparse element satisfies the Nikol'skii-type
 $\ell_1X$ inequality with parameter $r$.

{\bf A2.}  We say that $f=\sum_{i\in T}x_ig_i$ has incoherence property with parameters $D$ and $U$ if for any $A\subset T$ and any $\Lambda$ such that $A\cap \Lambda =\emptyset$, $|A|+|\Lambda| \le D$ we have for any $\{c_i\}$
\begin{equation}\label{C2}
\|f_A-\sum_{i\in\Lambda}c_ig_i\|\ge U^{-1}\|f_A\|.
\end{equation}
We say that a dictionary ${\mathcal D}$ is $(K,D)$-unconditional with a constant $U$ if for any $f=\sum_{i\in T}x_ig_i$ with
$|T|\le K$ inequality (\ref{C2}) holds.

The term {\it unconditional} in {\bf A2} is justified by the following remark. The above definition of $(K,D)$-unconditional dictionary is equivalent to the following definition. Let ${\mathcal D}$ be such that any subsystem of $D$ distinct elements $e_1,\dots,e_D$ from ${\mathcal D}$ is linearly independent and for any $A$ with $|A|\le K$ and any coefficients $\{c_i\}$ we have
$$
\|\sum_{i\in A}c_ie_i\| \le U\|\sum_{i=1}^Dc_ie_i\|.
$$

Let ${\mathcal D}$ be the Riesz dictionary with depth $D$ and parameter $\delta\in (0,1)$. This class of dictionaries is a generalization of the class of classical Riesz bases. We give a definition in a general Hilbert space (see \cite{Tbook}, p. 306).
\begin{Definition}\label{D3.1} A dictionary ${\mathcal D}$ is called the Riesz dictionary with depth $D$ and parameter $\delta \in (0,1)$ if, for any $D$ distinct elements $e_1,\dots,e_D$ of the dictionary and any coefficients $a=(a_1,\dots,a_D)$, we have
\begin{equation*}
(1-\delta)\|a\|_2^2 \le \|\sum_{i=1}^D a_ie_i\|^2\le(1+\delta)\|a\|_2^2.
\end{equation*}
We denote the class of Riesz dictionaries with depth $D$ and parameter $\delta \in (0,1)$ by $R(D,\delta)$.
\end{Definition}
It is clear that the term Riesz dictionary with depth $D$ and parameter $\delta \in (0,1)$ is another name for a dictionary satisfying the Restricted Isometry Property with parameters $D$ and $\delta$. The following simple lemma holds.
\begin{Lemma}\label{L3.1} Let ${\mathcal D}\in R(D,\delta)$ and let $e_j\in {\mathcal D}$, $j=1,\dots, s$. For $f=\sum_{i=1}^s a_ie_i$ and $A \subset \{1,\dots,s\}$ denote
$$
S_A(f) := \sum_{i\in A} a_ie_i.
$$
If $s\le D$ then
$$
\|S_A(f)\|^2 \le (1+\delta)(1-\delta)^{-1} \|f\|^2.
$$
\end{Lemma}

Lemma \ref{L3.1} implies that if ${\mathcal D}\in R(D,\delta)$ then it is $(D,D)$-unconditional with a constant $U=(1+\delta)^{1/2}(1-\delta)^{-1/2}$.

We need the concept of cotype of a Banach space $X$. We say that $X$ has cotype $q\ge 2$ if for any finite number of elements $u_i\in X$ we have the inequality
$$
\left(\text{Average}_{\pm}\|\sum_{i}\pm u_i \|^q\right)^{1/q} \ge C_q\left(\sum_{i}\|u_i\|^q\right)^{1/q}.
$$
It is known that the $L_p$ spaces with $2\le p<\infty$ have cotype $q=p$ and $L_p$ spaces with $1< p\le 2$ have cotype $2$.
\begin{Remark}\label{R3.1} Suppose ${\mathcal D}$ is $(K,K)$-unconditional with a constant $U$. Assume that $X$ is of cotype $q$ with a constant $C_q$. Then ${\mathcal D}$ has the Nikol'skii-type $\ell_1X$ property with parameters $K,1-1/q$ and $C_1=2UC_q^{-1}$.
\end{Remark}
\begin{proof} Our assumption about $(K,K)$-unconditionality implies: for any $A$, $|A|\le K$, we have
$$
\|\sum_{i\in A} \pm x_i g_i\| =\|\sum_{i\in A_+}x_i g_i - \sum_{i\in A_-}x_i g_i\| \le 2U\|\sum_{i\in A} x_i g_i\|.
$$
Therefore, by $q$-cotype assumption
$$
\|\sum_{i\in A} x_i g_i\|^q \ge (2U)^{-q}C_q^q\sum_{i\in A}|x_i|^q.
$$
This implies
$$
\sum_{i\in A} |x_i| \le |A|^{1-1/q}\left(\sum_{i\in A}|x_i|^q\right)^{1/q} \le 2UC_q^{-1}|A|^{1-1/q}\|\sum_{i\in A} x_i g_i\|.
$$
\end{proof}
The above proof also gives the following individual function version of Remark \ref{R3.1}.
\begin{Remark}\label{R3.2} Suppose $f=\sum_{i\in T}x_ig_i$ has incoherence property with parameters $D$ and $U$. Assume that $X$ has cotype $q$ with a constant $C_q$. Then $f$ satisfies the Nikol'skii-type $\ell_1X$ inequality with parameter $r=1-1/q$ and $C_1=2UC_q^{-1}$.
\end{Remark}
It is known that a Hilbert space has cotype $2$. Therefore, Remark \ref{R3.2} shows that assumption {\bf A2} implies assumption {\bf A1} with $r=1/2$. This explains how Theorem \ref{T1.6} is derived from Theorem \ref{T1.5}.

We note that the $(K,CK)$-unconditionality assumption on the dictionary ${\mathcal D}$ in a Hilbert space $H$ is somewhat weaker than the assumption ${\mathcal D}\in R(CK,\delta)$. Also, our theorems do not assume that the dictionary satisfies
assumptions {\bf A1} and {\bf A2}; we only assume that the individual function $f$,   a $K$-sparse approximation of a given $f_0$, satisfies {\bf A1} and {\bf A2}.

In assumption (\ref{C2}) we always have $U\ge 1$. In the extreme case $U=1$ assumption (\ref{C2}) is a strong assumption that leads to strong results.
\begin{Proposition}\label{P3.1} Let $X$ be a uniformly smooth Banach space. Assume that $f=\sum_{i\in T}x_ig_i$,  $|T|=K$, and the set of indices $T$ has the following property. For any $g\in{\mathcal D}$ distinct from $g_i$, $i\in T$, and any $c_i$, $c$ we have
\begin{equation}\label{3.2}
\|\sum_{i\in T}c_ig_i-cg\|\ge \|\sum_{i\in T}c_ig_i\|.
\end{equation}
Then the WCGA with $t_k\neq 0$, $k=1,2,\dots$, recovers $f$ exactly after $K$ iterations.
\end{Proposition}
\begin{proof} It is known (see, for instance, \cite{Tbook}, Lemma 6.9, p. 342) that (\ref{3.2}) implies
$$
F_f(g)=0,\qquad g\in {\mathcal D}\setminus\{g_i\}_{i\in T}.
$$
Thus, at the first iteration the WCGA picks $\varphi_1\in \{g_i\}_{i\in T}$. Then $f_1$ has the form $\sum_{i\in T}c_ig_i$ and we repeat the above argument. Then $\varphi_2\in \{g_i\}_{i\in T}\setminus \{\varphi_1\}$. After $K$ iterations all $g_i$, $i\in T$, will be taken and therefore we will have $f_K=0$.
\end{proof}

Proposition \ref{P3.1} can be applied in the following situation. Assume that $\Psi=\{\psi_i\}_{i=1}^\infty$ is a monotone basis for a uniformly smooth Banach space $X$. Then any $f=\sum_{i=1}^K x_i\psi_i$ will be recovered by the WCGA after $K$ iterations.
In particular, this applies to the Haar basis in $L_p$, $1<p<\infty$.

We now proceed to main results of this section.

\begin{Theorem}\label{T3.1} Let $X$ be a Banach space with $\rho(u)\le \gamma u^2$. Suppose for a given $f_0$ we have $\|f_0-f^\epsilon\|\le \epsilon$ with $K$-sparse $f:=f^\epsilon$ satisfying {\bf A1} and {\bf A2}. Then for any $k\ge 0$ we have for $K+m \le D$
$$
\|f_m\| \le \|f_k\|\operatorname{exp}\left(-\frac{c_1(m-k)}{K^{2r}}\right) +2\epsilon,
$$
where $c_1:= \frac{t^2}{32\gamma C_1^2 U^2}$.
\end{Theorem}
\begin{proof}  Let
$$
 f:=f^\epsilon=\sum_{i\in T}x_ig_i,\quad |T|=K,\quad g_i\in {\mathcal D}.
 $$
 Denote by $T^m$ the set of indices of $g_i$ picked by the WCGA after $m$ iterations, $\Gamma^m := T\setminus T^m$.
 Denote by $A_1({\mathcal D})$ the closure in $X$ of the convex hull of the symmetrized dictionary ${\mathcal D}^\pm:=\{\pm g,g\in D\}$.   We will bound  $\|f_m\|$ from above.  Assume $\|f_{m-1}\|\ge \epsilon$. Let $m>k$. We bound from below
 $$
 S_m:=\sup_{\phi\in A_1({\mathcal D})} |F_{f_{m-1}}(\phi)|.
 $$
 Denote $A_m:=\Gamma^{m-1}$. Then
 $$
 S_m \ge F_{f_{m-1}}(f_{A_m}/\|f_{A_m}\|_1),
 $$
 where $\|f_A\|_1 := \sum_{i\in A} |x_i|$. Next, by Lemma 6.9, p. 342, from \cite{Tbook} we obtain
 $$
 F_{f_{m-1}}(f_{A_m}) = F_{f_{m-1}}(f^\epsilon) \ge \|f_{m-1}\|-\epsilon.
 $$
 Thus
 $$
 S_m\ge \|f_{A_m}\|^{-1}_1(\|f_{m-1}\|-\epsilon).
 $$
 By (\ref{C1}) we get
 $$
 \|f_{A_m}\|_1 \le C_1 |A_m|^{r}\|f_{A_m}\| \le C_1 K^{r}\|f_{A_m}\| .
 $$
 Then
 \begin{equation}\label{3.4}
 S_m \ge \frac{\|f_{m-1}\|-\epsilon}{C_1 K^{r} \|f_{A_m}\|}.
 \end{equation}
 From the definition of the modulus of smoothness we have for any $\lambda$
\begin{equation}\label{3.4'}
\|f_{m-1}-\lambda \varphi_m \| +\|f_{m-1}+\lambda \varphi_m \| \le 2\|f_{m-1}\|\left(1+\rho\left(\frac{\lambda}{\|f_{m-1}\|}\right)\right)
\end{equation}
and by (1) from the definition of the WCGA and Lemma 6.10 from \cite{Tbook}, p. 343, we get
$$
|F_{f_{m-1}}(\varphi_m)| \ge t \sup_{g\in {\mathcal D}} |F_{f_{m-1}}(g)| =
$$
$$
t\sup_{\phi\in A_1({\mathcal D})} |F_{f_{m-1}}(\phi)|=tS_m.
$$
Then either $F_{f_{m-1}}(\varphi_m)\ge tS_m$ or $F_{f_{m-1}}(-\varphi_m)\ge tS_m$. Both cases are treated in the same way. We demonstrate the case $F_{f_{m-1}}(\varphi_m)\ge tS_m$. We have for $\lambda \ge 0$
$$
\|f_{m-1}+\lambda \varphi_m\| \ge F_{f_{m-1}}(f_{m-1}+\lambda\varphi_m)\ge  \|f_{m-1}\| + \lambda tS_m.
$$
From here and from (\ref{3.4'}) we obtain
 $$
 \|f_m\| \le \|f_{m-1}-\lambda \varphi_m\| \le \|f_{m-1}\| +\inf_{\lambda\ge 0} (-\lambda t S_m + 2\|f_{m-1}\|\rho(\lambda/\|f_{m-1}\|)).
 $$
 We discuss here the case $\rho(u) \le \gamma u^2$. Using (\ref{3.4}) we get
 $$
 \|f_m\| \le \|f_{m-1}\|\left(1-\frac{\lambda t}{C_1K^{r}\|f_{A_m}\|} +2\gamma \frac{\lambda^2}{\|f_{m-1}\|^2}\right) + \frac{\epsilon \lambda t}{C_1K^{r}\|f_{A_m}\|}.
 $$
 Let $\lambda_1$ be a solution of
 $$
 \frac{\lambda t}{2C_1K^{r}\|f_{A_m}\|} = 2\gamma \frac{\lambda^2}{\|f_{m-1}\|^2},\quad \lambda_1 = \frac{t\|f_{m-1}\|^2}{4\gamma C_1 K^{r}\|f_{A_m}\|}.
 $$
 Our assumption (\ref{C2}) gives
 \begin{eqnarray*}
 \|f_{A_m}\|&=&\|(f^\epsilon-G_{m-1})_{A_m}\| \le U\|f^\epsilon-G_{m-1}\|\\
 &\le&U(\|f_0-G_{m-1}\|+\|f_0-f^\epsilon\|) \le U(\|f_{m-1}\|+\epsilon).
 \end{eqnarray*}
 Specify
 $$
 \lambda = \frac{t \|f_{A_m}\|}{16\gamma C_1 K^{r} U^2}.
 $$
 Then, using $\|f_{m-1}\| \ge \epsilon$ we get
 $$
 \frac{\lambda}{\lambda_1} = \frac{\|f_{A_m}\|^2}{4\|f_{m-1}\|^2} \le 1
 $$
  and  obtain
 $$
 \|f_m\| \le \|f_{m-1}\| \left( 1- \frac{t^2}{32\gamma C_1^2 U^2 K^{2r}}\right) + \frac{\epsilon t^2}{16\gamma C_1^2 U^2K^{2r}}.
 $$
 Denote $c_1:= \frac{t^2}{32\gamma C_1^2 U^2}$. Then
 $$
 \|f_m\| \le \|f_{k}\|\operatorname{exp}\left(-\frac{c_1(m-k)}{K^{2r}}\right) + 2\epsilon.
 $$
\end{proof}

\begin{Theorem}\label{T3.2} Let $X$ be a Banach space with $\rho(u)\le \gamma u^2$. Suppose $K$-sparse $f^\epsilon$ satisfies {\bf A1}, {\bf A2} and $\|f_0-f^\epsilon\|\le \epsilon$. Then the WCGA with weakness parameter $t$ applied to $f_0$ provides
$$
\|f_{C(t,\gamma,C_1)U^2\ln (U+1) K^{2r}}\| \le CU\epsilon\quad\text{for}\quad K+C(t,\gamma,C_1)U^2\ln (U+1) K^{2r}\le D
$$
with an absolute constant $C$ and $C(t,\gamma,C_1) = C_2\gamma C_1^2 t^{-2}$.
\end{Theorem}
We formulate an immediate corollary of Theorem \ref{T3.2} with $\epsilon=0$.
\begin{Corollary}\label{C3.1} Let $X$ be a Banach space with $\rho(u)\le \gamma u^2$. Suppose $K$-sparse $f$ satisfies {\bf A1}, {\bf A2}. Then the WCGA with weakness parameter $t$ applied to $f$ recovers it exactly after $C(t,\gamma,C_1)U^2\ln (U+1) K^{2r}$ iterations under condition $K+C(t,\gamma,C_1)U^2\ln (U+1) K^{2r}\le D$.
\end{Corollary}

 \begin{proof} We use the above notations
   $T^m $ and  $\Gamma^m := T\setminus T^m$. Let $k\ge 0$ be fixed. Suppose
 $$
 2^{n-1} <|\Gamma^k| \le 2^n.
 $$
 For $j=1,2,\dots,n,n+1$ consider the following pairs of sets $A_j,B_j$: $A_{n+1}=\Gamma^k$, $B_{n+1}=\emptyset$; for $j\le n$, $A_j:=\Gamma^k\setminus B_j$ with $B_j\subset \Gamma^k$ is such that $|B_j|\ge |\Gamma^k|-2^{j-1}$ and for any set $J\subset \Gamma^k$ with $|J|\ge |\Gamma^k|-2^{j-1}$ we have
 $$
 \|f_{B_j}\| \le \|f_J\|.
 $$
 We note that this implies that if for some $Q\subset \Gamma^k$ we have
 \begin{equation}\label{3.5}
 \|f_Q\| <\|f_{B_j}\|\quad \text{then}\quad |Q|< |\Gamma^k|-2^{j-1}.
 \end{equation}

 For a given $b> 1$, to be specified later, denote by $L$ the index such that $(B_0:=\Gamma^k)$
 $$
 \|f_{B_0}\| < b\|f_{B_1}\|,
 $$
 $$
 \|f_{B_1}\| < b\|f_{B_2}\|,
 $$
 $$
 \dots
 $$
 $$
 \|f_{B_{L-2}}\| < b\|f_{B_{L-1}}\|,
 $$
 $$
 \|f_{B_{L-1}}\| \ge b\|f_{B_{L}}\|.
 $$
 Then
 \begin{equation}\label{3.6}
 \|f_{B_j}\| \le b^{L-1-j}\|f_{B_{L-1}}\|, \quad j=1,2,\dots,L.
 \end{equation}

  We now proceed to a general step. Let $m>k$ and let $A,B \subset \Gamma ^k$ be such that
 $ A=\Gamma^k\setminus B$. As above we bound $S_m$ from below. It is clear that $S_m\ge 0$.
 Denote $A_m := A\cap \Gamma^{m-1}$. Then
 $$
 S_m \ge F_{f_{m-1}}(f_{A_m}/\|f_{A_m}\|_1).
 $$
   Next,
 $$
 F_{f_{m-1}}(f_{A_m}) = F_{f_{m-1}}(f_{A_m}+f_B-f_B).
 $$
 Then $f_{A_m}+f_B=f^\epsilon - f_\Lambda$ with $F_{f_{m-1}}(f_\Lambda)=0$. Moreover, it is easy to see that $F_{f_{m-1}}(f^\epsilon)\ge\|f_{m-1}\|-\epsilon$. Therefore,
 $$
 F_{f_{m-1}}(f_{A_m}+f_B-f_B)\ge \|f_{m-1}\|-\epsilon - \|f_B\|.
 $$
 Thus
 $$
 S_m\ge \|f_{A_m}\|^{-1}_1\max(0,\|f_{m-1}\|-\epsilon-\|f_B\|).
 $$
 By (\ref{C1}) we get
 $$
 \|f_{A_m}\|_1 \le C_1 |A_m|^{r}\|f_{A_m}\| \le C_1 |A|^{r}\|f_{A_m}\| .
 $$
 Then
 \begin{equation}\label{3.7}
 S_m \ge \frac{\|f_{m-1}\|-\|f_B\|-\epsilon}{C_1 |A|^{r} \|f_{A_m}\|}.
 \end{equation}
 From the definition of the modulus of smoothness we have for any $\lambda$
$$
\|f_{m-1}-\lambda \varphi_m \| +\|f_{m-1}+\lambda \varphi_m \| \le 2\|f_{m-1}\|(1+\rho(\frac{\lambda}{\|f_{m-1}\|}))
$$
and by (1) from the definition of the WCGA and Lemma 6.10 from \cite{Tbook}, p. 343, we get
$$
|F_{f_{m-1}}(\varphi_m)| \ge t \sup_{g\in {\mathcal D}} |F_{f_{m-1}}(g)| =
$$
$$
t\sup_{\phi\in A_1({\mathcal D})} |F_{f_{m-1}}(\phi)|.
$$
 From here  we obtain
 $$
 \|f_m\| \le \|f_{m-1}\| +\inf_{\lambda\ge 0} (-\lambda t S_m + 2\|f_{m-1}\|\rho(\lambda/\|f_{m-1}\|)).
 $$
 We discuss here the case $\rho(u) \le \gamma u^2$. Using (\ref{3.7}) we get
 $$
 \|f_m\| \le \|f_{m-1}\|\left(1-\frac{\lambda t}{C_1|A|^{r}\|f_{A_m}\|} +2\gamma \frac{\lambda^2}{\|f_{m-1}\|^2}\right) + \frac{\lambda t(\|f_B\|+\epsilon)}{C_1 |A|^{r} \|f_{A_m}\|}.
 $$
 Let $\lambda_1$ be a solution of
 $$
 \frac{\lambda t}{2C_1|A|^{r}\|f_{A_m}\|} = 2\gamma \frac{\lambda^2}{\|f_{m-1}\|^2},\quad \lambda_1 = \frac{t\|f_{m-1}\|^2}{4\gamma C_1 |A|^{r}\|f_{A_m}\|}.
 $$
 Our assumption (\ref{C2}) gives
 $$
 \|f_{A_m}\| \le U(\|f_{m-1}\|+\epsilon).
 $$
 Specify
 $$
 \lambda = \frac{t \|f_{A_m}\|}{16\gamma C_1 |A|^{r} U^2}.
 $$
 Then $\lambda \le \lambda_1$ and we obtain
 \begin{equation}\label{3.8}
 \|f_m\| \le \|f_{m-1}\| \left( 1- \frac{t^2}{32\gamma C_1^2 U^2 |A|^{2r}}\right)+ \frac{ t^2 (\|f_B\|+\epsilon)}{16\gamma C_1^2 |A|^{2r} U^2}.
 \end{equation}
 Denote $c_1:= \frac{t^2}{32\gamma C_1^2 U^2}$ and $c_2:=\frac{t^2}{16\gamma C_1^2 U^2}$.
 This implies for $m_2>m_1\ge k$
 \begin{equation*}
 \|f_{m_2}\| \le \|f_{m_1}\| (1-c_1/|A|^{2r})^{m_2-m_1} + \frac{c_2(m_2-m_1)}{|A|^{2r}}(\|f_B\|+\epsilon).
 \end{equation*}
 Define $m_0:= k$ and, inductively,
 $$
 m_j=m_{j-1} + \beta |A_j|^{2r},\quad j=1,\dots,n.
 $$
 At iterations from $m_{j-1}+1$ to $m_j$ we use $A=A_j$ and obtain from (\ref{3.8}) that
 $$
 \|f_m\| \le \|f_{m-1}\|(1-u) + 2u(\|f_B\|+\epsilon),\quad u:= c_1|A|^{-2r}.
 $$
 Using $1-u\le e^{-u}$ and $\sum_{k=0}^\infty (1-u)^k = 1/u$ we derive from here
 $$
 \|f_{m_j}\| \le \|f_{m_{j-1}}\|e^{-c_1\beta}+ 2 (\|f_{B_j}\|+\epsilon).
 $$
 We continue it up to $j=L$. Denote $\eta:=e^{-c_1\beta}$. Then
 $$
 \|f_{m_L}\| \le \|f_k\|\eta^L +2 \sum_{j=1}^L (\|f_{B_j}\|+\epsilon)\eta^{L-j}.
 $$
 We bound the $\|f_k\|$. It follows from the definition of $f_k$ that $\|f_k\|$ is the error of best approximation of $f_0$ by the subspace $\Phi_k$. Representing $f_0=f+f_0-f$ we see that $\|f_k\|$ is not greater than  the error of best approximation of $f$ by the subspace $\Phi_k$ plus $\|f_0-f\|$. This implies $\|f_k\|\le \|f_{B_0}\| +\epsilon$. Therefore using (\ref{3.6}) we continue
 $$
 \le (\|f_{B_0}\|+\epsilon)\eta^L +2\sum_{j=1}^L (\|f_{B_{L-1}}\|(\eta b)^{L-j} b^{-1} + \epsilon\eta^{L-j})
 $$
 $$
 \le b^{-1}\|f_{B_{L-1}}\|\left( (\eta b)^L + 2 \sum_{j=1}^L (\eta b)^{L-j}\right) + \frac{2\epsilon}{1-\eta}.
 $$
We will specify $\beta$ later. However, we note that it will be chosen in such a way that guarantees $\eta< 1/2$. Choose $b=\frac{1}{2\eta}$. Then
 \begin{equation}\label{3.10}
 \|f_{m_L}\| \le \|f_{B_{L-1}}\|8  e^{-c_1\beta}+4\epsilon.
 \end{equation}

 By (\ref{C2}) we get
 $$
 \|f_{\Gamma^{m_L}}\| \le U(\|f_{m_L}\|+\epsilon) \le U(\|f_{B_{L-1}}\|8 e^{-c_1\beta} + 5\epsilon).
 $$
 If $\|f_{B_{L-1}}\|\le 10U \epsilon$ then by (\ref{3.10})
 $$
 \|f_{m_L}\| \le CU\epsilon.
 $$
 If $\|f_{B_{L-1}}\|\ge 10U\epsilon$ then
 making $\beta$ sufficiently large to satisfy $16U e^{-c_1\beta }<1$ so that $\beta = \frac{C_3\ln (U+1)}{c_1}$,  we get
 $$
 U(\|f_{B_{L-1}}\|8e^{-c_1\beta} +5\epsilon)< \|f_{B_{L-1}}\|
 $$
 and therefore
 $$
 \|f_{\Gamma^{m_L}}\|<\|f_{B_{L-1}}\|.
 $$
 This implies (see (\ref{3.5})
 $$
 |\Gamma^{m_L}| < |\Gamma^k| - 2^{L-2}.
 $$
   We begin with $f_0$ and apply the above argument (with $k=0$). As a result we either get the required inequality or we reduce the cardinality of support of $f$ from $|T|=K$ to $|\Gamma^{m_{L_1}}|<|T|-2^{L_1-2}$, $m_{L_1}\le \beta 2^{2rL_1}$. We continue the process and build a sequence $m_{L_j}$ such that $m_{L_j}\le \beta 2^{2rL_j}$ and after $m_{L_j}$ iterations we reduce the support by at least $2^{L_j-2}$. We also note that $m_{L_j}\le \beta 2^{2r} K^{2r}$. We continue this process till the following inequality is satisfied for the first time
 \begin{equation}\label{3.11}
  m_{L_1}+\dots+m_{L_n}  \ge 2^{4r}\beta K^{2r}.
 \end{equation}
 Then, clearly,
 $$
  m_{L_1}+\dots+m_{L_n} \le 2^{4r+1}\beta  K^{2r}.
 $$
 Using the inequality
 $$
 (a_1+\cdots +a_n)^{\theta} \le a_1^\theta+\cdots +a_n^\theta,\quad a_j\ge 0,\quad \theta\in (0,1]
 $$
 we derive from (\ref{3.11})
 $$
 2^{L_1-2}+\dots+2^{L_n-2} \ge \left(2^{2r(L_1-2)}+\dots+2^{2r(L_n-2)}\right)^{\frac{1}{2r}}
 $$
 $$
 \ge
 2^{-2}\left(2^{2rL_1}+\dots+2^{2rL_n}\right)^{\frac{1}{2r}}
 $$
 $$
 \ge 2^{-2}\left((\beta)^{-1}(m_{L_1}+\dots+m_{L_n})\right)^{\frac{1}{2r}}\ge K.
 $$
 Thus, after not more than $N:=2^{4r+1}\beta  K^{2r}$ iterations we recover $f$ exactly and then $\|f_N\| \le \|f_0-f\|\le \epsilon$.

 \end{proof}

  Theorem \ref{T1.5} from the Introduction follows from Theorems \ref{T3.2} and \ref{T3.1}.

\section{Discussion}

We begin with presenting some known results about exact recovery and the Lebesgue-type inequalities for incoherent dictionaries.
In this case we use another natural generalization of the WOMP. This generalization of the WOMP was introduced in \cite {T23}. In the paper \cite{ST} we proved Lebesgue-type inequalities for that algorithm. We now formulate the corresponding results.  We recall a generalization of the concept of $M$-coherent dictionary to the case of Banach spaces (see, for instance, \cite{Tbook}).

Let ${\mathcal D}$ be a dictionary in a Banach space $X$.  The coherence parameter of this dictionary is defined as
$$
M({\mathcal D}):= \sup_{g\neq h;g,h\in{\mathcal D}}\sup_{F_g}|F_g(h)|.
$$
In general, a norming functional $F_g$ is not unique. This is why we take $\sup_{F_g}$ over all norming functionals of $g$ in the definition of $M({\mathcal D})$. We do not need $\sup_{F_g}$ in the definition of $M({\mathcal D})$ if for each
$g\in{\mathcal D}$ there is a unique norming functional $F_g\in X^*$. Then we define ${\mathcal D}^*:=\{F_g,g\in{\mathcal D}\}$ and call ${\mathcal D}^*$ a {\it dual dictionary} to a dictionary ${\mathcal D}$.
 It is known that the uniqueness of the norming functional $F_g$ is equivalent to the property that $g$ is a point of Gateaux smoothness:
 $$
 \lim_{u\to 0}(\|g+uy\|+\|g-uy\|-2\|g\|)/u =0
 $$
 for any $y\in X$. In particular, if $X$ is uniformly smooth then $F_f$ is unique for any $f\neq 0$. We considered in \cite{T23} the following greedy algorithm which generalizes the Weak Orthogonal Greedy Algorithm to a Banach space setting.

 {\bf Weak Quasi-Orthogonal Greedy Algorithm (WQOGA).}
 Let $t\in (0,1]$ and $f_0$ be given.   Find $\varphi_1:=\varphi_1^{q,t}\in{\mathcal D}$ (here and below index $q$ stands for {\it quasi-orthogonal}) such that
 $$
 |F_{\varphi_1}(f_0)| \ge t\sup_{g\in {\mathcal D}}|F_g(f_0)|.
 $$
 Next, we find $c_1$ satisfying
 $$
 F_{\varphi_1}(f-c_1\varphi_1)=0.
 $$
 Denote $f_1:=f_1^{q,t}:=f-c_1\varphi_1$.

 We continue this construction in an inductive way. Assume that we have already constructed residuals $f_0,f_1,\dots,f_{m-1}$ and dictionary elements $\varphi_1,\dots,\varphi_{m-1}$. Now, we pick an element
 $\varphi_m:=\varphi_m^{q,t}\in{\mathcal D}$ such that
 $$
 |F_{\varphi_m}(f_{m-1})| \ge t\sup_{g\in {\mathcal D}}|F_g(f_{m-1})|.
 $$
 Next, we look for $c_1^m,\dots,c_m^m$ satisfying
 \begin{equation}\label{1.1}
 F_{\varphi_j}(f-\sum_{i=1}^mc_i^m\varphi_i)=0,\quad j=1,\dots,m.
 \end{equation}
If there is no solution to (\ref{1.1}) then we stop, otherwise we denote $G_m:=G_m^{q,t} := \sum_{i=1}^mc_i^m\varphi_i$ and $f_m:=f_m^{q,t}:=f-G_m $ with $c_1^m,\dots,c_m^m$ satisfying (\ref{1.1}).

\begin{Remark}\label{R1.1} Note that (\ref{1.1}) has a unique solution if
  $\det (F_{\varphi_j}(\varphi_i))_{i,j=1}^m \neq 0$. Applying the WQOGA in the case of a dictionary with the coherence parameter $M:=M({\mathcal D})$ gives, by a simple well known argument on the linear independence of the rows of the matrix $(F_{\varphi_j}(\varphi_i))_{i,j=1}^m$, the conclusion  that (\ref{1.1}) has a unique solution for any $m<1+1/M$.
 Thus, in the case of an $M$-coherent
dictionary ${\mathcal D}$, we can run the WQOGA for at least $[1/M]$ iterations.
\end{Remark}

In the case $t=1$ we call the WQOGA the Quasi-Orthogonal Greedy Algorithm (QOGA). In the case of QOGA we need to make an extra assumption that the corresponding maximizer $\varphi_m\in{\mathcal D}$ exists. Clearly, it is the case when ${\mathcal D}$ is finite.

It was proved in \cite{T23} (see also \cite{Tbook}, p. 382) that the WQOGA is as good as the WOMP in the sense of exact recovery of sparse signals with respect to incoherent dictionaries. The following result was obtained in \cite{T23}.
 \begin{Theorem}\label{T1.2} Let $t\in (0,1]$. Assume that ${\mathcal D}$ has coherence parameter $M$. Let $K<\frac{t}{1+t}(1+1/M)$. Then for any
 $f_0$ of the form
 \begin{equation*}
 f_0=\sum_{i=1}^Ka_ig_i,
 \end{equation*}
 where $g_i$ are distinct elements of ${\mathcal D}$, the WQOGA recovers it exactly after $K$ iterations. In other words, $f^{q,t}_K=0$.
 \end{Theorem}
It is known (see  \cite{Tbook}, pp. 303--305) that the bound $K<\frac{1}{2}(1+1/M)$ is sharp for exact recovery by the OGA.

We introduce a new norm, associated with a dictionary ${\mathcal D}$,  by the formula
$$
\|f\|_{\mathcal D}:=\sup_{g\in{\mathcal D}}|F_g(f)|,\quad f\in X.
$$
  We define best $m$-term approximation in the norm $Y$ as follows
$$
\sigma_m(f)_Y := \inf_{g\in\Sigma_m({\mathcal D})}\|f-g\|_Y.
$$
In \cite{ST} the norm $Y$ was either the norm $X$ of our Banach space or the norm $\|\cdot\|_{\mathcal D}$ defined above.
 The following two Lebesgue-type inequalities were proved in \cite{ST}.
 \begin{Theorem}\label{T1.3} Assume that ${\mathcal D}$ is an $M$-coherent dictionary. Then for \newline $m\le \frac{1}{3M}$ we have for the QOGA
 \begin{equation}\label{1.3}
 \|f_m\|_{\mathcal D} \le 13.5\sigma_m(f)_{\mathcal D}.
 \end{equation}
 \end{Theorem}

 \begin{Theorem}\label{T1.4} Assume that ${\mathcal D}$ is an $M$-coherent dictionary in a Banach space $X$. There exists an absolute constant $C$   such that, for $m\le 1/(3M)$, we have for the QOGA
$$
\|f_m\|_X \le C \inf_{g\in\Sigma_m({\mathcal D})}(\|f-g\|_X + m\|f-g\|_{\mathcal D}).
$$
\end{Theorem}
\begin{Corollary}\label{C1.1} Using the inequality $\|g\|_{\mathcal D} \le \|g\|_X$,  Theorem \ref{T1.4} obtains
$$
\|f_m\|_X \le C(1+m) \sigma_m(f)_X.
$$
\end{Corollary}

Inequality (\ref{1.3}) is a perfect (up to a constant 13.5) Lebesgue-type inequality. It indicates that the norm $\|\cdot\|_{\mathcal D}$ used in \cite{ST} is a suitable norm for analyzing performance of the QOGA. Corollary \ref{C1.1} shows that the Lebesgue-type inequality (\ref{1.3}) in the norm $\|\cdot\|_{\mathcal D}$ implies the Lebesgue-type inequality in the norm $\|\cdot\|_X$.

Thus, results of this paper complement the above discussed results from \cite{T23} and \cite{ST}. Results from \cite{T23} and \cite{ST} deal with incoherent dictionaries and use the QOGA for exact recovery and the Lebesgue-type inequalities. Results of this paper deal with dictionaries which satisfy assumptions {\bf A1} and {\bf A2} and we analyze the WCGA here. In the case of a Hilbert space, assumptions {\bf A1} and {\bf A2} are satisfied if ${\mathcal D}$ has RIP. It is well known that the RIP condition is much weaker than the incoherence condition in the case of a Hilbert space. It is interesting to note that we do not know how the coherence parameter $M({\mathcal D})$ is related to properties {\bf A1} and {\bf A2} in the case of a Banach space.

We now give a few applications of Theorem \ref{T1.5} for specific dictionaries ${\mathcal D}$. We begin with the case when ${\mathcal D}$ is a basis $\Psi$ for $X$. In some of our examples we take $X=L_p$, $2\le p<\infty$. Then it is known that $\rho(u) \le \gamma u^2$ with $\gamma = (p-1)/2$.

{\bf Example 1.} Let $X$ be a Banach space with $\rho(u)\le \gamma u^2$ and with cotype $q$.
Let $\Psi$ be a normalized in $X$ unconditional basis for $X$. Then $U\le C(X,\Psi)$. By Remark \ref{R3.1} $\Psi$ satisfies {\bf A1} with $r=1-\frac{1}{q}$. Theorem \ref{T1.5} gives
\begin{equation}\label{4.3}
\|f_{C(t,X,\Psi)K^{2-2/q}}\| \le C\sigma_K(f_0,\Psi) .
\end{equation}
We note that (\ref{4.3}) provides some progress in Open Problem 7.1 (p. 91) from \cite{Tsurv}.

{\bf Example 2.} Let $\Psi$ be a uniformly bounded orthogonal system normalized in $L_p(\Omega)$, $2\le p<\infty$, $\Omega$ is a bounded domain. Then we can take $r=1/2$. The inequality
$$
\|g\|_p \le CK^{1/2-1/p}\|g\|_2
$$
for $K$-sparse $g$ implies that
$$
\|S_A(f)\|_p \le CK^{1/2-1/p}\|S_A(f)\|_2 \le CK^{1/2-1/p}\|f\|_2 \le CK^{1/2-1/p}\|f\|_p.
$$
Therefore $U\le CK^{1/2-1/p}$. Theorem \ref{T1.5} gives
 \begin{equation}\label{4.4}
\|f_{C(t,p,D)K^{2/p'}\ln K}\|_p \le C\sigma_K(f_0,\Psi)_p .
\end{equation}
Inequality (\ref{4.4}) provides some progress in Open Problem 7.2 (p. 91) from \cite{Tsurv}.

Theorem \ref{T1.5} can also be applied for quasi-greedy bases and other greedy-type bases (see \cite{Tbook}).
We plan to discuss these applications in detail in our future work.

In this paper we limit ourselves to the case of Banach spaces satisfying the condition $\rho(u)\le \gamma u^2$.
In particular, as we mentioned above the $L_p$ spaces with $2\le p<\infty$ satisfy this condition. Clearly, the $L_p$ spaces with $1<p\le 2$ are also of interest. For the clarity of presentation we do not discuss the case $\rho(u)\le \gamma u^q$ in this paper.
The technique from Section 3 works in this case too and we will present the corresponding results in our future work.

 \newpage

redpajama_set_name: RedPajamaArXiv


text:
Home Business Will the Matrix movie come about? … the largest computer chip in...
Will the Matrix movie come about? … the largest computer chip in the world that can simulate what will happen in the future
Researchers said a recent test of the world's largest computer chip found that it could predict what will happen in the future "faster than the laws of physics."
The Cerebras CS-1 chip, containing 1.2 trillion transistors, is 200 times faster than a supercomputer.
The chip was so powerful in analyzing more than a million variables from fluctuating temperatures to 3D air movement that it was able to show what could happen faster than in real time.
Carbras CS-1 was developed in partnership with the US Department of Energy's National Energy Technology Laboratory, which has been described as "the most powerful artificial intelligence computing system in the world." The number of transistors running on the chip is about 22 times that of the recently announced Nvidia A100 80GB chip, designed for the latest supercomputers.
"This work opens the door to major breakthroughs in scientific computing performance," said a blog for Carbras chip, adding that "Carbras CS-1 is the first system ever to demonstrate sufficient performance for faster-than-real time simulation. This means that when the chip is used to simulate a terminal." Energy based on data on current operating conditions, it can tell you what will happen in the future faster than the laws of natural physics produce the same result. "
The chip's immense computing power will be used to train neural networks and perform high-fidelity simulations of real-world scenarios, such as simulating the best way to land a helicopter on a surface by modeling airflow patterns around its propellers.
The company has also tapped into a second-generation chip containing 2.6 trillion transistors, which will pave the way for more complex simulations in the real world.
Computer simulation in Matrix style via a chip that can simulate many conditions and choose the best (communication sites)
This invention raises once again questions about computer simulation in the manner of "Matrix", which is the movie that talks about the existence of a chip that can simulate many conditions and choose the best ones, that can predict the future and the nature of existence by simulating millions of possibilities.
The simulation hypothesis, developed by philosopher Nick Bostrom in 2003, states that in the future enormous amounts of computing power will be used to run a realistic simulation of the universe.
This hypothesis has since been popularized by Elon Musk, who claimed that there is a 99.99% chance that the universe we live in is a computer simulation.
"40 years ago we had a pong game," Musk said at a 2016 conference, "Now we have a realistic 3D simulation game with millions of people playing simultaneously, which means millions of possibilities … if you assume you can apply this to life, then Games will become indistinguishable from reality. "
Realistic universe-wide simulations are still elusive and may not be possible with conventional computers. Nevertheless, advances in ultra-powerful quantum computers could provide a potential pathway for their creation.
Previous articleEl Chiringuito TV: Maradona died of cardiac arrest
Next articleWatch .. How FIFA 21 Will Get Better on PlayStation 5
Financial services .. Communication technology to verify identity papers – Economy – local
Samsung unveils the 870 Evo memory with 38% faster performance – UAE breaking news
General Motors announces a partnership with Microsoft in automated vehicles
"Etisalat" and "Du" are driving stocks to record profits – the economic – the UAE economy
Financial services .. Services of "Internet banks" – economy – local
US stocks closed higher on the eve of Biden's inauguration as President of the United States
The Qatar Investment Authority has made big returns from its bet on bad debt and highly rated bonds during the pandemic
WhatsApp continues its efforts to prevent users from migrating to other services – UAE Urgent News
International Energy: The new Coronavirus wave slows down the recovery in oil demand
Postponing the opening of "Disneyland Paris" due to the pandemic – our lives – destinations
Coffee produces a carbon footprint that matches greenhouse gas emissions, which is the worst
Wall Street rises with Yellen's stimulus and bank profits
Baraka is the culmination of a decade-long effort
TAQA's general assembly approves the distribution of 1.5 fils per share...
Intercept and destroy two ballistic missiles and 6 non-collapsing aircraft
News 24 | "Health": these categories are the most dangerous to...
Saudi "Samba" raises first half profits by 15% to 696 million...
Saad Mohamed, a cancer player with Zamalek, denies the rumor of...
Iraqi police reveals the truth about the injury of his star...
Tips for securing your files in Google Drive

redpajama_set_name: RedPajamaCommonCrawl


text:
Encyclopedias almanacs transcripts and maps
Hexham, Monastery of
Former monastery of benedictines, then Austin canons, at Hexham, in Northumbria, England. The Benedictine abbey there was founded c. 673 by wilfrid, Archbishop of York, and grew rapidly in importance. Five years after the foundation of the abbey, the church of Hexham became the cathedral of the new Diocese of Bernicia, but c. 821 this bishopric was united to that of lindisfarne. Hexham was destroyed in the course of the Danish invasions in the following century, but was rebuilt, probably in 1113, as a priory of canons regular of st. augustine. The priory was dissolved in 1536 under King henry viii, when the last prior was hanged for his involvement in the pilgrimage of grace. Today the town of Hexham is famous for the priory church, now the parish church of St. Andrew, which is all that remains of the monastery.
Bibliography: w. dugdale, Monasticon Anglicanum (London 1655–73); best ed. by j. caley et al., 6 v. (1817–30) 6.1:179–185. j. raine, ed., The Priory of Hexham, Its Chroniclers, Endowments, and Annals, 2 v. (Surtees Society 44 and 46; Durham 1864–65). c. c. hodges, Ecclesia Hagustaldensis. The Abbey of St. Andrew, Hexham (privately printed; London 1888). d. knowles and r. n. hadcock, Medieval Religious Houses: England and Wales (New York 1953) 140. d. knowles, The Monastic Order in England, 943–1216 (2d ed. Cambridge, Eng. 1962), passim. d. knowles, The Religious Orders in England, 3 v. (Cambridge, Eng. 1948–60).
[j. brÜckmann]
New Catholic Encyclopedia
"Hexham, Monastery of ." New Catholic Encyclopedia. . Encyclopedia.com. 12 Jan. 2021 <https://www.encyclopedia.com>.
"Hexham, Monastery of ." New Catholic Encyclopedia. . Encyclopedia.com. (January 12, 2021). https://www.encyclopedia.com/religion/encyclopedias-almanacs-transcripts-and-maps/hexham-monastery
"Hexham, Monastery of ." New Catholic Encyclopedia. . Retrieved January 12, 2021 from Encyclopedia.com: https://www.encyclopedia.com/religion/encyclopedias-almanacs-transcripts-and-maps/hexham-monastery
Lanfranc , civil law at Pavia he became a student of the liberal arts and theology under berengarius at his school in Tours (1035). He excelled in dialectic and… Fountains Abbey , Former Cistercian abbey, near Ripon, Yorkshire, England. Although the south and midland regions of England had been "monasticized" by the benedictine… Cambridge Platform , CAMBRIDGE PLATFORM Also known as the Platform of Church Discipline, it was framed by a synod held in Cambridge, Mass., in 1648. Representatives of th… George Wishart , WISHART, GEORGE Protestant reformer; b. c. 1510; d. St. Andrews, March 28, 1545 or 1546. Nothing is known with certainty of the parentage and early l… Recluse , RECLUSE Recluse, or an anchorite, or hermit, designates a religious–minded person who embraces the eremitical life in one of its most extreme forms,… Andrew Melville , MELVILLE, ANDREW Scottish Protestant divine; b. Baldovy, Aug. 1, 1545;d. Sedan, 1622. Melville was educated at Montrose grammar school and at the Uni…
Peterborough, Abbey of
DAVENTRY, PRIORY OF
Meaux (Melsa), Abbey of
SHERBORNE, ABBEY OF
Aelfric of Canterbury, St.
BARKING ABBEY
HYDE, ABBEY OF
Hexham abbey
Hexed
Hexcel Corporation
hexavalent
hexatonic
hexastyle
Hexasterophora
hexaster
hexaploidy
hexaphosphoinositol
Hexanchiformes (Six- and Sevengill Sharks)
Hexanchiformes
Hexanchidae
hexamic acid
hexamethylene tetramine
hexamerous
Hexaméron
hexahedron
hexose
hexose-monophosphate shunt
Hexter, J. H. ("Jack")
Hexter, Jack H.
hexuronic acid
Hey Good Lookin'
Hey There, It's Yogi Bear
Hey, Babu Riba
Hey, Happy!
Hey, Jeanne A. K.
Hey, Julius
Heyck, Denis Lynn Daly 1943-
Heyd, Uriel
Heyden (Heiden, Haiden), Hans
Heyden (Heiden, Haiden), Sebald
Heydenfeldt, Solomon
Heydon, John (1629-ca. 1668)
Heydrich, Reinhard (1904–1942)
Heydrich, Reinhard Tristan°
Heyen, William
Heyen, William (Helmuth)


Climb inside the 2019 Subaru Forester. It features all-wheel drive versatility, an automatic transmission, and a 2.5 liter 4 cylinder engine. Subaru prioritized practicality, efficiency, and style by including: adjustable headrests in all seating positions, a trip computer, power front seats, turn signal indicator mirrors, lane departure warning, blind spot sensor, and remote keyless entry. Features such as automatic climate control and leather upholstery prove that economical transportation does not need to be sparsely equipped. Rear passengers enjoy the seat heating functionality, keeping them warm during the winter months. For drivers who enjoy the natural environment, a power moon roof allows an infusion of fresh air. Premium sound drives 9 speakers, providing you and your passengers a sensational audio experience. Subaru also prioritized safety and security with features such as: dual front impact airbags, front side impact airbags, traction control, brake assist, a security system, an emergency communication system, and 4 wheel disc brakes with ABS. Various mechanical systems are monitored by electronic stability control, keeping you on your intended path. We pride ourselves on providing excellent customer service. Please don't hesitate to give us a call.


text:
Home Papal Library Biography - Pope Boniface VIII - The Papal Library
Papal Library
Rerum Novarum Leo XIII May 12, 2021
Christus Dominus Pius XII April 19, 2021
Arcanum Leo XIII April 19, 2021
Biography - Pope Boniface VIII - The Papal Library
Boniface VIII1294-1303 Benedict Gaetani born 1235 Boniface VIII was born at Anagni. He was successively canon of Todi, of Paris, of Lyons, and the Vatican Basilica, consistorial advocate, and apostolical prothonotary. On the 12th of April, 1281, he was created cardinal by Martin IV; then Nicholas IV named him cardinal-priest of Saints Sylvester and Martin. Martin IV, who knew him to be a man of talent, dexterity, and fidelity, sent him as legate Charles of Sicily, to prevent him from warring against the King of Aragon, and to keep the subjects of both kings in their devotion to the Roman court. He was afterwards sent with another cardinal to restore peace between King Philip of France and Edward of England, and to defend the rights of the Church in both countries. Nicholas IV deputed him, with other cardinals, to inquire into and arrange the differences between Denis, King of Portugal, and the clergy of that kingdom. After these many signal services Cardinal Gaetani was unanimously elected pope on the 24th of December, 1294, at Castel Nuovo, near the city of Naples, where the cardinals were assembled in conclave. After accepting the pontificate on the 2nd of January, 1295, he, in company with Charles II, King of Sicily, and Charle Martel, his son, King of Hungary, set out for Rome, where he was consecrated and crowned by Cardinal Matthew Roar Orsini, the first deacon, on the 16th of the month of January. When he went to the Basilica of Saint John Lateran he rode a magnificent palfrey, of which the two kings held bridle-reins. They also, wearing their crowns, presented him at table with the first two dishes, and then seated selves at the cardinals' table. The first cares of Boniface were directed to the pacification of Italy. He reduced Sicily to obedience to the Holy See, and he succeeded in restoring a sufficient concord between the kings of France and England. He dissuaded the king of the Romans from his intention of attacking France, and sought means to destroy all the factions that divided the Christian princes. New efforts were made to reunite the Greeks to the faith; and, finally, every effort was made to aid in the recovery of the Holy Land, from which the Catholics had been driven by the Mussulmans. At the conclusion of a peace between Charles II of Naples and the King of Aragon, Charles swore fidelity to Pope Boniface in the Church of Saint Sabina. In the year 1295 Boniface ordered the feasts of the Holy Evangelists and of the four Doctors of the Church—Gregory, Augustine, Ambrose, and Jerome-to be celebrated as doubles. He ordered that at Rome there should be for the future a general academy of all the faculties. Boniface, perceiving that some princes oppressed the clergy with imposts, published, on the 21st of September, 1296, a bull, which he caused to be inserted in the sixth book the Decretals, to remedy that evil. The clauses of the bull were singularly softened for France, at the request of some of the prelates of the kingdom. The sixth book, entitled the Sexte, was printed at Mainz in 1465, folio. The bull in question is called Clericis laicos. In it the pope says: Antiquity shows us the enmity of laymen against the clergy, and our experience in the present time manifestly supports that teaching, since, without considering that they have no power over the persons or the property of ecclesiastics, the laity lay imposts upon the prelates and the clergy, both regular and secular; and we grieve to say that some prelates and other ecclesiastics, having more fear of the temporal majesty than of the eternal, acquiesce in that abuse. That we may obviate this, we order that all the prelates and ecclesiastics, regular or secular, who pay to the laymen tithes or any other portion of their revenues, under the name of aid, subvention, or any other, without the authority of the Holy See, and the kings, princes, and magistrates, and all others who shall impose such burdens, or who shall give aid and counsel thereto, shall incur excommunication, absolution from which is reserved to the Holy See, notwithstanding any privilege. Fleury adds: The aversion of the laity to the clergy, which the pope speaks of at the outset, goes back to no ancient date, for during the first five or six centuries the clergy attracted universal respect and affection by a charitable and disinterested conduct. Boniface, being at Orvieto on the 11th of August, 1297, canonized Louis IX, King of France, who died at Tunis on the 25th of August, 1270. He says: At length Boniface determined that King Louis should be included among the saints. He delivered two sermons upon the subject at Orvieto, the first in his palace, the Tuesday before Saint Laurence, that is to say, on the 6th of August, 1297, and in them summed up the proceedings preliminary to the canonization. Among other things he said: 'Pope Nicholas III affirmed that the virtues of that saint were so well known to him he would have canonized him if he had seen two or three miracles.' And again: 'The matter has been so often inquired into that the documents about it are more than an ass could carry.' Boniface delivered the other sermon in the church of the Friars Minor, in Orvieto, on the same day that he published the bull of canonization, which was the 11th of August. The bull, which is dated on the same day and addressed to all the bishops of France, gives an abridged life of the saint, with many of his miracles, and orders his feast to be celebrated on the anniversary of his death, the morrow of Saint Bartholomew, that is to say, the 25th of August. It was in the year 1297 that quarrels between the pope and the Colonna family began to appear. He confiscated their palace, condemned them as schismatics, compelled them to leave Rome, and took the purple from James and Peter, belonging to that illustrious family. The Colonnas had done evil to the Church. They had circulated a manifesto which affirmed that Celestine had no power to renounce the pontificate, and that Boniface, consequently, could not be legitimately elected. The two cardinals having appealed to the clemency of Boniface, he granted their pardon, released them from the interdict, and restored them to their dignity. Led away by bad advice, the two cardinals again revolted. Boniface again condemned them. But there was too much severity in the order to raze the town of Palestrina. At the same time it was astonishing that at that very moment Boniface published a constitution which, like one that had been published by Honorius III, punished all who sacrilegiously wronged the cardinals of the Holy Roman Church. The Holy Father perceived that at the close of the century a great number of pilgrims arrived at Rome, because their fathers had told them that every hundred years, at the close of the century, they ought to visit the tomb of the apostles to acquire the benefits of the jubilee. In the year 1300, therefore, he did not institute, but renewed that plenary indulgence. He ordered the feast to be renewed every hundred years; Clement V ordered that it should be every fifty years; Urban VI, every thirty-three years; and, finally, Paul II ordered that it should take place every fifty years, which is the present arrangement, excepting some irremediable cause of prevention arise, as was the case in the year 1800. At the jubilee of the year 1300 there was an immense concourse of pilgrims. Boniface ordained that to obtain the benefits of the jubilee the Romans should visit Saint Peter's and Saint Paul's thirty times and the pilgrims only fifteen times. In 1301 the differences between Philip the Fair and the pope were still further envenomed because the pope confirmed the bull by which he forbade ecclesiastics to pay anything to laymen without the apostolical authorization. Philip then confirmed a former decree prohibiting the sending of any money to Rome. One of the king's partisans, William of Nogaret, a fiery magistrate, accused the pope of simony, magic, and atheism; and the bishops, theologians, and doctors who would not embrace the party of the king were exiled. Philip even went so far as to forbid all the prelates of his kingdom to attend a council about to be held in Italy. The pope, being at Rome on the 6th of November, is said to have published there the celebrated constitution, Unam Sanctam, in which, in order to re-establish the papal authority, oppressed by the councillors of the king, he declared it to be heretical to say that any Christian is not subject to the pope; and he excommunicated those who had prohibited the prelates from going to Rome. Neither at Rome nor elsewhere is the bull, Unam Sanctam, or In Coena Domini, any longer officially mentioned. In 1303 Boniface founded at Rome the university commonly known as the Sapienza. The usage of cloistering nuns was very ancient, as is proved by the fourth century, nevertheless it was not generally recognized. Boniface made it a law for all nuns in Christendom. In 1303 there were disturbances in Rome, and the pope deemed it prudent to retire to Anagni. But Sciarra Colonna, his irreconcilable enemy, and William of Nogaret, Philip's councillor, after corrupting some of the servants of the court and many of the principal inhabitants of the city, entered Rome at the head of armed men, shouting: Death to Pope Boniface! Long live the King of France! They then attacked the palace of the pontiff, and found him seated on his throne, in his pontifical attire, with the crown on his head, and holding in his hand the keys of the Church. It was Boniface who added to the tiara a second circle or crown. The unfortunate pope was abandoned by all his court, except the cardinals of Sabina, Peter of Spain, of Ostia, and Bonasini, who was his successor. The invaders pillaged the treasury, and left the pope, still clad as we have described, under the guard of some soldiers, after having insulted him. Nogaret even threatened to take him to France as a prisoner and to have him deposed by a general council. At that threat the magnanimous pontiff replied: We shall be well content to be deposed by Patarini [heretic Albigenses] such as you are, and such as were your father and mother, who were punished as such. Novaes says not a word about Sciarra Colonna having struck the pope in the face with his gauntlet. Feller thinks the blow was given. The Biographie Universelle says on the subject: Some historians add that Colonna carried his brutality so far as to strike the pope on the cheek with his gauntlet. Fortunately for the memory of Colonna, there is still some doubt as to this excess, which would have been dastardly as well as inhuman against an unarmed and aged man. After so cruel and ignoble an attack, the inhabitants of Anagni, who had not interfered, repented of their ingratitude to their compatriot and their sovereign, who had heaped benefits upon them. Suddenly, stimulated by the Cardinal Luca Fieschi, they rushed to arms, attacked the pope's enemies, who were few in number, put them to flight, and took prisoner Nogaret himself, whom the pope ordered to be treated gently. Hearing of that success, Boniface, with unheard-of clemency, set Nogaret at liberty, and he retired without suffering the penalty of his crime. The pope, finding himself free, determined to return to Rome. But he was so violently shocked by these insults and sacrileges that, thirty days after, on the 11th of October, 1303, he died from the excitement he had suffered. He had governed eight years, nine months, and eighteen days. Boniface was a man of remarkable qualities. He showed himself to be a consummate jurisconsult, a man of elevated ideas, and an intrepid conservator of the rights of the Church. So Saint Antoninus describes him. It was affirmed that, frenzied with grief, he had gnawed his own flesh; but on the 11th of October, 1605, three hundred years after his death, he was found in his tomb without the least sign of decomposition, and with the flesh entirely uninjured. This biographical data is from The Lives and Times of the Popes by The Chevalier Artaud De Montor. Published by The Catholic Publication Society of New York in ten volumes in 1911. The pictures, included in the volumes, were reproduced from Effigies Pontificum Romanorum Dominici Basae.


Another fairly quiet winter weekend; great for the soul. On Friday night after work Dave made some homemade pizzas that were waiting for us when we got home. Then we watched The Grinch (the new cartoon one).
On Saturday morning we were up early to get the boys out the door for skiing. After they left, Q watched a couple of episodes of Paw Patrol before we went to swimming. He is all snuggled up on the couch under his blanket.
Saturday outfit - new sweatshirt and leggings.
The pool at swimming was colder than usual so Q was not overly thrilled to be there, but he eventually got into it and liked jumping off the side. After we left swimming we picked up our grocery order and then got a few things on Bloor.
Meanwhile it was race day at the ski hill and E came in third place!
While Q napped (for three hours), I cleaned the house and prepared for our dinner guests. We were having chili with various toppings - cheese, chips, sour cream, avocado, cilantro, and green onion.
A few snacks to start us off.
When I moved them over to the table, Q was very interested.
The kids are ready to eat.
On Sunday morning we woke up to a surprise snowfall. I had gone to bed at 10:30 and there had been no sign of snow; we were surprised at how much there was. We all went out to shovel.
I took the boys to church where we were celebrating the anniversary of being an affirming ministry (which means we welcome people of all walks of life, specifically those in the LGBTQ community). There was a lovely rainbow flag hung at the front.
And we got to have rainbow cupcakes afterwards!
In the afternoon, Q went to nap, I did some reading, and E worked on his math app on the iPad.
Dave came home after picking up his parents at the train station, and we just hung out for the rest of the afternoon. They also went sledding while I got supper ready. I finished up my night with yoga.


Bezel set with 60 diamonds weighing a total of +/- 0.85 carats.
Eggshell (ivory/off-white) colored dial, with a very fine sunray finish.
Date sub-dial at the 6 o'clock position.
Moonphase aperture at the center of the date sub-dial.
Jaeger LeCoultre Caliber 925/1, measures only 4.90mm thick, oscillating rotor with a 22 carat gold weight component, beats at 28,800 vph, composed out of 253 parts, contains 30 Jewels & has an approximate power reserve of 43 hours.


text:
AoC News, Writing
Photo by Camilo Jimenez
It's funny, because I think every single previous iteration of the Army of Cats site has had a blog so it's not really anything new. I've always had a space to write, to document process, or to share other folks' work or just ideas I like.
Even before I created artwork for a living, I had a LiveJournal which I updated for years. It was really quite formative and allowed me to make an arse of myself trying out different artistic voices as well as making random online friends. Thankfully, in a rare moment of wisdom, long ago, when my lj days came to a natural end I deleted the account – after saving all my years of juvenile ramblings in a secret PDF file…
After that came a Blogger page, then a short-lived run with a thing called Posterous, before finally settling on good old WordPress, a platform I've really grown to like and – a rarity these days – actually trust.
For the past few years I've been content to use the various social media platforms to post day-to-day content and, while my 'engagement' isn't bad, I'm just finding it more and more draining. Twitter in particular feels like a place you have to wade into rather than a nice, open space of creativity and discourse.
I'm tired of the adverts, tired of feeling like I'm battling algorithms, tired of constantly having to re-select 'show latest posts', and tired of spaces that essentially just aren't mine.
As the brilliant Austin Kleon puts it on his own blog:
Maybe I'm weird, but it just feels good. It feels good to reclaim my turf. It feels good to have a spot to think out loud in public where people aren't spitting and shitting all over the place."
Perhaps you feel similarly?
I've actually found myself really enjoying visiting other people's blogs again. There's a cosiness and an informality to people's own spaces, particularly when they're documenting some slightly weird, niche interest.
Model-maker's blogs, record collector's blogs, or blogs where someone is just scanning in old punk zines and flyers. I love stuff like that! It's a reminder that the web as a platform was built by individuals, not just massive corporations (I remember when the Google search page had a 'Blog' button, showing you results only from blogs…).
So, here we are, a quieter, clearer space for me to document work and ideas.
I will, of course, still be posting in the usual places but I'll be putting the real effort in here and linking back to it when I can.
Thanks for reading and see you next time.
Next Post	The Dissolutions EP Artwork
CATEGORIES Select Category AoC News (9) Design (11) Events (2) Illustration (2) Process (7) Quotes (1) Screenprinting (12) Sketchbook (2) Videos (5) Writing (2)
ARCHIVES Select Month December 2021 September 2021 August 2021 May 2021 February 2021 January 2021 December 2020 November 2020 October 2020 September 2020 August 2020 July 2020 June 2020 May 2020
Based in Yorkshire, UK, Army of Cats is the studio name for the creative output of graphic artist Graham Pilling. Image Maker. Silkscreen printer. Fell runner. Cat wrangler. Coffee Drinker.
AoC News (9)
Screenprinting (12)
Copyright © 2022 Graham Pilling / Army of Cats Creative Studio / All Rights Reserved -- Powered by Creative Themes
Instagram	YouTube	Twitter	Facebook	Flickr


Our client was an established USA based medical device company that was seeking to expand its pipeline of new products. We were asked to undertake a technology scouting assignment to identify potential new surgical product / technology opportunities that were a good fit with the company's mechanical /electrical engineering manufacturing capabilities and its current sales channels. The brief was to cast the net wide geographically and to generate a 'long-list' of opportunities that could then be further investigated to generate a 'short-list' for engagement with the owners. Alacramed used its wide network of contacts in the medical device industry, together with personal knowledge and internal and external databases to find new opportunities for the client.


Swifts are in trouble, with their breeding numbers plummeting.
The 51% decrease in their breeding numbers in the UK between 1995 and 2015 has made swifts an amber-listed species.
Why are their breeding numbers plummeting?
We believe loss of nest sites is at least partly responsible. These migrant birds return from their wintering grounds in Africa to the same spot each year to breed – usually in buildings, in gaps under roof tiles and eaves.
Due to our tendency to seal up buildings during renovation or knock them down, swifts are returning to discover their nest site has gone or access is blocked.
The swift is one of the last summer migrants to arrive in the UK and the first to leave. 'Screaming' calls reveal the presence of parties of swifts flying above towns.
Many individuals and local authorities are already doing a lot for swifts. Some examples can be found on the Swift Conservation and Action for Swifts websites.
Are your swifts under threat?
Many established swift colonies are being lost through building demolition, renovation and roof repair.
Tell us about the swifts your see, or don't see!
Your information will help our knowledge of swifts so that more nest sites can be provided and protected. Tell us where you see swifts and help us to help them.
We'd like to find out where swifts are seen and where they're nesting. Watch out for screaming groups of swifts flying at roof-height (that means they're breeding nearby), or where you've seen swifts nesting – perhaps entering a roof or hole in a building.
You don't need to report sightings of swifts that are either very high in the sky, feeding over water bodies or away from villages, towns and cities. These birds could have travelled some distance and may not be local breeding birds.
The best time to look is around dusk on a warm, still evening, or early morning. And if you can see the nest, it's not a swift's. June and July are the best months to look for screaming swifts, around dusk or early morning. These are likely to be young birds pairing up for the first time looking for potential nest sites.
We'd like to know where you've seen screaming swifts or swift nest sites.
You can enter as many records as you like at different times. We need sightings from anywhere across the UK. You can even tell us those sightings you remember from the past – the more records, the better.
If you have sent in records before, it's important to know if birds are still returning to the same areas. Please tell us what's happening there this year. This helps us know if the birds are returning, if the colony is stable and if the site is still in use.
Every year we ask you to record sightings of low-level roof-height screaming parties of swifts and their nest sites. But what are we doing with your swift survey submissions?
These pages illustrate some of the great work already being undertaken around the country to protect swifts against loss of nest sites, and to help this enigmatic bird by providing new ones.
Listen to a special podcast exploring Swift Survey 2018, delving into the science behind your sightings.
There are lots of ways to help swifts!
Why not set up a nestbox to give swifts a place to nest and breed year after year. Take part in our High home for swifts activity.
A swifts average daily flight distance.
Parent swifts can collect up to this many insects in a day.
The top speed of the fastest proven swift flight.


text:
How Europe can better tackle rising cancer incidence
In her letter to the new EU Health Commissioner Stella Kyriakides, President-elect of the EU executive Ursula von der Leyen said an EU-wide "Beating Cancer" plan should be put forward in order to help member states improve cancer prevention and care. [Shutterstock]
Cancer, the second leading cause of death globally according to the World Health Organisation, is responsible for an estimated 9.6 million deaths in 2018.
In light of projections that the cancer incidents in Europe will double by 2035, a new survey conducted by Central and Eastern European Cancer Action Group (CEECAG), has identified large differences between Europe's west and central and eastern countries in handling cancer.
In her mission letter to the proposed new EU Health Commissioner Stella Kyriakides, the President-elect of the EU executive, Ursula von der Leyen, said an EU-wide "Beating Cancer" plan should be put forward in order to help member states improve cancer prevention and care.
"This should propose actions to strengthen our approach at every key stage of the disease: prevention, diagnosis, treatment, life as a cancer survivor and palliative care. There should be a close link with the research mission on cancer in the future Horizon Europe programme," von der Leyen wrote.
Report finds serious East-West divide in cancer handling in Europe
News | Diabetes, Cancer, Hepatitis 13-09-2019
A new survey conducted by the Central and Eastern European Cancer Action Group (CEECAG) has found severe shortcomings in managing cancer incidents in Central and Eastern Europe (CEE), whose "young brains" increasingly move to the west.
Health expert: Cancer control plans must be implemented
The governments should take full responsibility for the implementation of national cancer plans, which are a commitment toward people and not just a piece of paper, health expert Dr Tit Albreht told EURACTIV.com in an interview.
How patients' involvement brings quality to cancer care and policymaking
Medical experts and stakeholders from patient advocacy groups are keen to point out how crucial it is to consider patients' voice as an added value when conducting cancer clinical trials, whatever policy on cancer, national or EU-wide, will eventually be put together.
Center-right MEPs call for special EU Parliament committee on cancer
The European People's Party (EPP), the biggest political group in the EU assembly, will ask for the creation of a special parliamentary committee to help formulate a new EU-wide plan to combat cancer. EURACTIV.com and EURACTIV.cz report from Strasbourg.
Eastern Europe diversity should be considered in EU-wide cancer plan
Having a pan-European cancer control plan is crucial, but some flexibility should be granted to member states in choosing which aspect to prioritise within the framework, said Linda Gibbs from Pfizer Oncology in an interview with EURACTIV.com.
Tackling disparities in cancer care across the central and eastern European region
Opinion | Promoted content | Health 27-09-2019
Despite encouraging advances in science and technology, cancer rates continue to rise across the world. The International Agency for Research on Cancer (IARC) estimates that one-in-five men and one-in-six women worldwide will develop cancer over the course of their lifetime, …
Tweets by @PfizerEUPolicy
Follow @PfizerEUPolicy