MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Approximation power of wavelets

The Wikipedia article on Wavelet Transform states that:

Wavelet compression is not good for all kinds of data: transient signal characteristics mean good wavelet compression, while smooth, periodic signals are better compressed by other methods, particularly traditional harmonic compression (frequency domain, as by Fourier transforms and related).

What is the precise quantification of this statement? For the smooth periodic signals we have for example: if the signal is of class $C^d$ of $d$-times continuously differentiable periodic functions, then the partial Fourier sum of order $N$ gives uniform approximation error at most $N^{-d-1}$. What would be the corresponding characterization for wavelet series?

To make the question more concrete: if the signal is piecewise $C^d$-periodic, with, say, one discontinuity, what approximation error do I get with $N$ wavelet coefficients (the Fourier approximation gives only $N^{-1}$ away from the discontinuity)? Conversely, how many coefficients do I need to get an accuracy $\epsilon$?

-

The relationship between wavelets and smoothness spaces is characterized by "Jackson" and "Bernstein" inequalities. Jackson inequalities look something like $$||f-\pi_k f||_{L_p} \le C_1(k,p) |f|_{\text{smoothness seminorm}},$$ where $\pi_k$ is a projector onto the $k$'th level approximation space (space spanned by all wavelets up to resolution level $k$) and $1 \le p \le \infty$.

Bernstein inequalities look something like $$|u|_{\text{smoothness seminorm}} \le C_2(k,p)||u|| _{L_p},$$ where $u$ is any function in the $k$'th level approximation space.

The exact results vary based on the domain, choice of wavelets, and smoothness space of interest. Usually $C_1 \approx 2^{-k d}$, where $d$ is the level of smoothness in the seminorm, and $C_2 \approx 2^{k/p}$, but you'll have to look to the literature for your situation. These sort of results are often proved by breaking space up into a bunch of dyadic cubes and then applying polynomial approximation theory on them.

For a well written introduction, see DeVore's explanatory paper.

-
+1 for the link. Still, this is for me very confusing. What if I want to approximate the function with accuracy $\epsilon$, how large should I take $k$ to be? Consequently, how many wavelet coefficients are needed? – dima Dec 3 at 13:32
One would solve $C \cdot 2^{-kd}|f|_{Lip(d)}=\epsilon$ for $k$. That gives the the resolution level $k$, from which the number of terms $N$ can be determined. In 1D on a periodic domain with Haar wavelets and $p=\infty$ Lipschitz smoothness with $d=1$, it simplifies. You get twice as many wavelets each time you increase the resolution, so $N \approx 2^k$. Altogether this yields $C/N = epsilon$ I believe. My personal knowledge is with Besov smoothness spaces and $p \neq \infty$ though, so you should probably double check it before using this result. – Nick Alger Dec 3 at 14:08
OK, this is nice, thanks. I would really like to know, though, what happens for $d\geqslant 2$... – dima Dec 3 at 16:02
Same formula should hold for $d>1, p=\infty$ if I recall correctly. I think this is proved in the last chapter of Wojtaszczyk's book, [A Mathematical Introduction to Wavelets](books.google.com/books/about/…). – Nick Alger Dec 4 at 13:57