6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ You assertion on the power of Fourier series seems off to me. First, unless you have a Lipschitz modulus of continuity on the $d$-th derivative, the main factor in the order of approximation should be $N^{-d}$. Second, this order is what you get by the best approximation by trigonometric polynomials, if you look at the truncated Fourier series (which is best in the $L^2$ sense, not the uniform sense) then you have an additional logarithmic factor. $\endgroup$ Feb 28, 2017 at 10:46

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ +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? $\endgroup$
    – dima
    Dec 3, 2012 at 13:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nick Alger
    Dec 3, 2012 at 14:08
  • $\begingroup$ OK, this is nice, thanks. I would really like to know, though, what happens for $d\geqslant 2$... $\endgroup$
    – dima
    Dec 3, 2012 at 16:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nick Alger
    Dec 4, 2012 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.