3
$\begingroup$

I am currently working with wavelets and computer vision, but I want to understand them in a more mathematical way. I know that the object in my study is defined by

$$\Phi_{(s, l)}(x) = \frac{1}{\sqrt[]{s}} \Phi\left( \frac{x-l}{s}\right)$$

where $\Phi$ is a mother wavelet. And I know that mother wavelets should satisfy that they have finite energy and the admissibility condition. I also know that we can compute, for a function $f$, its Continuous Wavelet Transform which goes by the formula

$$ W(s, l) = \int_{-\infty}^\infty f(t) \Phi_{(s, l)}(t) dt $$

Now, I'm having trouble with:

  • Finding the exact Discrete Wavelet Transform. I have read lots of papers and every single one of them have different approaches to this, I can't come up with the right formula
  • The mathematical relationship between the Discrete Wavelet Transform and the Wavelet Matrix. I know that you can find lots of articles (example: http://www.whydomath.org/node/wavlets/generalwt.html, http://www.whydomath.org/node/wavlets/hwt.html) talking about how to generate specific Wavelet Matrix. But they don't explain what has everything to do with the Wavelet formula, and that is not the mathematical explanation that I want. To be precise, I don't want to learn that, if I average data and build that matrix I get a Haar wavelet matrix; I want to be able to build the Haar matrix because I understant the Wavelet theory.
$\endgroup$
  • 1
    $\begingroup$ This should be defined as $W(s,l)=\int\cdots$, rather than $W(s,t)$. $\endgroup$ – RideTheWavelet May 21 '18 at 15:43
2
$\begingroup$

The key idea in the Discrete Wavelet Transform is that of a Multiresolution Analysis, or an MRA. This is a collection of subspaces $V_{j}$ of $L^{2}(\mathbb{R})$ with the following properties (from Ten Lectures on Wavelets$^1$):

  1. $\cdots V_{2}\subset V_{1}\subset V_{0}\subset V_{-1} \subset V_{-2}\cdots$,
  2. $\overline{\bigcup_{j\in\mathbb{Z}}V_{j}}=L^{2}(\mathbb{R})$,
  3. $\bigcap_{j\in\mathbb{Z}}V_{j}=\{0\}$,
  4. $f\in V_{j}\Leftrightarrow f(2^{j}\cdot)\in V_{0}$,
  5. $f\in V_{0}\Rightarrow f(\cdot-n)\in V_{0}\text{ for all }n\in\mathbb{Z}$,
  6. $\{\phi_{0,n}: n\in\mathbb{Z}\}$ is an orthonormal basis in $V_{0}$.

Here $\phi$ is a scaling function, and $\phi_{j,n}(x)=2^{-j/2}\phi(2^{-j}x-n)$ for all $j,n\in\mathbb{Z}$. Whenever we have a multiresolution analysis $\{V_{j}\}_{j\in\mathbb{Z}},$ then there exists an orthonormal wavelet basis $\{\psi_{j,k}:j,k\in\mathbb{Z}\}$ of $L^{2}(\mathbb{R})$ (same meaning for $\psi_{j,k}$ as for $\phi_{j,n}$), where we may find $\psi$ because $\{\psi_{0,k}:k\in\mathbb{Z}\}$ is an orthonormal basis for $W_{0},$ the orthogonal complement of $V_{0}$ in $V_{-1}$.

Since $\phi(x)=\phi_{0,0}(x)$ is in $V_{-1},$ it has a representation as $\phi(x)=\sum_{n\in\mathbb{Z}}h_{n}\phi_{-1,n}(x)$ (with only finitely many $h_{n}\neq0$). Integrating the left and right hand sides gives $1=\sum_{n\in\mathbb{Z}}h_{n}/\sqrt{2},$ which gives the equation $\sum_{n\in\mathbb{Z}}h_{n}=\sqrt{2}$, and the other equations found on the links you posted may be derived from properties of the MRA. In particular, $\psi(x)=\sum_{n\in\mathbb{Z}}g_{n}\phi_{-1,n}(x),$ where one choice of the $g_{n}$ is given by $g_{n}=(-1)^{n}h_{1-n}$ for all $n\in\mathbb{Z}$ (note that we have nonuniqueness because I may translate $\psi$ by an integer or multiply it by $-1$ with no change in the properties I'm imposing on it).

For Haar, we have $h_{0}=h_{1}=1/\sqrt{2},$ and $g_{0}=-g_{1}=1/\sqrt{2}$.

There is far more to be said, and it would not be appropriate to go into further detail here. However, this gives a taste of the theory, and you can learn more by reading either Ten Lectures$^1$, which is more advanced; or A First Course in Wavelets$^2$, which assumes less, and has a very nice, in-depth study of the Haar wavelet basis to demonstrate the general theory in a simple, concrete case. Of course, there are also many, many other books on the subject (Strang and Nguyen's Wavelets and Filter Banks, P.P. Vaidyanathan's Multirate Systems and Filter Banks, Kovacevic and Vetterli's Wavelets and Subband Coding, Stephane Mallat's A Wavelet Tour of Signal Processing, Hernandez and Weiss's A First Course on Wavelets, Yves Meyer's Wavelets and Operators), some of which are more focused than others on wavelets specifically, and which represent a broad spectrum of difficulties/ assumed background. This last group of references is probably better once you've figured out what you'd like to know more about, whereas the first two will be very good for getting the main idea of wavelets.

[1]: Ingrid Daubechies. Ten Lectures on Wavelets. SIAM, 1992, Philadelphia, PA.

[2]: Albert Boggess and Francis J. Narcowich. A First Course in Wavelets with Fourier Analysis, 2nd ed. Wiley, 2009, Hoboken, NJ.

EDIT: When processing a discrete signal, we imagine that the samples we observe are the coefficients of some function $f$ at a given scale, say, $-J$, where $J>0$ is an integer. That is, if $f(x)=\sum_{n\in\mathbb{Z}}c_{n}\phi_{-J,n}(x),$ we observe $\{c_{n}\}_{n\in\mathbb{Z}}$. This might seem like a strange assumption, but I would argue that supposing that we observe $\{f(x_{k})\}$ where $x_{k}$ are on some grid is also an odd assumption, since we are considering $L^{2}(\mathbb{R})$ functions, where pointwise evaluation doesn't make sense; on the other hand, $c_{n}=\langle f,\phi_{-J,n}\rangle$ is well-defined (and equals a weighted average of the values of $f$ in a small interval, which fits better with what sensors/ cameras do in applications). At any rate, supposing that we have observed these coefficients, we are now able to compute the scaling and wavelet coefficients at the next coarser scale, $1-J$, in the following way: \begin{align*}\langle f,\phi_{1-J,n}(x)\rangle&=\langle f,\sum_{k\in\mathbb{Z}}h_{k}\phi_{-J,k}(x-2^{1-J}n)\rangle\\&=\langle f,\sum_{k\in\mathbb{Z}}h_{k}\phi_{-J,2n+k}\rangle\\&=\sum_{k\in\mathbb{Z}}\overline{h_{k}}\langle f,\phi_{-J,2n+k}\rangle\\&=\sum_{k\in\mathbb{Z}}c_{2n+k}\overline{h_{k}}.\end{align*} That is, we compute an inner product between the $h_{k}$ and the $c_{k}$ starting at a certain point, and then move over by $2$ to get $\langle f,\phi_{1-J,n+1}\rangle$, which you can see in the matrices in the links from your question. Similarly, we can do this for the wavelet coefficients. This can also be thought of as a convolution with a time-reversed $h$ ($(h(-\cdot)\ast c)(n)=\sum_{k\in\mathbb{Z}}h(-\cdot)_{-k}c_{n+k}=\sum_{k\in\mathbb{Z}}h_{k}c_{n+k}$) followed by downsampling ($(\downarrow y)(n)=y(2n)$).

So the matrix arises because we want to compute all of the following:

  1. Start with $c_{n}^{(-J)}=\langle f,\phi_{-J,n}\rangle$.
  2. Use the above equation and its like to obtain $c^{(1-J)}_{n}=\langle f,\phi_{1-J,n}\rangle$ and $d^{(1-J)}_{n}=\langle f,\psi_{1-J,n}\rangle$.
  3. Repeat 1 and 2 using the $c^{(1-J)}_{n}$ for as many scales as desired/ possible given the length of the data to end up with (if you compute $J$ scales) $\{c^{(0)}_{n}\},\{d_{n}^{(0)}\},\{d_{n}^{(-1)}\},\ldots,\{d^{(1-J)}_{n}\}$, which are listed in order of coarsest to finest scale.

I've labeled the $c_{n}^{(j)}/d_{n}^{(j)}$ as such because these are often called the coarse coefficients at scale $j$ and the detail coefficients at scale $j$, respectively.

$\endgroup$
  • $\begingroup$ Your answer has been very revealing and I feel that I get the idea better. However, there is a concept that I can't make the connection by myself. What is the relation between the discrete wavelet transform and the matrix? I mean, now I know how to compute $h_n$ and $g_n$, but I'm missing why you can use this as a matrix and apply that matrix to the signal. Again, thank you very much. A First Course in Wavelets has been very helpful too. $\endgroup$ – Aliara Jun 3 '18 at 16:44
  • 1
    $\begingroup$ I've edited my answer to better explain this point. $\endgroup$ – RideTheWavelet Jun 4 '18 at 5:16
  • $\begingroup$ Please, you will have to forgive me. I come from abstract mathematics and applied solutions are really hard for me, I can't make the connection. It bothers me because I'm using this in CV, I have an image, multiply it by a matrix wavelet and I obtain... the image transformed, I guessed. For example, as said here: mathworld.wolfram.com/HaarFunction.html. But I don't see why I am building the matrix, what's the result of it and why my data is compressed (I use them as a compression tool). I'm really sorry and really thankful for your time, again =( $\endgroup$ – Aliara Jun 4 '18 at 17:01
  • 1
    $\begingroup$ Try these and let me know how they help: First link, Second link, Third link. Fourthly, don't despair if you're having some trouble. It took me a long time to feel like I really had the "hang" of wavelets, too. $\endgroup$ – RideTheWavelet Jun 5 '18 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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