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.

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.