Stechkin's lemma

In mathematics – more specifically, in functional analysis and numerical analysis – Stechkin's lemma is a result about the ℓ^q norm of the tail of a sequence, when the whole sequence is known to have finite ℓ^p norm. Here, the term "tail" means those terms in the sequence that are not among the N largest terms, for an arbitrary natural number N. Stechkin's lemma is often useful when analysing best-N-term approximations to functions in a given basis of a function space. The result was originally proved by Stechkin in the case $q=2$.

Statement of the lemma

Let $0<p<q<\infty$ and let $I$ be a countable index set. Let $(a_{i})_{i\in I}$ be any sequence indexed by $I$, and for $N\in \mathbb {N}$ let $I_{N}\subset I$ be the indices of the $N$ largest terms of the sequence $(a_{i})_{i\in I}$ in absolute value. Then

$\left(\sum _{i\in I\setminus I_{N}}|a_{i}|^{q}\right)^{1/q}\leq \left(\sum _{i\in I}|a_{i}|^{p}\right)^{1/p}{\frac {1}{N^{r}}}$

where

$r={\frac {1}{p}}-{\frac {1}{q}}>0$.

Thus, Stechkin's lemma controls the ℓ^q norm of the tail of the sequence $(a_{i})_{i\in I}$ (and hence the ℓ^q norm of the difference between the sequence and its approximation using its $N$ largest terms) in terms of the ℓ^p norm of the full sequence and an rate of decay.

Proof of the lemma

W.l.o.g. we assume that the sequence $(a_{i})_{i\in I}$ is sorted by $|a_{i+1}|\leq |a_{i}|,i\in I$ and we set $I=\mathbb {N}$ for notation.

First, we reformulate the statement of the lemma to

$\left({\frac {1}{N}}\sum _{i\in I\setminus I_{N}}|a_{i}|^{q}\right)^{1/q}\leq \left({\frac {1}{N}}\sum _{j\in I}|a_{j}|^{p}\right)^{1/p}.$

Now, we notice that for $d\in \mathbb {N}$

$|a_{i}|\leq |a_{dN}|,\quad {\text{for}}\quad i=dN+1,\dots ,(d+1)N;$

$|a_{dN}|\leq |a_{j}|,\quad {\text{for}}\quad j=(d-1)N+1,\dots ,dN;$

Using this, we can estimate

$\left({\frac {1}{N}}\sum _{i\in I\setminus I_{N}}|a_{i}|^{q}\right)^{1/q}\leq \left({\frac {1}{N}}\sum _{d\in \mathbb {N} }N|a_{dN}|^{q}\right)^{1/q}=\left(\sum _{d\in \mathbb {N} }|a_{dN}|^{q}\right)^{1/q}$

as well as

$\left(\sum _{d\in \mathbb {N} }|a_{dN}|^{p}\right)^{1/p}=\left({\frac {1}{N}}\sum _{d\in \mathbb {N} }N|a_{dN}|^{p}\right)^{1/p}\leq \left({\frac {1}{N}}\sum _{i\in I\setminus I_{N}}|a_{i}|^{p}\right)^{1/p}.$

Also, we get by ℓ^p norm equivalence:

$\left(\sum _{d\in \mathbb {N} }|a_{dN}|^{q}\right)^{1/q}\leq \left(\sum _{d\in \mathbb {N} }|a_{dN}|^{p}\right)^{1/p}.$

Putting all these ingredients together completes the proof.

References

• Schneider, Reinhold; Uschmajew, André (2014). "Approximation rates for the hierarchical tensor format in periodic Sobolev spaces". Journal of Complexity. 30 (2): 56–71. CiteSeerX 10.1.1.690.6952. doi:10.1016/j.jco.2013.10.001. ISSN 0885-064X. See Section 2.1 and Footnote 5.