Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 340 / 2

Fix the ordering of the orthonormal basis and write $c_m=⟨f,g_m⟩$, taking indices from $1$. The linear N-term approximation retains the first $N$ coefficients:Its index set is independent of $f$, so the map is an orthogonal projection and is linear.

For the nonlinear N-term approximation, let ${\Lambda }_N(f)$ be any set of $N$ indices with greatest $|c_m|$, resolving ties arbitrarily and padding with zero coefficients if necessary. Since $(c_m)\in {\ell }^2$, such a selection exists. ThenThe Parseval identity shows that for any fixed index set the displayed coefficients minimize the Hilbert space error. Choosing the largest squared magnitudes minimizes the omitted sum over every set of at most $N$ indices. This is the best N-term approximation; dependence of the selected indices on $f$ makes the operation nonlinear.

For $0<\alpha \le 1$, uniform Lipschitz-$\alpha$ means that one constant $M$ satisfies $|f(x)-f(y)|\le M|x-y{|}^{\alpha }$ for every $x,y\in [0,1]$. The resulting Hölder space has normFor the subsequent estimates at general $\alpha >0$, use the higher-order Hölder class convention: write $\alpha =r+\beta$ with $r\ge 0$ an integer and $0<\beta \le 1$, and require $f\in C^r([0,1])$ with $f^{(r)}$ uniformly Lipschitz-$\beta$. ThusAt integer $\alpha =k$, this uses $C^{k-1,1}$; the alternative classical $C^k$ convention is stronger on this compact closed interval and also suffices for the estimates.

For exponents above one, a first-difference inequality alone forces the function to be constant. Partition $[x,y]$ into $n$ equal pieces and use the triangle inequality: $|f(y)-f(x)|\le M|y-x{|}^{\alpha }{n}^{1-\alpha }\to 0$. Consequently a nontrivial higher-order definition is needed for the full range of exponents in the later wavelet estimates. Equivalently, higher-order Hölder class gives a local Taylor polynomial with remainder bounded by $C\Vert f{\Vert }_{C^{\alpha }}|x-x_0{|}^{\alpha }$.

Use localization and cancellation of the assumed interval-adapted wavelet basis: at scale $j$, every detail wavelet has support diameter at most $B{2}^{-j}$, L1 norm at most $B^{\prime }{2}^{-j/2}$, and annihilates polynomials of degree less than $q$. These bounds also apply to the modified boundary wavelets; a restriction of an arbitrary whole-line wavelet without the cancellation-preserving boundary construction would not suffice. The finitely many coarse scaling functions can be treated separately.

Write $\alpha =r+\beta$ with $0<\beta \le 1$ as above. Because $\alpha <q$, we have $r<q$. Choose $x_0$ in the support of a function of ${\psi }_{j,n}$, and let $T_{x_0}$ be the degree-$r$ Taylor polynomial of $f$. The Hölder-Taylor remainder bound givesFor $r=0$ this is the Hölder seminorm bound. For $r\ge 1$, the integral Taylor remainder is bounded using $f^{(r)}(t)-f^{(r)}(x_0)$, whose magnitude is at most $[f^{(r)}{]}_{C^{0,\beta }}|t-x_0{|}^{\beta }$.

The vanishing moments remove $T_{x_0}$ from the inner product. Applying the remainder estimate and the L1 norm bound on the localized support yields the wavelet coefficient decay for Hölder functionsThusHere $C$ depends on the fixed wavelet family, the exponent and boundary construction, but not on $f,j,n$. The proof uses the assumed regularity and moments; it does not identify the minimal Daubechies wavelet order with its differentiability order, which need not coincide.

Let $M$ bound the piecewise Hölder norms, and let $B=\Vert f{\Vert }_{\infty }$. At scale $j$, classify a wavelet as bad when its localized support of a function meets a discontinuity, and as good otherwise. Compact support and bounded overlap imply at most $C_{0}K$ bad wavelets per scale and at most $C_1{2}^j$ total wavelets. A good support lies in a single smooth piece, so the preceding wavelet coefficient decay for Hölder functions gives $|c_{j,n}|\le CM{2}^{-j(\alpha +1/2)}$. The permitted bounded-function estimate gives $|c_{j,n}|\le CB{2}^{-j/2}$ for bad coefficients.

Consider a specific N-term approximation: retain all coarse scaling functions and all wavelets through scale $J$, and also retain the bad coefficients at scales $J<j\le L$, where $L=\lceil 2\alpha J\rceil$. Since $\alpha >1/2$, $L\ge J$ for large $J$. Its term count is bounded byBy the Parseval identity, its squared L2 norm error is the sum of omitted squared coefficients. The good tail satisfiesand the remaining bad tail satisfiesChoose $J=\lfloor {\log }_2(N/(2C_2^{\prime }))\rfloor$ with a fixed sufficiently large $C_2^{\prime }$; then the $O(KJ)$ extra terms fit the remaining budget for all sufficiently large $N$, while $2^J$ is comparable to $N$. Padding to $N$ terms does not increase the error. The best N-term approximation is at least as accurate as this constructed selection, soThe constant may depend on the finite number of jumps, the piecewise Hölder norms, $B$ and the fixed wavelet family. Values exactly at the jumps are immaterial in $L^2$. The improvement comes from retaining only a bounded number of jump-crossing coefficients at each finer scale, as in best N-term wavelet approximation of piecewise Hölder functions.