Everything you always wanted to know about
* the dot product,
* change of basis, and
* the discrete fourier transform
abridged. Jim Mahoney, Fall 2004
-------------------------------------------------
I. Discretized waves
So let's say we sample a sound wave.
What we get is a bunch of numbers, at evenly spaced times
wave = [ 10, -5, 20, -2, ... ]
spaced, say 1/44000 sec apart. The units are pressure, perhaps;
that's not important right now.
We would like to write this as a sum of sinusoids
or complex exponentials. In other words, we'd like to write
something like
wave = A * [ 0, 5, 8, 5, 0, ... ] # period ~8 sin
+ B * [ 8, 5, 0, -5, -8, ... ] # period ~8 cos
+ C * [ 1, 1, 1, 1, 1, ... ] # constant component
+ D * [ 1, -1, 1, -1, ... ] # highest frequency
+ ...
for a variety of different discretized sinusoids.
The first question is, how do we solve for the constants
A, B, C, ... ?
---------------------------------------------------
II. Basis Vectors
To see the answer, we need to think of this problem
as a change of basis. Let's jump to something simpler,
from 2D geometry
Any vector is
V = [ Vx, Vy ]
which we can think of as
V = Vx [1,0] + Vy [0,1]
where [1,0] and [0,1] are the "basis vectors".
We can if we like use another basis, say one rotated
by 45 degrees.
e1 = [ 1, 1 ] * 1/sqrt(2)
e2 = [ 1, -1] * 1/sqrt(2)
This is an "orthonormal" basis :
each of these vectors has unit length,
and they're orthoganol to each other.
How do we know that they're orthogal?
Because their dot product is zero.
(If you don't remember dot product, nows the time to go review that.)
For vectors M and N,
M dot N = |M| |N| cos(theta), where theta = angle between 'em,
= Mx Nx + My Ny, in rectangular coordinates.
We can write a vector like V in terms of the regular basis,
or in terms of the new e1 and e2 vectors.
V = Vx [1,0] + Vy [0,1] = V1 e1 + V2 e2
Exercise 1:
(a) Plug in e1, e2, and solve for V1, V2 in terms of Vx, Vy.
(b) Pick some actual numbers, and do this out.
---------------------------------------------------------
III. Dot Product to the rescue
But it turns out there's a really cool way to solve
for V1, namely by doing a dot product with e1 on both sides.
What happens is that since (e1 . e2) = 0 and (e1 . e1) = 1,
the left side gets very simple.
V = [ Vx, Vy ] = V1 e1 + V2 e2
e1 . V = e1 . ( V1 e1 + V2 e2 )
= V1 (e1 . e1) + v2 (e1 . e2)
= V1
So V1 = e1 . V = 1/sqrt(2) [1, 1] . [Vx, Vy] = (1/sqrt(2))(Vx+Vy)
And boom - we have an answer.
Exercise 2:
Show that this method gives the same answer as what you
got for Exercise 1.
------------------------------------------------------------
IV. Matrices
As an aside, I'll point out that this whole thing can
be done with matrices in a very cool way.
(If you don't remember matrix row by column multiplcation,
go review that now.)
Exercise 3 (warm-up)
Multiply the following 2x2 matrix by the 2x1 column vector
[ 0 1 ] [ 7 ] = [ ? ]
[ -2 3 ] [ 2 ] [ ? ]
In terms of the column vector V, this look like
V = [ Vx ] = V1 [e1] + V2 [e2] = ( V1 [ 1 ] + V2 [ 1 ] ) * 1/sqrt(2)
[ Vy ] [ ] [ ] [ 1 ] [-1 ]
or as a single matrix formula
[ Vx ] = 1/sqrt(2) [ 1 1 ] [ V1 ]
[ Vy ] [ 1 -1 ] [ V2 ]
The matrix
1/sqrt(2) [ 1 1 ]
[ 1 -1 ]
is a "change of basis" matrix, from
our regular (x,y) basis of [1,0], [0,1]
to the e1, e2 basies. In fact, the four terms are just
the dot products of ihat [1,0] and jhat [0,0] with
e1 and e2.
Exercise 4: Verify this last fact.
----------------------------------------------------------------
V. Discrete Fourier Transforms
So lets get back to why we're doing all this basis stuff.
We don't want to do 2-dimensional transforms, we want to
to things like 1024 dimensional transforms, with 1024 sampled points.
Our "time" basis consists of functions that look like
[1,0,0,0,0,0,0,0,0,...] sound pulse at t=t0
[0,1,0,0,0,0,0,0,0,...] sound pulse at t=t0 + dt
[0,0,1,0,... ] sound pulse at t=to + 2 dt
...
while our "sinusoid" (or complex exponential) basis has functions like
[1,-1, 1, -1, 1, -1, ...] high frequency
[1, 1, 1, 1, 1, 1, ...] zero frequency
[0, 5, 8, 5, 0, -5, -8, ...] sinusoid
[...]
and we want to solve for "how much" we have of each sinusoid,
[4, 10, -6, 12, 2, 23, ... ] = time series
A [ 1, -1, 1, -1, 1, -1, ... ] sum of sines
+ B [0, 5, 8, 5, 0, -5, -8, ...]
+ ...
by figuring out what the A, B, C, ... are.
OK, so here's the punch line : we do a ** dot product **
on both sides with one of the sin functions.
This trick works for the discrete case (sums)
or the continuous case (integrals)
We define
f(t) . g(t) == integral[ f*(t) g(t) dx ] contiuous
== sum_over_i[ f*(i) g(i) ] discrete
where f*(x) is the complex conjugate of f,
if we're doing complex numbers
Exercise 5.
Show that integral( sin(m x) sin(n x) dx ) = 0
if m,n are different.
(This means that sines of different frequences are ** orthogonal **)
--------------------------------------------------------------
VI. Examples
OK, time to make this concrete. We'll do several examples,
both continuous, discrete, and a mixture in between.
a) A string fixed from x = 0 to L, y(0)=y(L)=0.
1. First, find the cos() or sin() functions that fit.
What (spatial) frequencies are we talking about?
2. Second, let's pick a specific shape for y(x),
typical choices are a square triangle wave,
since the integrals are do-able that way.
3. Then find one of the sinusoid amplitudes
by multiplying by one of the sines, and integrating.
Repeat to get more amplitudes
b) Discrete complex exponentials
see for example
http://mathworld.wolfram.com/DiscreteFourierTransform.html
1. Let's do N=8 as one that's fairly manageable,
taking 8 sound samples
y[n] = y[t_n] = [ y0, y1, y2, y3, y4, y5, y6, y7, y8 ]
= sum over k=1,N { Ck exp[ 2 pi i k n / N] }
where n = 0..7 labels which time, t_n = n * dt
and k = 0..7 labels which frequency, f_k = k * df
and Ck is how much amplitude we have of frequency f_k
2. What are the frequencies that work ?
T = N dt = total time interval
dk = T/N = frequency
more coming ...