Stechkin's lemma explained

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 < inf ty and let I be a countable index set. Let (a _{i} ) _{i} be any sequence indexed by I , and for N \in N let I _{N} \subset I be the indices of the N largest terms of the sequence (a _{i} ) _{i} in absolute value. Then\left( \sum _{i \in I \setminus I _{N}} | a _{i} | ^{q} \right) ^{1/q} \leq \left( \sum _{i} | a _{i} | ^{p} \right) ^{1/p} (1)/(N ^{r})

where

r = (1)/(p) - (1)/(q) > 0 .

Thus, Stechkin's lemma controls the ℓ^q norm of the tail of the sequence

(a _{i} ) _{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} is sorted by |a _{i+1} | \leq |a _{i} |, i \in I and we set I = N for notation.

First, we reformulate the statement of the lemma to

\left( (1)/(N) \sum _{i \in I \setminus I _{N}} | a _{i} | ^{q} \right) ^{1/q} \leq \left( (1)/(N) \sum _{j} | a _{j} | ^{p} \right) ^{1/p} .

Now, we notice that for

d \in N |a _{i|} \leq |a _{dN} |, for i = dN +1 , ... , (d +1 )N; |a _{dN} | \leq |a _{j|,} for j = (d -1 )N +1 , ... , dN;

Using this, we can estimate

\left( (1)/(N) \sum _{i \in I \setminus I _{N}} | a _{i} | ^{q} \right) ^{1/q} \leq \left( (1)/(N) \sum _{d} N | a _{dN} | ^{q} \right) ^{1/q} = \left( \sum _{d} | a _{dN} | ^{q} \right) ^{1/q} as well as\left( \sum _{d} | a _{dN} | ^{p} \right) ^{1/p} = \left( (1)/(N) \sum _{d} N | a _{dN} | ^{p} \right) ^{1/p} \leq \left( (1)/(N) \sum _{i \in I \setminus I _{N}} | a _{i} | ^{p} \right) ^{1/p} .

Also, we get by norm equivalence:

\left( \sum _{d} | a _{dN} | ^{q} \right) ^{1/q} \leq \left( \sum _{d} | a _{dN} | ^{p} \right) ^{1/p} .

Putting all these ingredients together completes the proof.

References

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