Database Reference
In-Depth Information
X
=
X
0
,...,X
N−
1
of complex numbers given by:
N−
1
e
−i
2
π
N
j
.
X
k
=
(2.17)
j
=0
The original signal can be reconstructed by the inverse Fourier transform
of
X
,whichisgivenby:
N−
1
X
k
e
i
2
π
N
j
.
x
j
=
(2.18)
k
=0
In [1], Agrawal
et al.
suggest using the DFT for dimensionality re-
duction of long observation sequences. They argue that most real sig-
nals only require a few DFT coe
cients for their approximation. Thus
similarity search can be performed only over the first few DFT coe
-
cients, instead of the full observation sequence. This provides an e-
cient and approximate solution to the problem of similarity search in
high-dimensional spaces. They use the Euclidean distance as the dis-
similarity measure.
5.6.2 Discrete Wavelet Transform.
Wavelets can be thought
of as a generalization of the Fourier transform to a much larger family of
functions than sine and cosine. Mathematically, a wavelet is a function
ψ
j,k
defined on the real numbers
, which includes an integer transla-
tion by
k
, also called a shift, and a dyadic dilation (a product by the
powers of two), known as stretching. The functions
ψ
j,k
play a similar
role as the exponential functions in the Fourier transform:
ψ
j,k
form an
orthonormal basis for the
L
2
(
R
) space. The
L
2
(
) space consists of all
the functions whose
L
2
norm is finite. Particularly, the functions
ψ
j,k
,
where
j
and
k
are integers are given as follows:
R
R
ψ
j,k
(
t
)=2
j/
2
ψ
(2
j
t
−
k
)
.
(2.19)
Similar to the Fourier transform, by using the orthonormal basis func-
tions
ψ
j,k
, we can uniquely express a function
f
L
2
(
∈
R
) as a linear
combination of the basis functions
ψ
j,k
as follows:
f
=
j,k∈
Z
<f,ψ
j,k
>ψ
j,k
,
(2.20)
where
<f,g>
:=
R
fgdx
is the usual inner product of two functions in
L
2
(
R
).
