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.

  • 1
    $\begingroup$ 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 $\endgroup$ Nov 4, 2012 at 14:22
  • $\begingroup$ Thanks, I have this paper and I read, but still I have problems $\endgroup$ Nov 4, 2012 at 14:36
  • $\begingroup$ i meant give references like this paper so that others know what you're talking about $\endgroup$ Nov 4, 2012 at 16:09
  • 1
    $\begingroup$ Edited to correct grammar/readability issues. Please double-check that I haven't changed the meaning. What does "PGA" stand for? $\endgroup$
    – Jeffε
    Nov 4, 2012 at 20:44
  • $\begingroup$ Thanks for editing, meaning haven't changed. "PGA" stands for Pure Greedy Algorithm $\endgroup$ Nov 4, 2012 at 21:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.