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<\mathrm{\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

${(\sum _{i\in I\setminus I_N}|a_i{|}^q)}^{1/q}\le {(\sum _{i\in I}|a_i{|}^p)}^{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}|\le |a_i|,i\in I$ and we set $I=\mathbb{N}$ for notation.

First, we reformulate the statement of the lemma to

${(\frac{1}{N}\sum _{i\in I\setminus I_N}|a_i{|}^q)}^{1/q}\le {(\frac{1}{N}\sum _{j\in I}|a_j{|}^p)}^{1/p}.$

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

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

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

Using this, we can estimate

${(\frac{1}{N}\sum _{i\in I\setminus I_N}|a_i{|}^q)}^{1/q}\le {(\frac{1}{N}\sum _{d\in \mathbb{N}}N|a_{dN}{|}^q)}^{1/q}={(\sum _{d\in \mathbb{N}}|a_{dN}{|}^q)}^{1/q}$

as well as

${(\sum _{d\in \mathbb{N}}|a_{dN}{|}^p)}^{1/p}={(\frac{1}{N}\sum _{d\in \mathbb{N}}N|a_{dN}{|}^p)}^{1/p}\le {(\frac{1}{N}\sum _{i\in I\setminus I_N}|a_i{|}^p)}^{1/p}.$

Also, we get by Template:Math norm equivalence:

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

Putting all these ingredients together completes the proof.

References

• Template:Cite journal See Section 2.1 and Footnote 5.