Data Science Part 21: Multiresolution Approximation

In multiresolution approximation spaces, the sequence {Vj}j∈ℤ of subspaces L2(ℝ) are called multiresolution approximation (MRA) if:

1. Vj+1 is a subset of Vj

2. lim (j -> ∝) Vj = {0} (the zero function)

3. lim (j -> -∝) Vj = L2(ℝ) (the entire subspace)

4. For all j, k, f(t) ∈ Vj if f(t/2) ∈ Vj+1. This means that Vj+1 has a smaller Subspace than Vj. Here is the visualization: 

Under some conditions, the wavelet {Ψj,n(t)} forms an orthonormal basis for L2(ℝ). We can derive the following: 

The Haar multiresolution space is defined as Φ(t) is 1 when t is between 0 and 1 and 0 elsewise. In V0, we have all piecewise constant functions L2(ℝ) with discontinuities at t = ..., -1, 0, +1,... etc. We can express superposition of  Φ(t) as translated by integers. Here is a list of Haar wavelets: 

 

V-1 has discontinuities at  t = ..., -1/2, 0, +1/2,... etc. Vj are piecewise constant functions, and discontinuities at integer multiples of 2^j. The biggest wavelets pull out the biggest structure, and the subsequent wavelets will pull out smaller and smaller structures. We want more temporal resolution at high resolutions and frequency resolution at lower frequencies since things change more in higher frequencies. We can use this to represent images very, very efficiently. 

Here is a drawing with some of the frequency domains:

The shannon multiresolution space is also another wavelet but with a different function of Φ(t) = sin(𝜋t)/(𝜋t) which basically is bigger when you go nearer to the 0 point and smaller otherwise. 

Vj is very bandlimited functions in the L2(ℝ) space, where 𝜔 ∈ [(−2^−𝑗) * 𝜋,(2^−𝑗) * 𝜋]. 

The differences between multiresolution spaces is that the approximation of f in Vj-1 contains details that are not in Vj. 

Another way to write Vj-1 is 𝑉𝑗⨁𝑊𝑗 which indicates that Wj is the orthogonal complement of Vj in Vj-1. It contains all vectors in Vj-1, but orthogonal to Vj. The direct sum operator ⨁ helps to relate vector spaces.  It is a union of all the sums represented by any given signal xa + xb, which is in a nutshell just adding the signals. 

We can also write PVj-1f as PWjf, where PWjf is the projection of f onto Wj, which are the details not indicated in Vj.

Then we can write the function as

f = PV0f + PW0f + PW-1f + PW-2f + ... 

where PV0f is the approximation to f at scale 2^0, then W0f is scale to 2^-1, W-1f is 2^-2, and et cetera. V is the coarses scale and as you progress through Wj, Wj-1, we get into much much finer details. Here, the bigger the square is, the finer the detail. 

So we start with the input and for the highpass components, we will output as wavelet coefficients. For the lowpass, we will iterate to the coarser scale recursively. Performing this operation gives low complexity overall. 

The approximation of functions indicates that they have finite energy which means ∫tϵR |f(t)|^2 dt <  ∞. Under some technical conditions the f(t) doesn't have any discontinuities. A example of a Haar MRA space formed by a scaling function is 

If the function f(k) is a taylor approximation then it is the average of the Taylor approximation at the 2 extremes of a given range. We can approximate f as

and the error as 

.

If there is a discontinuity, we will take the average of the functions. There will be way too many discontinuities in a Fourier transform for it to work properly. With Haar wavelet we can approximate fj(k) and ej(k) properly.