Why are wavelet transforms (Multi Resolution Analysis) used more in practice for compression rather than Fourier series?

Question

I know that both Fourier and wavelet can be used for compression of signals.

The Fourier series guarantees that it gets the closest approximation of the original signal in the least squared sense. It also decomposes the signal into orthogonal components. So, I wonder why it isn't obvious to always use the Fourier series as a compression algorithm?

The Wavelet transform allows us to observe frequencies at different times, because it is localized in time (at least relative to the fourier transform). So it is only useful when we care about the interpretability of the components, it seems to me.

Why is the wavelet compression used in practice much more than compression using a fourier series?

Answer 1

In short: wavelets and relatives are pretty good at compacting a sufficiently large class of regular-enough and useful signals and images. What follows are signal properties (and corresponding wavelet features) that make wavelets good (not best) candidates for lossy compression:

• piecewise-smooth (vanishing moments, or cancellation of low-order polynomials)
• edges or jumps (gradient-like or Laplacian behavior of wavelets)
• localized oscillations (zero-average and wiggling wavelet shape)
• noise or spurious events (orthogonality and sparsity enhancement)

As said by @hops, the efficiency of wavelets for compression depends of the good matching of a signal class and the chosen wavelets.

Let us restrict here to non-redundant discrete transformations: discrete Fourier and discrete wavelets. Both are orthogonal, or close enough (bio-orthogonal wavelets) to skip the distinction.

So both, when transform coefficients are discarded, are least-squares approximations. But least-squares are not the best metric for compression: if you double the amplitude of a sample, the energy is multiplied by $4$, but it only adds one bit to the stored data, in a $\log_2$ reasoning.

In a way, a transform will help compression if it reduces the logarithmic cost or bit-budget of a discrete signal; hence, if the coefficients have a power law $1/c^{\beta}$ that decreases fast enough (the highest the $\beta$, the better).

This feature is often called the compressibility of signals. It can be assessed empirically, but also theoretically based on complicated functional analysis (Besov, Sobolev spaces).

However, consider the useful class of $C^\alpha$ piecewise regular signals, $\alpha \ge 1$. They are locally smooth, with jumps (edges). Taking the largest $M$ coefficients for compression (or nonlinear approximation), the mean squared error for the Fourier basis will asymptotically decrease in $1/M$ for Fourier (because of Gibbs ringing). While wavelet approximations can decrease as $1/M^{-2\alpha}$. The smoother the signal, the better the wavelet compressibility. In other words, Fourier cannot use the regularity of the signal.

In practice, this is not so simple. The complex aspect of Fourier is somewhat difficult to handle. Quantization should be taken into account. The storage of the highest coefficients location costs too. Perceptual distortion should play a role, at least for lossy compression.

So at low compression rates, local Fourier decompositions like the JPEG DCT can perform as well as wavelets, since asymptotic proofs do not apply. Indeed, local cosine bases, lapped orthogonal transforms that bridge the gap between Fourier and standard wavelets perform well too, and they are used in the MP3 standard (MDCT). For images, the 2D aspect renders separable wavelets less efficient than in 1D.

For strict lossless compression through, (wavelet) transforms are not the state-of-the-art yet.

Answer 2

Fourier analysis is great for signals with unchanging characteristics. So it is usually a good fit for modeling noise. Unfortunately, most of the time we are not interested in noise but in signals. You can try regaining a signal by subtracting noise, but straightforward subtraction requires the phase of the noise (which does not lead itself well to modeling for stochastic signals), and spectral subtraction is basically selective attenuation that kills weak parts of the signal along with the noise.

So one usually wants to model the signal more than the noise, and the whole point of a "signal" is its information content, namely intentionally changing signal characteristics. For that, local support of your basis functions is a reasonable approach since it helps keeping the nonzero coefficients for representing the changing signal better localized in space-time.

Answer 3

Compression is often used to reduce the number and amount of (near) inaudible sub-components in a sound file.

But inaudibility is a human psycho-acoustic phenomena, and experimentally determined to be non-linear. How well a human can localize a sonic event in time depends on the frequency content, and how well a human can discriminate absolute frequency differences depends on the frequency (octave). Thus a non-linear transform (even though "less exact" than a complete Fourier transform) might correspond more closely to ranges of audio sub-components that are perceivable or not perceivable in both time and frequency. This allows a compression algorithm to use less computed components (wavelets vs. DFT bins) to find the ones than can be thrown out or compressed into less bits. Whereas an FFT computes the same length of time window and number of frequency result bins whether or not there is any perceptual difference across the FFT aperture.

Answer 4

It would be best if you quantified what you mean by wavelet compression being used "much more in practice" (by citing examples, etc). This would allow more specificity to the domain of interest, but I will try to give a reasonable (albeit general and not too technical) explanation.

A wavelet transform and the Fourier Transform correspond to different choices of basis functions. Any basis can be used to get a perfect description of the function. If we decide to limit ourselves to $N$ coefficients where $N$ is less than the total number of basis vectors, we may do so using the least squares criterion as you suggested (or others). Note that for a good compression algorithm, the signal must be well approximated by only these $N$ coefficients where $N$ should be made small.

The basis functions of the Fourier Transform are complex exponentials with infinite support (from $-\infty$ to $+\infty$). If the signal being compressed is easily expressed as a summation of such sinusoids (as is the case for periodic signals), the Fourier transform coefficients will have a small number of components with a large magnitude. If we store only these high magnitude components, we will be able to reproduce the signal very accurately. If not, then we won't. Now, consider a piece of music. Does it contain one note that simply plays (and doesn't fluctuate in amplitude) for the entire song? Obviously not. When a new note is hit, we have to sum many sinusoids to express the idea of the note "starting" to play.

The basis functions of a wavelet transform are dilated (and scaled) versions of the mother wavelet. The wavelet is usually chosen to have some compromise between its frequency resolution (or scaling resolution) and its time localization as you noted in your question. Now, a piece of music that is decomposed into (projected onto) these basis functions will only have components with a large magnitude at a small number of times and frequencies (dilations). This means that when a note starts to play, the wavelets corresponding to those frequencies will be activated (resulting in a large magnitude for those components). When the note stops, those coefficients will be lower (or zero). This means that the large magnitude coefficients that we retain in the compressed version are only at specific times and frequencies.

Thus, a wavelet transform will be optimal for these situations. Then, one must choose a mother wavelet. This choice can also affect the compression ratio. If the wavelet approximates the signal well in both time and frequency resolution, then one would expect to have fewer large magnitude coefficients, resulting in better compression.

A very useful way of looking at both transforms is how they divide up the time-frequency plane into "tiles." If these tiles correspond to the natural energy distribution of the signal in time and frequency, then one can expect a good compression ratio. If not, then not. Wavelets offer one more flexibility in tuning this tiling to a particular signal.

I hope that helps.

Note: I've avoided using the article "the" for the Wavelet Transform simply because one must always choose a mother wavelet to define the Wavelet Transform fully, and this choice impacts the effectiveness of the transform. This is one reason it is so useful though. Through the choice of this mother wavelet, we can find a good match for most signals occurring in practice.