# Pure Greedy algorithms

I study pure greedy algorithms in different bases. I am interested in the following question: Is there such a Riesz basis $D$ in Hilbert space and $f\in H$ such that $$\|f-G_m(f,D)\| > Cm^{-1/2} |f|_H$$ for every constant $C$? In other words, is there a Riesz basis that yields a convergence rate bigger than $-1/2$?

I know that there are such dictionaries whose convergence rate is larger than $-1/2$ (even $-0.27$) but I cannot construct such a Riesz basis.

Note: A Pure Greedy Algorithm is defined inductively by \begin{align*} G_0(f) & = 0 \\ G_m(f) & = G_{m-1}(f)+G(f-G_{m-1}(f)) \end{align*} where $G(f)=\langle f,g\rangle g$ and $g=g(f)$ is an element from $D$ that maximizes $\left|\langle f,g\rangle\right|$.

Here are some ideas that might be helpful. It is known that if $$\sup_{g\in D} \sum_{g'\in D,~ g'\ne g} \left|\langle g,g'\rangle\right| < 1/3,$$ then the convergence rate is less than $-1/2$. That is why I took Riesz basis for which that supremum is equal to 1: $$D=(f_j), ~\text{where}~ f_j=e_j+\frac{1}{2}e_{j+1}.$$ Now I want to find $f$. But I can not :(

Some useful information can be found in this paper by DeVore and Temlyakov and this paper by Temlyakov.

• you might want to give some references and define your notation an terminology. i am guessing this link for example is useful: mosaic.math.tamu.edu/~rdevore/publications/91.pdf Nov 4, 2012 at 14:22
• Thanks, I have this paper and I read, but still I have problems Nov 4, 2012 at 14:36
• i meant give references like this paper so that others know what you're talking about Nov 4, 2012 at 16:09
• Edited to correct grammar/readability issues. Please double-check that I haven't changed the meaning. What does "PGA" stand for? Nov 4, 2012 at 20:44
• Thanks for editing, meaning haven't changed. "PGA" stands for Pure Greedy Algorithm Nov 4, 2012 at 21:29