<p>I study pure greedy algorithms in different bases.  I am interested in the following question:  Is there such a <a href="http://math.gmu.edu/~dwalnut/teach/Math772/Fall11/772f11lec11.pdf" rel="nofollow">Riesz basis</a> $D$ in Hilbert space and $f\in H$ such that
$$
    \|f-G_m(f,D)\| &gt; 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$?</p>

<p>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.</p>

<p><strong>Note:</strong> A Pure Greedy Algorithm is defined inductively by
\begin{align*}
  G_0(f) &amp; = 0 \\
  G_m(f) &amp; = 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|$.</p>

<p>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| &lt; 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 :(</p>

<p>Some useful information can be found in <a href="http://mosaic.math.tamu.edu/~rdevore/publications/91.pdf" rel="nofollow">this paper by DeVore and Temlyakov</a> and <a href="http://www.icm2006.org/proceedings/Vol_II/contents/ICM_Vol_2_70.pdf" rel="nofollow">this paper by Temlyakov</a>.</p>

CC BY-SA 3.0
2012-11-04T14:22:38.873Z
you might want to give some references and define your notation an terminology. i am guessing this link for example is useful: http://mosaic.math.tamu.edu/~rdevore/publications/91.pdf
Sasho Nikolov
CC BY-SA 3.0
2012-11-04T14:36:31.697Z
Thanks, I have  this paper and I read, but still I have problems
Studentmath
CC BY-SA 3.0
2012-11-04T16:09:06.903Z
i meant give references like this paper so that others know what you're talking about
Sasho Nikolov
CC BY-SA 3.0
2012-11-04T20:44:49.773Z
Edited to correct grammar/readability issues.  Please double-check that I haven't changed the meaning.  What does "PGA" stand for?
Jeffε
CC BY-SA 3.0
2012-11-04T21:29:51.413Z
Thanks for editing, meaning haven't changed. "PGA" stands for Pure Greedy Algorithm
Studentmath
<ds.algorithms><greedy-algorithms>
Pure Greedy algorithms
Studentmath
# Pure Greedy algorithms

(Asked by: username_0 on 2012-11-04)

I study pure greedy algorithms in different bases. I am interested in the following question: Is there such a [Riesz basis](http://math.gmu.edu/~dwalnut/teach/Math772/Fall11/772f11lec11.pdf) $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](http://mosaic.math.tamu.edu/~rdevore/publications/91.pdf) and [this paper by Temlyakov](http://www.icm2006.org/proceedings/Vol_II/contents/ICM_Vol_2_70.pdf).

**Tags:** ds.algorithms, greedy-algorithms
> **Comments:**
> **username_1**: you might want to give some references and define your notation an terminology. i am guessing this link for example is useful: http://mosaic.math.tamu.edu/~rdevore/publications/91.pdf  
> **username_0**: Thanks, I have  this paper and I read, but still I have problems  
> **username_1**: i meant give references like this paper so that others know what you're talking about  
> **username_2**: Edited to correct grammar/readability issues.  Please double-check that I haven't changed the meaning.  What does "PGA" stand for?  
> **username_0**: Thanks for editing, meaning haven't changed. "PGA" stands for Pure Greedy Algorithm  

---

## 0 answers

