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 ${\displaystyle q=2}$.

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

${\displaystyle \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

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

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

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

First, we reformulate the statement of the lemma to

${\displaystyle \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 ${\displaystyle d\in \mathbb {N} }$

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

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

Using this, we can estimate

${\displaystyle \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

${\displaystyle \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:

${\displaystyle \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.

• 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.