yawiki.org entry for Fast wavelet transform

	Navigation Home Recent Most Active Popular Blog Credits RSS
	Interaction Register Statistics
	Help Suggestions Contact Us How to Edit Help

[Edit]

The Fast Wavelet Transform is a mathematical algorithm designed to turn a waveform or signal in the time domain into a sequence of coefficients based on an orthogonal basis of small finite waves, or wavelets.
It has as theoretical foundation the device of a finitely generated, orthogonal multiresolution analysis (MRA). In the terms given there, one selects a sampling scale J with sampling rate of 2^J per unit interval, and projects the given signal f onto the space

V_J

; in theory by computing the scalar products

$s^_n:=2^J langle f(t),phi(2^J t-n)$

angle,

where

phi

is the scaling function of the chosen wavelet transform; in praxis by any suitable sampling procedure under the condition, that the signal is highly oversampled, so

$P_J f (x):=sum_ s^_n,phi(2^Jx-n)$

is the orthogonal projection or at least some good approximation of the original signal in

V_J

.

The MRA is characterised by its scaling sequence

$a=(a_,dots,a_0,dots,a_N)$ or, as Z-transform, $a(Z)=sum_^Na_nZ^n$

and its wavelet sequence

$b=(b_,dots,b_0,dots,b_N)$ or $b(Z)=sum_^Nb_nZ^n$

(some coefficients might be zero). Those allow to compute the wavelet coefficients

d^_n

, at least some range k=M,...,J-1, without having to approximate the integrals in the corresponding scalar products. Instead, one can directly, with the help of convolution and decimation operators, compute those coefficients from the first approximation

s^

    Fast wavelet transform
        Forward DWT
        Inverse DWT

top

Forward DWT
One computes recursively, starting with the coefficient sequence

s^

and counting down from k=J-1 down to some M,

s^_n:=rac12 sum_^N a_m s^_ or $s^(Z):=(downarrow 2)(a^$
(Z)cdot s^(Z))

and

d^_n:=rac12 sum_^N b_m s^_ or $d^(Z):=(downarrow 2)(b^$
(Z)cdot s^(Z))
,

for k=J-1,J-2,...,M and all $ninZ$ . In the Z-transform notation:

The downsampling operator $(downarrow 2)$ reduces an infinite sequence, given by its Z-transform, which is simply a Laurent series, to the sequence of the coefficients with even indices, $(downarrow 2)(c(Z))=sum_c_Z^k$ .

The starred Laurent-polynomial $a^$
(Z) denotes the adjoint filter, it has time-reversed adjoint coefficients, $a^$
(Z)=sum_^N a_n^
Z^. (The adjoint of a real number being the number itself, of a complex number its conjugate, of a real matrix the transposed matrix, of a complex matrix its hermitian adjoint).

Multiplication is polynomial multiplication, which is equivalent to the convolution of the coefficient sequences.

It follows that

$P_k f (x):=sum_ s^_n,phi(2^kx-n)$

is the orthogonal projection of the original signal f or at least of the first approximation $P_J f (x)$ onto the subspace $V_k$ , that is, with sampling rate of 2^k per unit interval. The difference to the first approximation is given by

$P_J f (x)=P_k f (x)+D_k f (x)+dots+D_f (x)$ ,

where the difference or detail signals are computed from the detail coefficients as

$D_k f (x):=sum_ s^_n,psi(2^kx-n)$ ,

with $psi$ denoting the mother wavelet of the wavelet transform.

top
Inverse DWT
Given the coefficient sequence $s^$ for some M and all the difference sequences $d^$ , k=M,...,J-1, one computes recursively

s^_n:=sum_^N a_k s^_+sum_^N b_k d^_ or $s^(Z)=a(Z)cdot(uparrow 2)(s^(Z))+b(Z)cdot(uparrow 2)(d^(Z))$
for k=J-1,J-2,...,M and all $ninZ$ . In the Z-transform notation:

The upsampling operator $(uparrow 2)$ creates zero-filled holes inside a given sequence. That is, every second element of the resulting sequence is an element of the given sequence, every other second element is zero or $(uparrow 2)(c(Z)):=sum_c_nZ^$ . This linear operator is, in the Hilbert space $ell^2(Z,R)$ , the adjoint to the downsampling operator $(downarrow 2)$ .

	Source Privacy License Download Contact Us Atlas Scientus.org Dictionary (Yet Another Wiki) RC : 1.39 MIT OpenCourseWare This article is licensed under the GNU Free Documentation License [copyleft]. It uses material from the Wikipedia article "Fast wavelet transform". link