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}$.

Statement of the lemma

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