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 [math]\displaystyle{ q = 2 }[/math].

Statement of the lemma

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

[math]\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}} }[/math]

where

[math]\displaystyle{ r = \frac{1}{p} - \frac{1}{q} \gt 0 }[/math].

Thus, Stechkin's lemma controls the ℓ^q norm of the tail of the sequence [math]\displaystyle{ (a_{i})_{i \in I} }[/math] (and hence the ℓ^q norm of the difference between the sequence and its approximation using its [math]\displaystyle{ N }[/math] 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 [math]\displaystyle{ (a_{i})_{i \in I} }[/math] is sorted by [math]\displaystyle{ |a_{i+1}| \leq |a_{i}|, i \in I }[/math] and we set [math]\displaystyle{ I= \mathbb{N} }[/math] for notation.

First, we reformulate the statement of the lemma to

[math]\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}. }[/math]

Now, we notice that for [math]\displaystyle{ d \in \mathbb{N} }[/math]

[math]\displaystyle{ |a_i| \leq |a_{dN}|, \quad \text{for} \quad i=dN+1, \dots, (d+1)N; }[/math]

[math]\displaystyle{ |a_{dN}| \leq |a_j|, \quad \text{for} \quad j=(d-1)N+1, \dots, dN; }[/math]

Using this, we can estimate

[math]\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} }[/math]

as well as

[math]\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}. }[/math]

Also, we get by ℓ^p norm equivalence:

[math]\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}. }[/math]

Putting all these ingredients together completes the proof.

References

• Schneider, Reinhold; Uschmajew, André (2014). "Approximation rates for the hierarchical tensor format in periodic Sobolev spaces". Journal of Complexity 30 (2): 56–71. doi:10.1016/j.jco.2013.10.001. ISSN 0885-064X.  See Section 2.1 and Footnote 5.