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 {\displaystyle q=2} .
Statement of the lemma Let 0 < p < q < ∞ {\displaystyle 0<p<q<\infty } and let I {\displaystyle I} be a countable index set. Let ( a i ) i ∈ I {\displaystyle (a_{i})_{i\in I}} be any sequence indexed by I {\displaystyle I} , and for N ∈ N {\displaystyle N\in \mathbb {N} } let I N ⊂ I {\displaystyle I_{N}\subset I} be the indices of the N {\displaystyle N} largest terms of the sequence ( a i ) i ∈ I {\displaystyle (a_{i})_{i\in I}} in absolute value. Then
( ∑ i ∈ I ∖ I N | a i | q ) 1 / q ≤ ( ∑ i ∈ I | a i | p ) 1 / p 1 N r {\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
r = 1 p − 1 q > 0 {\displaystyle 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 ∈ I {\displaystyle (a_{i})_{i\in I}} (and hence the ℓq norm of the difference between the sequence and its approximation using its N {\displaystyle N} largest terms) in terms of the ℓp norm of the full sequence and a rate of decay.
Proof of the lemma W.l.o.g. we assume that the sequence ( a i ) i ∈ I {\displaystyle (a_{i})_{i\in I}} is sorted by | a i + 1 | ≤ | a i | , i ∈ I {\displaystyle |a_{i+1}|\leq |a_{i}|,i\in I} and we set I = N {\displaystyle I=\mathbb {N} } for notation. First, we reformulate the statement of the lemma to
( 1 N ∑ i ∈ I ∖ I N | a i | q ) 1 / q ≤ ( 1 N ∑ j ∈ I | a j | p ) 1 / p . {\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}.}
Now, we notice that for d ∈ N {\displaystyle d\in \mathbb {N} }
| a i | ≤ | a d N | , for i = d N + 1 , … , ( d + 1 ) N ; {\displaystyle |a_{i}|\leq |a_{dN}|,\quad {\text{for}}\quad i=dN+1,\dots ,(d+1)N;}
| a d N | ≤ | a j | , for j = ( d − 1 ) N + 1 , … , d N ; {\displaystyle |a_{dN}|\leq |a_{j}|,\quad {\text{for}}\quad j=(d-1)N+1,\dots ,dN;}
Using this, we can estimate
( 1 N ∑ i ∈ I ∖ I N | a i | q ) 1 / q ≤ ( 1 N ∑ d ∈ N N | a d N | q ) 1 / q = ( ∑ d ∈ N | a d N | q ) 1 / q {\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}}
as well as
( ∑ d ∈ N | a d N | p ) 1 / p = ( 1 N ∑ d ∈ N N | a d N | p ) 1 / p ≤ ( 1 N ∑ i ∈ I | a i | p ) 1 / p . {\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}|a_{i}|^{p}\right)^{1/p}.}
Also, we get by ℓp norm equivalence:
( ∑ d ∈ N | a d N | q ) 1 / q ≤ ( ∑ d ∈ N | a d N | p ) 1 / p . {\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}.}
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.