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 ...