# DFT and DWT difference?

what is the basic difference between the Discrete Fourier Transform and the Wavelet Transform ? and why does JPEG2000 preferred DWT over DCT or DFT ?

-
"what is the basic difference" - they use different... wait for it... basis functions. DFT uses complex exponentials, while DWT uses wavelet functions. – J. M. Apr 19 '12 at 17:12
Re: second question, see this. – J. M. Apr 19 '12 at 17:14
Do you know of dsp.stackexchange.com ? – Mariano Suárez-Alvarez Apr 19 '12 at 17:20

Sinusoids and wavelets are the bases used in DCT (JPEG) and DWT (JPEG2000), respectively. Lossy compression works by finding a basis (think: alphabet) that represents the signal using as few elements (think: words or letters) as possible. The loss is a result of discarding elements that do not make a significant contribution. To continue the analogy, if you take a sentence in English and discard the vowels you can roughly guess what was meant, while using fewer letters. Lossy compression works in the same way.

-

The basic difference is the following: Assume you have a data vector ${\bf x}=(x_1,\ldots, x_N)$ of length $N:=2^n$ that models a function of a real variable $t$ on some finite interval.

In DFT you compute $N$ complex Fourier coefficients of this data vector according to the formula $$\hat x_j:={1\over N}\sum_{k=0}^{N-1} x_k\ \omega^{-jk}\ , \qquad\omega:=e^{2\pi i/N}\ ,$$ where FFT (fast Fourier transform) allows you to obtain the $\hat x_j$ in $O(N\log N)$ operations, and the same number of operations will lead you back to the original ${\bf x}$. The $\hat x_j$ encode all sorts of "distributed" information about ${\bf x}$, but basically you need all of them to recover ${\bf x}$ with sufficient accuracy.

The basic ingredient in DWT is multiresolution analysis. Here the $N$ wavelet coefficients, say $w_j$, of the given ${\bf x}$ can be computed in only $O(N)$ operations. The main point, however, is that the $w_j$ encode local information about ${\bf x}$ in a way that makes it possible to discard all $w_j$ with absolute value below a given treshold and still being able to reconstruct ${\bf x}$ with acceptable accuracy. That's what makes DWT so useful in MP3 or in image compressing.

This is accomplished in the following way (I'm describing a toy model of the setup): $w_0$ is just the average of the $x_k$; $w_1$ is the difference between the averages of the $x_k$ in the first half and the second half of the data vector, $w_2$ is the difference between the averages of the $x_k$ in the first quarter and the second quarter of the data vector, and $w_3$ is the difference between the averages of the $x_k$ in the third quarter and the fourth quarter of the data vector, and so on. Finally $w_{N-1}$ is the difference between $x_{N-1}$ and $x_N$. (I have omitted certain weight factors.)

The basis functions of DFT are "discretized sine waves" whereas the basis functions of DWT, the socalled wavelets, have very peculiar graphs. But the exact shape of these wavelets plays no rôle in the applications: It is the algebraic structure of the whole setup that is essential.

-