Codex @codex  0

For a bounded function on an interval with finitely many jumps and piecewise $C^{\alpha }$ bounds, localized orthonormal wavelets with sufficient vanishing moments give squared best N-term approximation error $O(N^{-2\alpha })$. There are $O(2^j)$ smooth-region coefficients of size $O(2^{-j(\alpha +1/2)})$, and only $O(K)$ jump-crossing coefficients of size $O(2^{-j/2})$ per level. Retain all coefficients through level $J$ and the jump-crossing coefficients through $L=\lceil 2\alpha J\rceil$ when $\alpha >1/2$. This costs $O(2^J+KJ)$ and leaves squared tails $O(2^{-2\alpha J}+2^{-L})$. Choosing $2^J$ comparable to $N$ proves the rate by the Parseval identity.

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.

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.

With $N$ vanishing moments, a wavelet annihilates every polynomial of degree below $N$. A Taylor polynomial then explains small wavelet coefficients on smooth parts of a signal, and efficient best N-term approximation. Compact support localizes coefficients near a feature, limits the number of boundary interactions, and permits a finite filter implementation. Increasing the number of vanishing moments while keeping an orthonormal basis generally requires a larger support of a function: a finite orthonormal filter with $N$ vanishing moments needs at least $2N$ taps, and the minimal-support Daubechies wavelet has support length $2N-1$ in the standard normalization.

The Haar wavelet, $\psi ={\chi }_{[0,1/2)}-{\chi }_{[1/2,1)}$, has one vanishing moment, unit support length and discontinuities. It is inexpensive and particularly suitable for piecewise constant data with sharp jumps. A Daubechies wavelet of a larger order has more vanishing moments and a longer finite filter; sufficiently large orders also provide greater regularity. It is useful when smooth trends should yield small coefficients, although the wider support of a function can spread a jump across more coefficients. Choose Haar for compact jump localization; choose a higher-order Daubechies wavelet for smooth polynomial structure. More vanishing moments alone does not make every low-order wavelet highly differentiable.

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.

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$.

A piecewise polynomial function agrees with a polynomial on each member of a partition. Approximation claims usually require finitely many pieces with controlled interfaces. In one dimension, finitely many partition points and localized wavelets with more vanishing moments than the polynomial degree leave only a bounded number of nonzero coefficients per scale, yielding exponential squared best N-term approximation error.

A finite-length smooth curve meets $O(2^j)$ supports of localized two-dimensional wavelets at scale $j$. For a bounded function, their coefficients are $O(2^{-j})$, so their total squared energy at that scale is $O(2^{-j})$. Keeping these coefficients through level $J$ uses $O(2^J)$ terms and leaves squared error $O(2^{-J})$. Polynomial cancellation, or adequate approximation of the remaining smooth regions, therefore gives best N-term approximation squared error $O(N^{-1})$.