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
.
Statement of the lemma
[edit] Let
and let
be a countable index set. Let
be any sequence indexed by
, and for
let
be the indices of the
largest terms of the sequence
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}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6af966b91805014b29d0f0577dc01ec43a5ea86b)
where
.
Thus, Stechkin's lemma controls the ℓq norm of the tail of the sequence
(and hence the ℓq norm of the difference between the sequence and its approximation using its
largest terms) in terms of the ℓp norm of the full sequence and an rate of decay.
W.l.o.g. we assume that the sequence
is sorted by
and we set
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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d154077f2edcc62489dc6def7ced5eeb93b89c7)
Now, we notice that for
![{\displaystyle |a_{i}|\leq |a_{dN}|,\quad {\text{for}}\quad i=dN+1,\dots ,(d+1)N;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68ea1c35d1a47228643af155ea00e69f363151ab)
![{\displaystyle |a_{dN}|\leq |a_{j}|,\quad {\text{for}}\quad j=(d-1)N+1,\dots ,dN;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f20ed1dd7df386ee12e76dce150d9f28acf41358)
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/64023462d93deb4614552a08ff687244e7ff7cf2)
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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b9bd659f4e0a1291869c63ceb0cc95c1d6abf79)
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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/54759e247fa13ae57746fc3347b24b751df2784b)
Putting all these ingredients together completes the proof.