Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 340 / 3

Write $c_m=⟨f,g_m⟩$. A linear N-term approximation fixes the indices independently of $f$, normally the first $N$ in a prescribed ordering:A best N-term approximation chooses the indices using $f$: retain $N$ coefficients of largest absolute value, resolving ties arbitrarily, and set $f_N^n={\sum }_{m\in {\Lambda }_N(f)}{c}_m{g}_m$. The Parseval identity shows why this choice is optimal:For any fixed index set, the orthogonal projection coefficients minimize the error; optimizing the set then means discarding the smallest squared coefficients. Thus “linear” requires a specified ordering, while “nonlinear” refers to the data-dependent selection.

Use the usual localized, compact support construction of an interval-adapted wavelet basis, including boundary wavelets with the stated vanishing moments, and order the linear N-term approximation by increasing resolution. Also interpret a piecewise polynomial function as having finitely many pieces. These conventions matter: regularity and vanishing moments alone, or an arbitrary enumeration, do not establish the asserted rates.

At scale $j$, a wavelet whose support lies in one polynomial piece has zero coefficient because $p<q$. Only a bounded number $B$ of wavelets per scale can meet a partition point. Their $L^1$ norms are bounded by $C{2}^{-j/2}$, and $f$ is bounded. Thus $|c_{j,k}|\le C_f{2}^{-j/2}$ andRetain the fixed number of coarse scaling function coefficients and every nonzero coefficient through level $J$. This uses at most $B(J+1)+B_0$ terms, leaving squared error at most $C{2}^{-J}$. The optimal best N-term approximation is no worse; choose $J$ proportional to $N$ to obtain $O({\omega }^N)$ for some $\omega \in (0,1)$. In contrast, retaining all wavelets through level $J$ costs $\asymp 2^J$ terms. Choosing the last complete level before $N$ givesThese are squared errors; the corresponding $L^2$ errors are $O({\omega }^{N/2})$ and $O(N^{-1/2})$.

For a function smooth on finitely many closed pieces with finite one-sided derivatives, integration by parts gives its Fourier series coefficients, for $n\ne 0$,where $J_r=f(x_r+)-f(x_r-)$ includes the jump of the periodic extension at the endpoint when necessary. In particular $|c_n|\le C/|n|$. Keeping frequencies $|n|\le K$, with $N\asymp K$, gives squared error $O({\sum }_{n>K}{n}^{-2})=O(N^{-1})$.

A best N-term approximation cannot improve this worst-case rate. For example, $f={\chi }_{[0,1/2)}$ has $|c_n|=1/(\pi |n|)$ on odd nonzero $n$ and zero on even nonzero $n$. Even the optimal selection therefore leaves a squared tail comparable to $N^{-1}$. Thus for the class with jumps,or $N^{-1/2}$ in the $L^2$ norm. Individual functions with no jumps, or additional cancellation, can converge faster. “Smooth except at finitely many points” must include controlled one-sided smoothness; smoothness merely on open pieces permits pathological behavior near their endpoints.

For the multiresolution analysis $V_j$ and its detail spaces $W_j$, take the completed tensor product ${\mathcal{V}}_j=V_j\otimes V_j$. Since $V_{j+1}=V_j\oplus W_j$,The three tensor-product wavelets areTaking products of members of the two one-dimensional families gives an orthonormal basis of each respective completed tensor product. Density and the coarse-scale trivial intersection yieldas an orthonormal basis of $L^2({\mathbb{R}}^2)$. The normalization is $2^j$ in two dimensions. On the square, tensorize the interval-adapted wavelet basis and include the finite coarse scaling function part.

Use localized tensor-product wavelets and finitely many bounded polynomial pieces, with the boundary wavelets adapted as in part (b). A rectifiable smooth curve of length $\ell$ meets $O(1+\ell 2^j)$ dyadic squares of side $2^{-j}$: subdividing an arclength parametrization into pieces of length at most $2^{-j}$ covers it by that many balls, each meeting only a bounded number of squares. Enlarging squares by the fixed support diameter preserves the count.

Each normalized two-dimensional wavelet has $L^1$ norm $O(2^{-j})$. A coefficient meeting the curve is therefore $O(2^{-j})$, and the total squared energy of these coefficients at level $j$ is $O(2^{-j})$. If $p<q$, all other coefficients vanish by the vanishing moments. Keeping the curve coefficients through level $J$ costs $O(2^J)$ and leaves squared error $O(2^{-J})$.

The printed part (e) does not repeat $p<q$. The bound still holds for any fixed polynomial degree when $q\ge 1$: on a smooth piece, a Taylor polynomial in the variable carrying a wavelet gives coefficient size $O(2^{-(q+1)j})$. There are $O(4^j)$ such coefficients, so their squared energy is $O(2^{-2qj})$. Retain all coefficients through $K=\lfloor J/2\rfloor$, and curve coefficients through $J$. The cost is $O(4^K+2^J)=O(2^J)$ and the omitted squared energy isThe best N-term approximation is at least as good as this selection, provingThis argument covers the unqualified finite-degree clause without adding an unnecessary restriction $p<q$.