1
00:00:08,059 --> 00:00:13,006
Ok, this is the lecture where
complex number's coming in
2
00:00:13,041 --> 00:00:16,717
Complex number has
slipped into this course
3
00:00:16,746 --> 00:00:22,726
Because even a real matrix can
have complex eigenvalues
4
00:00:22,761 --> 00:00:29,267
So we met complex numbers there as the
eigenvalues and complex eigenvectors
5
00:00:29,302 --> 00:00:35,431
And we…
this is probably the last…
6
00:00:35,962 --> 00:00:39,681
We have a lot of other things to
do about eigenvalues and eigenvectors
7
00:00:39,940 --> 00:00:42,796
And that will be mostly real
8
00:00:42,831 --> 00:00:46,729
But at one point
somewhere we have to see
9
00:00:46,764 --> 00:00:50,824
What you do when the numbers
become complex numbers
10
00:00:50,859 --> 00:00:54,365
What happens when the
vectors are complex
11
00:00:54,400 --> 00:00:55,978
when the matrices are complex
12
00:00:56,013 --> 00:00:59,436
When...
what's the inner products of two
13
00:00:59,471 --> 00:01:02,306
The dot product of two
complex vectors?
14
00:01:03,207 --> 00:01:05,257
We just have to make the change
15
00:01:05,292 --> 00:01:08,687
Just see what is the change
when numbers become complex
16
00:01:08,722 --> 00:01:16,680
Then, can I tell you about the most
important example of complex matrices
17
00:01:16,715 --> 00:01:20,425
It comes in the Fourier matrix
18
00:01:20,460 --> 00:01:25,322
So, the Fourier matrix without describe
is a complex matrix
19
00:01:25,357 --> 00:01:28,503
It's certainly the most
important complex matrix
20
00:01:28,538 --> 00:01:33,236
It's the matrix that we
need in the Fourier transform
21
00:01:34,716 --> 00:01:38,346
And really, the special thing that
I want to tell you about
22
00:01:38,381 --> 00:01:41,904
Is what's called Fast Fourier Transform
23
00:01:42,713 --> 00:01:45,679
And everybody refers to it as FFT
24
00:01:45,714 --> 00:01:49,853
And in all computers, and it's used
25
00:01:49,888 --> 00:01:53,652
It is being used as we
speak in a thousand places
26
00:01:53,687 --> 00:01:59,403
Because it's like a transformed
whole industry
27
00:01:59,438 --> 00:02:02,931
to be able to do the
Fourier transform fast
28
00:02:02,966 --> 00:02:05,308
Which means, multiplying…
29
00:02:05,343 --> 00:02:11,521
How do I multiply fast by
that matrix, by that n by n matrix
30
00:02:11,556 --> 00:02:16,388
Normally multiplication by
an n*n matrix
31
00:02:16,415 --> 00:02:21,379
will normally be n-squared
multiplication
32
00:02:22,328 --> 00:02:23,936
Because I've got n-squared entries
33
00:02:23,971 --> 00:02:26,780
And none of them is 0,
this is a full matrix
34
00:02:27,588 --> 00:02:30,724
And it's a matrix with
orthogonal columns
35
00:02:30,759 --> 00:02:33,554
And it's just like the best matrix
36
00:02:33,589 --> 00:02:39,774
And this Fast Fourier Transform
idea reduces this n-squared
37
00:02:39,774 --> 00:02:45,983
which was slowing up the calculation
of Fourier Transform
38
00:02:46,018 --> 00:02:48,613
Down to n log(n)
39
00:02:50,851 --> 00:02:53,846
n log(n)
log to the base 2, actually
40
00:02:54,585 --> 00:02:57,145
And it's this...
when that hit
41
00:02:57,900 --> 00:03:02,084
when that possibility hit
It made a big difference
42
00:03:02,119 --> 00:03:08,080
Everybody realized gradually what…
43
00:03:08,465 --> 00:03:09,990
That this simple idea
44
00:03:10,025 --> 00:03:13,017
You'll see it's just a simple
matrix factorization
45
00:03:13,286 --> 00:03:14,997
But it changed everything
46
00:03:15,032 --> 00:03:20,190
OK. So, I want to talk about complex
vectors and matrices in general
47
00:03:20,225 --> 00:03:22,501
Recap a little bit from last time
48
00:03:22,536 --> 00:03:27,123
And the Fourier matrix in particular
49
00:03:27,158 --> 00:03:30,240
OK. So, what's the deal?
50
00:03:31,578 --> 00:03:34,821
All right, the main point is,
what about length?
51
00:03:35,908 --> 00:03:38,044
I'm giving a vector
52
00:03:38,079 --> 00:03:39,997
I have a vector x
53
00:03:40,229 --> 00:03:45,486
Or let me call it z, as a reminder
that is complex, for the moment
54
00:03:45,521 --> 00:03:49,093
But I can…
later I'll call it component x
55
00:03:49,128 --> 00:03:50,722
It'll be complex number
56
00:03:50,757 --> 00:03:55,572
But vectors z1, z2… down to zn
57
00:03:56,537 --> 00:04:00,631
So the only novelty is
it's not in Rn anymore
58
00:04:01,538 --> 00:04:04,593
It's in complex N-dimensional space
59
00:04:04,628 --> 00:04:07,304
Each of those numbers is
a complex number
60
00:04:07,339 --> 00:04:12,420
So this z, z1 is in Cn
61
00:04:12,420 --> 00:04:16,427
N-dimensional complex space
instead of Rn
62
00:04:17,979 --> 00:04:19,780
It's just a different letter there
63
00:04:19,815 --> 00:04:22,746
But now the point about
its length is what?
64
00:04:23,434 --> 00:04:29,815
The point about its length
is that trans(z), is no good
65
00:04:34,540 --> 00:04:43,179
trans(z)z, if I just put down trans(z)
here, it would be z1, z2, to zn
66
00:04:45,899 --> 00:04:49,706
During that multiplication,
it doesn't give me the right thing
67
00:04:49,741 --> 00:04:51,184
Why not?
68
00:04:51,219 --> 00:04:56,404
Because the length squared
should be positive
69
00:04:57,277 --> 00:05:01,806
And if I multiply...
Suppose this is like 1 and i
70
00:05:01,841 --> 00:05:06,016
What's the length of the vector
with component 1 and i?
71
00:05:06,918 --> 00:05:07,796
What if I do this?
72
00:05:07,831 --> 00:05:13,266
So n is just 2, I'm in C2 2-dimensional
space complex space
73
00:05:13,301 --> 00:05:16,630
With the vector whose components
are 1 and i
74
00:05:16,665 --> 00:05:23,477
All right, so if I took 1 * 1,
and i * i, and added
75
00:05:23,648 --> 00:05:26,742
trans(z)z would be 0!
76
00:05:27,112 --> 00:05:30,904
But I don't, that vector is not...
doesn't have length 0
77
00:05:30,939 --> 00:05:33,121
The vector with component is 1 and i
78
00:05:34,165 --> 00:05:35,626
This multiplication…
79
00:05:35,866 --> 00:05:42,097
What I really want is conj(z1)*z1
80
00:05:42,132 --> 00:05:46,888
You remember that conj(z1)z1 is…
81
00:05:46,923 --> 00:05:50,695
So you see that first step
will be conj(z1)z1
82
00:05:50,730 --> 00:05:54,044
Which is the magnitude of z1^2
83
00:05:54,079 --> 00:05:55,270
Which is…
84
00:05:55,305 --> 00:05:56,073
What I want?
85
00:05:57,061 --> 00:06:00,273
That's like 3^2 or 5^2?
86
00:06:00,466 --> 00:06:04,501
Now if z1 is i
87
00:06:07,099 --> 00:06:14,861
then i*(-i) gives 1
plus 1
88
00:06:15,037 --> 00:06:22,893
So the component i
its marginis squared is +1
89
00:06:22,928 --> 00:06:23,642
That's great!
90
00:06:23,677 --> 00:06:26,032
So, what I want to do then,
is do that…
91
00:06:26,067 --> 00:06:31,301
I want z1-bar z1, z2-bar z2, zn-bar zn
92
00:06:31,336 --> 00:06:34,421
You remember this complex conjugate
93
00:06:34,456 --> 00:06:38,400
So here's the point
94
00:06:38,435 --> 00:06:42,574
Now I can erase this no good
and put is good
95
00:06:45,148 --> 00:06:50,453
Because that now gives the answer 0
for the 0-vector of course
96
00:06:50,488 --> 00:06:55,222
But it gives a positive length,
squared for any other vector
97
00:06:56,092 --> 00:06:59,283
So, it's the right definition of length
98
00:06:59,318 --> 00:07:02,846
And essentially the message is
99
00:07:02,881 --> 00:07:06,054
That will always going to be taking…
100
00:07:07,195 --> 00:07:10,484
When we transpose
we also take complex conjugate
101
00:07:10,711 --> 00:07:13,734
So, let's find the length of 1…
102
00:07:13,769 --> 00:07:18,562
So the vector (1, i), that's z
103
00:07:18,597 --> 00:07:20,036
That's the vector z
104
00:07:20,071 --> 00:07:22,885
Now I take the conjugate of 1 is 1
105
00:07:22,920 --> 00:07:25,006
The conjugate of i is -i
106
00:07:25,566 --> 00:07:31,012
I take these vectors,
I get 1+1; I get 2
107
00:07:33,523 --> 00:07:38,131
So, that's the vector, and that's the
vector of length square root of 2
108
00:07:38,471 --> 00:07:40,135
Square root of 2 is the length.
109
00:07:40,170 --> 00:07:44,223
They're not the 0 that we
would have got from 1 - i^2
110
00:07:44,224 --> 00:07:45,206
Ok
111
00:07:46,913 --> 00:07:52,427
So the message really is, whenever we
transpose, we also take conjugates
112
00:07:52,462 --> 00:07:56,719
So here's the symbol,
one symbol to do both
113
00:07:57,556 --> 00:08:04,596
So that symbol H
it stands for a guy named Adam Hermit
114
00:08:04,631 --> 00:08:09,838
who didn't actually pronounce the 'H'
but let's pronounce that
115
00:08:09,873 --> 00:08:14,106
So I would call that Z Hermitian Z.
116
00:08:14,578 --> 00:08:17,206
Oh, let me write that word Her…
117
00:08:17,206 --> 00:08:19,285
So his name was Hermit
118
00:08:21,652 --> 00:08:26,985
and then we make it into
an adjective Hermitian
119
00:08:28,036 --> 00:08:33,458
So, herm(Z)Z, ZH Z
OK
120
00:08:34,898 --> 00:08:41,034
So, that's the length squared
121
00:08:41,069 --> 00:08:43,126
Now, what's the inner product?
122
00:08:43,923 --> 00:08:45,689
Well, they should match
123
00:08:45,724 --> 00:08:48,963
The inner product of 2 vectors
124
00:08:49,902 --> 00:08:51,968
So inner product
125
00:08:53,933 --> 00:08:55,944
Is no longer…
126
00:08:55,979 --> 00:09:01,722
Used to be trans(Y) X,
that's for real vectors
127
00:09:01,757 --> 00:09:07,744
For complex vectors, whenever
we transpose, we also take the conjugate
128
00:09:07,779 --> 00:09:11,643
So, it's herm(Y) X
129
00:09:12,716 --> 00:09:15,174
Of course, it's not real
anymore usually
130
00:09:15,209 --> 00:09:19,423
The inner product will
usually be complex number
131
00:09:20,358 --> 00:09:22,836
But if Y and X are the same
132
00:09:22,871 --> 00:09:24,973
It's the same Z
133
00:09:25,008 --> 00:09:28,823
Then we have herm(Z) Z
134
00:09:28,858 --> 00:09:31,210
we have the length-squared
that's what we want
135
00:09:31,245 --> 00:09:35,922
The inner product of a vector with itself
should be its length squared
136
00:09:36,448 --> 00:09:40,950
So this is like forced on us
because this is forced on us
137
00:09:41,315 --> 00:09:46,726
So this, everybody's picking up
what's this equals
138
00:09:46,761 --> 00:09:52,432
This is z1^2 + zn^2
139
00:09:52,685 --> 00:09:54,530
That's the length squared
140
00:09:54,565 --> 00:09:57,502
And that's the inner product
that we have to go with
141
00:09:57,781 --> 00:09:59,974
So it could be a complex number now
142
00:10:01,566 --> 00:10:05,232
One more change
well, 2 more changes
143
00:10:05,267 --> 00:10:09,191
We've got to change the
idea of a symmetric matrix
144
00:10:09,383 --> 00:10:12,803
So I'll just recap on
symmetric matrices
145
00:10:12,838 --> 00:10:20,080
Symmetric means trans(A) = A
146
00:10:20,892 --> 00:10:22,589
But not…
147
00:10:22,624 --> 00:10:29,558
No good if A is complex
148
00:10:31,328 --> 00:10:33,615
So what do we…
149
00:10:33,650 --> 00:10:37,638
Instead, if I…
150
00:10:38,545 --> 00:10:41,181
That applies perfectly to real matrices
151
00:10:41,216 --> 00:10:43,578
But now if my matrices are complex
152
00:10:43,613 --> 00:10:50,671
I want to take the transpose
and the conjugate to equal A
153
00:10:52,774 --> 00:10:57,529
So, that's the right complex
version of symmetry
154
00:10:57,564 --> 00:11:00,394
The symmetry now means
155
00:11:00,429 --> 00:11:04,400
When I transpose, it's a flip across
the diagonal, and take conjugate
156
00:11:04,435 --> 00:11:05,570
So, for example…
157
00:11:05,605 --> 00:11:07,204
Here would be an example.
158
00:11:08,142 --> 00:11:10,642
On the diagonal it would better be real
159
00:11:10,677 --> 00:11:14,887
Because when I flip it,
the diagonal's still there
160
00:11:15,667 --> 00:11:20,861
And when I take the complex
conjugate it has to be still there
161
00:11:20,896 --> 00:11:24,018
So it'd better be a real number,
let me say 2 and 5
162
00:11:24,996 --> 00:11:28,162
What about entries of the diagonal?
163
00:11:28,421 --> 00:11:36,714
If this entry is, say, 3+i,
then this entry had better be...
164
00:11:37,912 --> 00:11:39,164
Because I want…
165
00:11:39,199 --> 00:11:40,248
Whatever this
166
00:11:40,283 --> 00:11:43,977
When I transpose, it'll show up here
and I conjugate
167
00:11:44,012 --> 00:11:47,280
So I need 3 - i there
168
00:11:48,339 --> 00:11:56,532
So there's the matrix that corresponds
to the symmetry, but it's complex
169
00:11:56,567 --> 00:12:01,309
And those matrices are called
Hermitian Matrices
170
00:12:02,233 --> 00:12:08,140
Hermitian Matrices
A^H = A, fine
171
00:12:09,706 --> 00:12:13,701
OK, and those matrices
have real eigenvalues
172
00:12:14,675 --> 00:12:17,288
And they have perpendicular
eigenvectors
173
00:12:17,323 --> 00:12:18,960
What does perpendicular mean?
174
00:12:19,987 --> 00:12:22,830
Perpendicular means the inner product
175
00:12:22,865 --> 00:12:25,464
So, let's go on to perpendicular
176
00:12:29,096 --> 00:12:32,044
Well, when I had perpendicular vectors
177
00:12:32,079 --> 00:12:37,761
For example, they were like
q1, q2, up to qn
178
00:12:38,627 --> 00:12:43,020
That's my...Q is my letter that
I used for perpendicular
179
00:12:43,055 --> 00:12:46,576
Actually, I also mean unit length
180
00:12:46,924 --> 00:12:50,126
So those are perpendicular unit vectors
181
00:12:50,161 --> 00:12:54,223
But now what's...
what's the orthonormal basis?
182
00:12:54,258 --> 00:12:56,094
I'll still use these words
183
00:12:56,094 --> 00:12:59,997
But how do I compute perpendicular
184
00:13:00,032 --> 00:13:01,564
How do I check perpendicular?
185
00:13:01,599 --> 00:13:08,014
This means that the inner
product of qi with qj
186
00:13:08,297 --> 00:13:12,753
But now I not only transpose,
I must conjugate, right?
187
00:13:12,788 --> 00:13:17,825
To get 0, if i is not j
188
00:13:17,860 --> 00:13:20,951
And 1, if i=j
189
00:13:21,776 --> 00:13:24,224
So it's the unit vector
meaning unit length
190
00:13:25,178 --> 00:13:26,532
Orthogonal
191
00:13:27,373 --> 00:13:29,184
All the angles are right angles
192
00:13:29,184 --> 00:13:33,805
But these are angles in complex
N-dimensional space
193
00:13:34,210 --> 00:13:45,169
So it's qi-bar-transpose,
or for short, herm(qi) qj
194
00:13:45,204 --> 00:13:47,498
So it will still be true
195
00:13:47,533 --> 00:13:50,923
So, let me… again I will
create a matrix out of those guys
196
00:13:52,362 --> 00:13:56,133
The matrix will have
these q's in its columns
197
00:13:56,168 --> 00:13:58,513
q2 to qn
198
00:14:01,577 --> 00:14:06,069
And I want to turn that into
matrix language, just like before
199
00:14:06,848 --> 00:14:08,165
What does that mean?
200
00:14:08,200 --> 00:14:10,340
That means I want all
these inner products
201
00:14:10,375 --> 00:14:15,071
So I take these columns of Q,
multiply by their rows
202
00:14:15,106 --> 00:14:19,898
So it used to be trans(Q)Q = I, right?
203
00:14:22,066 --> 00:14:24,442
This was an orthogonal matrix
204
00:14:28,522 --> 00:14:30,093
But what's changed?
205
00:14:31,966 --> 00:14:33,962
These are now complex vectors
206
00:14:34,694 --> 00:14:39,973
Their inner products are involved
conjugating, the first factor
207
00:14:41,515 --> 00:14:46,034
So, it's not...
it's the conjugate of trans(Q)
208
00:14:46,069 --> 00:14:49,818
Q-bar-transpose Q, Q^H
209
00:14:49,853 --> 00:14:51,676
So, can I call this…
210
00:14:51,711 --> 00:14:56,854
Let me call this Q^H Q
which is I
211
00:14:56,889 --> 00:14:58,263
So, that's our new...
212
00:14:58,583 --> 00:15:00,737
You see I'm just translating
213
00:15:00,772 --> 00:15:04,752
And the book on one page
gives a little like dictionary
214
00:15:07,569 --> 00:15:12,010
The right words in the real case Rn
215
00:15:12,045 --> 00:15:18,448
And the corresponding words in
the complex case for the vector space Cn
216
00:15:18,483 --> 00:15:20,838
Of course Cn is a vector space
217
00:15:21,746 --> 00:15:24,446
The numbers we multiply
are now complex numbers
218
00:15:24,481 --> 00:15:29,051
We're just moving into complex
in dimensional space
219
00:15:29,051 --> 00:15:34,629
Ok, now actually I have to say
220
00:15:34,664 --> 00:15:39,698
We change the word symmetric
to hermation for those matrices
221
00:15:39,733 --> 00:15:45,315
People also change this word
orthogonal into another word
222
00:15:45,350 --> 00:15:47,142
That happens to be unitary
223
00:15:50,093 --> 00:15:58,798
as a word that applies the signals that we
might be dealing with a complex matrix
224
00:15:58,833 --> 00:16:01,061
So what's a unitary matrix?
225
00:16:01,851 --> 00:16:03,861
Just like an orthogonal matrix
226
00:16:04,758 --> 00:16:12,420
It's a square, n*n matrix,
with orthonormal columns
227
00:16:13,120 --> 00:16:15,611
perpendicular columns, unit vectors
228
00:16:15,646 --> 00:16:22,483
Unit vectors computed by
a perpendicular and computed by...
229
00:16:22,518 --> 00:16:26,856
Remembering that there is
a conjugate as well as a transverse
230
00:16:26,891 --> 00:16:29,304
Ok, so those are the words
231
00:16:30,290 --> 00:16:34,655
Now I'm ready to get into the
substance of the lecture
232
00:16:34,690 --> 00:16:39,479
which is the most famous
complex matrix
233
00:16:39,514 --> 00:16:43,310
which happens to be one of these guys
234
00:16:43,345 --> 00:16:47,622
It has orthogonal columns.
235
00:16:49,514 --> 00:16:52,142
And it's named after Fourier
236
00:16:52,177 --> 00:16:54,570
because it comes into the
Fourier transform
237
00:16:54,605 --> 00:16:57,609
So it's the matrix that all around us
238
00:16:57,644 --> 00:16:58,169
Ok
239
00:17:00,457 --> 00:17:01,831
Let me tell you what it is
240
00:17:01,866 --> 00:17:05,997
First of all, in the n*n case
241
00:17:07,519 --> 00:17:12,562
Then often I'll let n be 4, because
4 is the good size to work with
242
00:17:13,176 --> 00:17:15,829
But here is the n*n Fourier matrix
243
00:17:19,847 --> 00:17:22,645
its first column
is the vector of 1
244
00:17:26,475 --> 00:17:27,712
n by n of course
245
00:17:27,747 --> 00:17:31,627
its second column is the power...
246
00:17:32,271 --> 00:17:40,650
actually better if I move from the math
department to EE for this one half hour
247
00:17:40,685 --> 00:17:43,428
then please let me move back again
248
00:17:45,802 --> 00:17:48,312
What's the difference between
those two departments
249
00:17:48,347 --> 00:17:52,511
It's just math starts counting at one
250
00:17:52,546 --> 00:17:57,165
and electric engineering starts
counting at 0.
251
00:17:57,974 --> 00:17:59,979
Actually they're probably right.
252
00:18:00,014 --> 00:18:02,946
So anyway, we'll give them, humor them
253
00:18:02,981 --> 00:18:05,615
So this is really the zero's column
254
00:18:06,640 --> 00:18:09,789
and the first column up to the n-1
255
00:18:09,824 --> 00:18:13,952
That's the one inconvenience
spot in the electric engineering
256
00:18:13,987 --> 00:18:16,737
All these expressions
start at zero, no problem
257
00:18:16,772 --> 00:18:23,865
But the end at n-1, well that's,
that's the difficulty
258
00:18:24,810 --> 00:18:26,349
That's called ….
259
00:18:26,384 --> 00:18:30,718
So what's, there are the power
of a number that I'm going to call W
260
00:18:30,753 --> 00:18:36,647
W square, W cube, W to the...
now what's the W here?
261
00:18:36,682 --> 00:18:38,073
What's the power?
262
00:18:38,108 --> 00:18:41,269
This was the zero's power,
first power, second power
263
00:18:41,304 --> 00:18:43,442
This will be n-1 power
264
00:18:45,427 --> 00:18:48,485
That's the column,
what's the next column?
265
00:18:48,520 --> 00:18:57,781
It's the power of W square, W fourth,
W the sixth, W to the 2(n - 1)
266
00:18:58,706 --> 00:19:01,029
And then more columns,
more columns, more columns
267
00:19:01,064 --> 00:19:02,491
And what's the last column?
268
00:19:04,813 --> 00:19:09,395
It's the powers of...
269
00:19:09,395 --> 00:19:12,615
just see, actually if we
look along rows
270
00:19:12,650 --> 00:19:19,261
This matrix is symmetric, symmetric
in the old, not quite perfect way
271
00:19:19,296 --> 00:19:22,462
Not perfect, because these numbers
are complex
272
00:19:23,224 --> 00:19:27,639
and so it's that first row is all one
273
00:19:27,674 --> 00:19:30,920
1, w, w square, up to the w( n-1 )
274
00:19:30,955 --> 00:19:36,792
that's the, the last column is
the powers of w to the n -1
275
00:19:36,827 --> 00:19:41,832
So this guy matches that, and
finally we get w to something here
276
00:19:45,426 --> 00:19:48,257
I guess we could actually
figure out what that something is
277
00:19:48,984 --> 00:19:50,961
What are the entries of this matrix?
278
00:19:50,996 --> 00:19:57,191
(I,j) entry of this matrix
279
00:19:59,317 --> 00:20:03,866
Am I going to, you know
allow me to let i go from 0 to n-1
280
00:20:03,901 --> 00:20:09,376
So i and j go from 0 to n-1
281
00:20:09,411 --> 00:20:12,900
So the one, the (0,0) entry is one
282
00:20:12,935 --> 00:20:18,478
it's just this same w guy
to the power i times j.
283
00:20:24,775 --> 00:20:26,420
Let's see, I'm jumping into
the formula here
284
00:20:26,455 --> 00:20:28,097
And I've to tell you what W is
285
00:20:28,132 --> 00:20:31,160
and then you know everything
about this matrix
286
00:20:32,784 --> 00:20:36,604
So w is, well, shall we finish here?
287
00:20:36,639 --> 00:20:40,315
What was this,
this is the n-1 n-1 entry
288
00:20:40,350 --> 00:20:45,947
This is the w to the (n-1) square
everything's looking like a mess here
289
00:20:46,763 --> 00:20:52,119
Because we have, not too bad
because all the entries of powers of W
290
00:20:54,446 --> 00:20:55,995
That none of them is 0
291
00:20:56,030 --> 00:20:57,823
this is a full matrix
292
00:20:58,993 --> 00:21:01,426
but W is a very special number
293
00:21:02,146 --> 00:21:09,211
W is the special number
whose nth power is one
294
00:21:11,020 --> 00:21:14,480
In fact, actually there are
n numbers like that
295
00:21:15,224 --> 00:21:17,215
one of them is 1, of course
296
00:21:17,250 --> 00:21:26,268
But the one...the w we want is
the angel is two pile over n
297
00:21:30,859 --> 00:21:33,252
Got what I mean?
n over two π
298
00:21:35,079 --> 00:21:39,562
no, two π over n,
w is the e of the i
299
00:21:39,597 --> 00:21:45,866
And the angle is 2π over n, right.
300
00:21:45,901 --> 00:21:48,670
Where is this w and the complex plane?
301
00:21:49,770 --> 00:21:52,252
It's on the unit surf, right?
302
00:21:52,287 --> 00:22:01,057
This, it's the cosign of 2π over n
plus i times the sign of 2π over n
303
00:22:01,977 --> 00:22:04,654
But actually, forget this
304
00:22:05,421 --> 00:22:11,375
it's never good to work with
the real and imaginary parts
305
00:22:11,410 --> 00:22:16,393
The rectangular coordinates
when we're taking powers
306
00:22:16,428 --> 00:22:20,162
To take that to the 10th power,
we can't see what we're doing
307
00:22:20,197 --> 00:22:24,765
To take this form to the 10th power,
we see immediately what we are doing
308
00:22:24,800 --> 00:22:27,974
It would be either the π 20 over n
309
00:22:28,794 --> 00:22:31,174
so when a matrix is full of powers
310
00:22:31,209 --> 00:22:35,384
So it's this formula, and where
is this complex plane
311
00:22:35,419 --> 00:22:39,380
Here the real numbers,
here the imaginary axis
312
00:22:40,123 --> 00:22:42,742
Here's the unit circle of radius one
313
00:22:43,486 --> 00:22:46,736
and this number is on the unit circle
314
00:22:47,470 --> 00:22:51,656
And this angel which is one angel
of the full way round
315
00:22:51,691 --> 00:22:54,881
so if I draw, for example, N equal 6
316
00:22:55,428 --> 00:22:59,399
this would be either the 2π i,
2π/6
317
00:22:59,403 --> 00:23:02,658
this would be 1/6 of the way round
this would be 60 degree
318
00:23:05,644 --> 00:23:07,705
And where is w square?
319
00:23:08,486 --> 00:23:15,897
So my w is e to the 2πi/6 in this case
320
00:23:15,932 --> 00:23:19,023
In the six five, for the six five six
fourier transform
321
00:23:19,895 --> 00:23:24,530
It's totally constructed out
of this number and its powers
322
00:23:25,368 --> 00:23:27,086
So what are its powers
323
00:23:27,121 --> 00:23:30,198
Well, its powers are on
the unit circle, right?
324
00:23:30,233 --> 00:23:34,660
Because when I square a mate,
square a number, a complex number
325
00:23:35,638 --> 00:23:39,776
I square its absolute value
which gives me one again
326
00:23:40,512 --> 00:23:43,256
All the powers have around
the unit circle
327
00:23:43,291 --> 00:23:46,713
And the angel gets
doubled to 120
328
00:23:46,748 --> 00:23:51,407
So there is w square, there is w cube
there's w the fourth, there's w the fifth
329
00:23:51,442 --> 00:23:58,824
And there is w the sixth, as we hoped
w the sixth coming back to one
330
00:23:59,755 --> 00:24:02,874
So those are the six...
331
00:24:03,500 --> 00:24:09,184
can I say this on TV?
The six roots of one
332
00:24:09,219 --> 00:24:16,792
And this one, the primitive one
we say the first one, which is w
333
00:24:17,562 --> 00:24:20,951
Ok, so what, let me change, let me...
334
00:24:20,986 --> 00:24:23,683
I said I would probably
switch to n equal 4
335
00:24:23,718 --> 00:24:25,860
What's w for that?
336
00:24:26,564 --> 00:24:30,737
It's the fourth root of one
w to the fourth would be one
337
00:24:31,623 --> 00:24:36,686
W would be e to the 2πi over 4 now
338
00:24:41,679 --> 00:24:42,620
what's that?
339
00:24:43,744 --> 00:24:46,250
This is either the iπ over 2
340
00:24:46,285 --> 00:24:48,895
this a quarter of way around
the unit circle
341
00:24:48,930 --> 00:24:54,939
And that's exactly I,
a quarter of way around
342
00:24:56,611 --> 00:25:02,997
And sure enough, the power of I
I square, which is -1
343
00:25:03,032 --> 00:25:05,944
I cube, which is -I
344
00:25:05,979 --> 00:25:10,694
and finally I the fourth
which is 1, right?
345
00:25:11,473 --> 00:25:15,581
So there is w, w square,
w cube, w the fourth
346
00:25:15,616 --> 00:25:21,190
I'm really ready to write down this
free matrix for the four by four case
347
00:25:22,187 --> 00:25:24,672
Just so we see that clearly
348
00:25:24,707 --> 00:25:29,475
let me do it here,
f4 is, all right
349
00:25:29,510 --> 00:25:59,902
(see the board)
350
00:26:01,913 --> 00:26:03,495
You see the exponents?
351
00:26:03,530 --> 00:26:08,900
Form is nice, the exponent is the row
number times the column number
352
00:26:08,935 --> 00:26:10,363
All starting at 0
353
00:26:11,826 --> 00:26:16,297
Ok, and now I can put in
those numbers if you like
354
00:26:16,332 --> 00:26:36,024
(see the board)
355
00:26:41,015 --> 00:26:44,776
What's, why do I think that
matrix is so remarkable?
356
00:26:47,379 --> 00:26:54,307
It's the 4*4 matrix that comes into
the four points for A transverse
357
00:26:55,255 --> 00:27:00,247
When we want to find the free transform
the four points free transforms
358
00:27:01,380 --> 00:27:04,123
about vectors with four components
359
00:27:05,133 --> 00:27:11,312
We wanna multiply by this F4,
or we wanna multiply by F4 inverse
360
00:27:12,221 --> 00:27:14,233
One way we're taking the transform
361
00:27:14,268 --> 00:27:16,738
one way we're taking the
inverse transform
362
00:27:16,773 --> 00:27:21,240
Actually, it's so closed that it's easy
to confuse that
363
00:27:21,275 --> 00:27:25,724
the inverse of this matrix
will be 9th matrix also
364
00:27:28,374 --> 00:27:31,306
So and that's of course what makes it
365
00:27:33,801 --> 00:27:37,972
I guess Fourier knew that
he knew the inverse of this matrix
366
00:27:40,173 --> 00:27:44,765
As you see it just come from the fact
that columns are orthogonal
367
00:27:44,800 --> 00:27:47,224
from the facts that columns
are orthogonal
368
00:27:47,259 --> 00:27:52,617
we will quickly figure out
what is the inverse
369
00:27:54,306 --> 00:27:57,286
But Fourier didn't know,
didn't notice
370
00:27:57,321 --> 00:28:01,769
I think Gauss noticed it
but didn't make a point of it
371
00:28:01,804 --> 00:28:06,437
and then it turn out to be really
important was the fact that
372
00:28:06,472 --> 00:28:09,490
this matrix is so special that
you can break it up into
373
00:28:09,525 --> 00:28:11,702
9 pieces with lots of zeros
374
00:28:12,973 --> 00:28:15,038
factors that have lots of zeros
375
00:28:15,073 --> 00:28:20,956
and multiply by a...or by
a inverse very very fast, ok
376
00:28:22,712 --> 00:28:25,834
but how did it get into
the lecture first
377
00:28:26,453 --> 00:28:29,464
because the columns are
orthogonal
378
00:28:29,499 --> 00:28:34,310
can I just check that the columns
of this matrix are orthogonal
379
00:28:36,783 --> 00:28:42,714
so the inner part of that column
with that column is zero
380
00:28:44,287 --> 00:28:50,228
The inner product of column 1
with column three is zero.
381
00:28:51,719 --> 00:28:58,122
How about the inner product
of two and four?
382
00:28:58,963 --> 00:29:03,972
Can I take the inner product of
column two with column four?
383
00:29:04,664 --> 00:29:07,256
Or even the inner product
of two with three.
384
00:29:07,291 --> 00:29:12,004
Let's see...
Let me do two and four
385
00:29:18,859 --> 00:29:23,790
Ok, oh, I see, yes
386
00:29:28,271 --> 00:29:33,098
I believe that those two
columns are orthogonal
387
00:29:33,852 --> 00:29:36,660
so let me take their inner
product and hope to get zero
388
00:29:36,695 --> 00:29:40,848
Ok, now if you hadn't listened
to the first half of the lecture
389
00:29:41,777 --> 00:29:44,083
when you took the inner product
of that with that
390
00:29:44,118 --> 00:29:48,587
you would multiply 1*1
I by -I
391
00:29:48,587 --> 00:29:51,111
and that would have given you 1
392
00:29:52,564 --> 00:29:56,138
-1 by -1 would give you another 1
393
00:29:56,173 --> 00:30:00,754
-I by I would have been -I square
that's another 1
394
00:30:04,162 --> 00:30:07,766
So do I conclude that the inner
product of the columns
395
00:30:07,801 --> 00:30:09,494
I said columns two and four
396
00:30:09,529 --> 00:30:12,492
That's because I forgot those
are columns one and three
397
00:30:15,978 --> 00:30:17,416
I'm interested in their inner products
398
00:30:17,451 --> 00:30:19,919
and I'm hoping it to be zero,
but it doesn't look like a zero
399
00:30:20,734 --> 00:30:25,155
Never will that is a zero, those
columns are perpendicular, why?
400
00:30:25,190 --> 00:30:30,394
Because the inner product,
we conjugate
401
00:30:30,429 --> 00:30:34,865
you remember that the one of the factors
in the inner product test give conjugated
402
00:30:34,900 --> 00:30:38,550
So when I conjugated it, it the
changes that add to the minus I
403
00:30:38,585 --> 00:30:40,150
that changes this to a plus I
404
00:30:40,185 --> 00:30:46,122
Change those second sign and
the fourth sign, and I do get zero
405
00:30:47,827 --> 00:30:53,536
So those columns are orthogonal
so columns are orthogonal
406
00:30:55,208 --> 00:31:01,130
They are not quite orthonormal
but I could fix that easily
407
00:31:01,373 --> 00:31:05,808
They all those columns have lanes 2
408
00:31:06,569 --> 00:31:09,936
lane squared is four, like this
409
00:31:09,971 --> 00:31:15,839
The four I have there, this lane
square plus, one squared...is four
410
00:31:15,874 --> 00:31:17,671
squared root is two
411
00:31:17,706 --> 00:31:22,782
so if I really want them, suppose
I really want to fix like perfectly
412
00:31:22,817 --> 00:31:31,629
I could divide by two, and now I have
columns that are actually orthonormal
413
00:31:37,147 --> 00:31:38,343
So what
414
00:31:39,219 --> 00:31:41,528
so I can invert right away, right?
415
00:31:41,866 --> 00:31:44,359
Orthonormal columns mean...
416
00:31:44,394 --> 00:31:46,954
now I'm keeping this one
half here for the moment
417
00:31:47,665 --> 00:31:53,575
Means F4 Hermitian, can I use
that conjugated transpose?
418
00:31:53,575 --> 00:31:56,489
Times F4 is i
419
00:32:00,216 --> 00:32:01,951
So I see what the inverse is
420
00:32:02,693 --> 00:32:04,954
The inverse of F4 is...
421
00:32:04,989 --> 00:32:07,289
it's just like an orthogonal matrix
422
00:32:07,324 --> 00:32:08,908
the inverse is the transpose
423
00:32:08,943 --> 00:32:11,798
Here the inverse is the
conjugate transpose.
424
00:32:12,441 --> 00:32:19,954
So fine, that tells me that anything's
good that I learn about F4
425
00:32:22,603 --> 00:32:23,671
I'll know the same
426
00:32:23,706 --> 00:32:25,808
I'll know the similar fact about
its inverse
427
00:32:25,843 --> 00:32:29,210
because its inverse is just its
conjugate transpose
428
00:32:29,245 --> 00:32:31,301
Ok, now, so what's good?
429
00:32:32,221 --> 00:32:34,543
Well, first, the columns
are orthogonal
430
00:32:34,543 --> 00:32:37,724
That's the key fact then
431
00:32:37,759 --> 00:32:40,703
that's the thing that
makes the inverse easy
432
00:32:40,738 --> 00:32:45,666
But what property is that leads
to the fast Fourier transform?
433
00:32:45,701 --> 00:32:50,444
Now I'm going to talk in the last minute
about the fast Fourier transform
434
00:32:52,096 --> 00:32:58,901
What, here's the idea
F6 are 6*6 matrix
435
00:33:00,768 --> 00:33:02,877
there's a neat connection to F3
436
00:33:03,785 --> 00:33:04,963
Half as big
437
00:33:06,127 --> 00:33:09,011
there's a connection of F8 to F4
438
00:33:09,832 --> 00:33:13,166
there's a connection of F64 to F32
439
00:33:14,326 --> 00:33:19,301
So I write down what that connection is
what's the connection of F64 to F32?
440
00:33:19,336 --> 00:33:30,187
So F64 is a 64*64 matrix,
whose w is the 64 root of one.
441
00:33:30,222 --> 00:33:35,554
So it's one-64th of the
way round in F64
442
00:33:36,489 --> 00:33:42,146
And F32 is a 32*32 matrix
remember their different sizes
443
00:33:44,675 --> 00:33:52,537
And the w in that 32*32 matrix is the
32nd root of one, which is twice as far
444
00:33:52,572 --> 00:33:57,983
That, you see that key point
that's how 32 and 64 connected.
445
00:33:58,668 --> 00:34:03,619
In the w, the w64 is
one-64th of the way
446
00:34:03,654 --> 00:34:10,382
so on saying that if I
square the W64
447
00:34:10,417 --> 00:34:18,847
that's what I'm using for the w64
Wn is either the i2π over n
448
00:34:18,882 --> 00:34:26,139
So W64 is one-64th of the way round it
when I square that, what do I get?
449
00:34:26,174 --> 00:34:29,926
W32, right?
450
00:34:30,760 --> 00:34:34,678
If I square that matrix,
I double the angle
451
00:34:35,055 --> 00:34:37,748
if I square this number,
I double the angle
452
00:34:37,783 --> 00:34:43,711
I get the W32
453
00:34:44,606 --> 00:34:47,419
So somehow there's a little hope here
454
00:34:47,454 --> 00:34:54,447
The connect F64 with F32
and here's the connection, Ok
455
00:34:54,482 --> 00:34:59,547
Let me, let me go back, let me
oh, I'll do it here.
456
00:35:02,796 --> 00:35:09,477
Here's the connection, F64
the 64*64 Fourier matrix
457
00:35:10,270 --> 00:35:14,126
It's connected to two copies of F32
458
00:35:14,988 --> 00:35:17,605
let me leave a little space
for the connection
459
00:35:17,640 --> 00:35:19,514
That's a 64*64
460
00:35:21,327 --> 00:35:23,480
here's the matrix of that same size
461
00:35:23,515 --> 00:35:26,596
because it's got two copies of F32
462
00:35:26,631 --> 00:35:28,792
And two zero matrices
463
00:35:29,525 --> 00:35:32,267
Those zero matrices are the keys.
464
00:35:33,196 --> 00:35:39,212
Because when I multiply by this matrix
just as it is, regular multiplication
465
00:35:39,247 --> 00:35:45,453
I would take neat 64, I would have 64
squared little multiplications to do.
466
00:35:45,488 --> 00:35:48,198
But this matrix is half zero.
467
00:35:49,068 --> 00:35:51,262
Well, of course, the two are unequal
468
00:35:51,297 --> 00:35:52,756
I'm going to put an equal sign
469
00:35:52,791 --> 00:35:57,402
but there has to be
some fixed up factors
470
00:35:57,952 --> 00:36:03,156
One there, and one there
to make it true.
471
00:36:04,836 --> 00:36:11,276
The beauty is these fixed-up factors
will be really almost all zeros.
472
00:36:13,047 --> 00:36:15,631
So as soon as we get
this formula right
473
00:36:16,560 --> 00:36:23,454
we've got a great idea for how to
get from the 64th square calculations
474
00:36:23,489 --> 00:36:29,221
So this, originally we have 64th
square calculations from there
475
00:36:30,096 --> 00:36:34,002
But this one will give us...
this will...
476
00:36:34,037 --> 00:36:39,217
we don't need that many
we only need 2 times 32 squared
477
00:36:39,252 --> 00:36:44,995
Because we got that twice
and plus the fixed-up.
478
00:36:46,625 --> 00:36:50,286
So I have to tell you what's
in this fixed-up matrices
479
00:36:52,181 --> 00:36:55,085
The one on the right is actually
a permutation matrix
480
00:36:55,120 --> 00:36:58,644
the very simple, odds and
evens' permutation matrices
481
00:36:58,679 --> 00:37:01,907
the ones show up
482
00:37:02,689 --> 00:37:06,611
I haven't put enough ones
I really need 32 of these guys
483
00:37:06,646 --> 00:37:09,784
Double space, and then...
484
00:37:13,897 --> 00:37:16,419
you see
it's a permutation matrix
485
00:37:16,452 --> 00:37:18,491
What it does...
486
00:37:18,526 --> 00:37:24,919
so I call it P, for permutation matrix
so what that P does?
487
00:37:26,049 --> 00:37:28,244
When I multiply the vector
488
00:37:29,057 --> 00:37:34,684
it takes the odd, the even number
component first, and then the odds
489
00:37:35,475 --> 00:37:42,417
You see this one skipping every time
it's going to pick out X0, X2, X4, X6
490
00:37:42,789 --> 00:37:47,554
And then below that will come
it'll pick out X1, X3, X5
491
00:37:50,110 --> 00:37:56,380
And of course that can be hardware
in the computers be instantaneous
492
00:37:56,648 --> 00:38:01,626
So that's, so far
what have we said?
493
00:38:01,661 --> 00:38:09,174
We're saying that 64*64 Fourier matrix is
really separated to vector into the odds
494
00:38:09,209 --> 00:38:12,022
into the even components
and the odd components.
495
00:38:12,814 --> 00:38:18,610
Then do a 32 size Fourier
transform onto those separately
496
00:38:19,328 --> 00:38:22,141
And then put the pieces together again
497
00:38:22,176 --> 00:38:24,451
so the pieces putting them together
498
00:38:24,486 --> 00:38:29,677
Turns out to be I and
a diagonal matrix and I
499
00:38:29,712 --> 00:38:31,858
and a minus of the same diagonal matrix
500
00:38:34,250 --> 00:38:38,119
So the fixed-up cause is really
the cause multiplying by D
501
00:38:39,049 --> 00:38:41,653
This diagonal matrix,
because it is...
502
00:38:41,653 --> 00:38:47,378
essentially no cause in the I part
or in the permutation part
503
00:38:47,413 --> 00:38:51,378
So really it's the fixed up cause
504
00:38:52,175 --> 00:38:59,862
it's essentially, because D the
diagonal is 32 multiplications
505
00:39:03,622 --> 00:39:05,856
That's, there you're seeing, of course
506
00:39:05,891 --> 00:39:08,616
we didn't check the formula,
or we didn't even say what D is yet
507
00:39:08,651 --> 00:39:13,498
But I will, this diagonal matrix D
is powers of W
508
00:39:13,533 --> 00:39:19,063
1, w, w square
down to W to the 31st
509
00:39:24,478 --> 00:39:27,545
So you see that, when I'm to
do a multiplication by D
510
00:39:27,580 --> 00:39:30,116
I need to do 32 multiplications
511
00:39:30,876 --> 00:39:31,805
There they are
512
00:39:32,754 --> 00:39:39,511
then but the other, the more serious
work is to do the F32 twice on the...
513
00:39:39,546 --> 00:39:46,067
Separately on the even number and odd
number components, so twice 32 squared
514
00:39:46,355 --> 00:39:48,986
So 64 squared is gone now
515
00:39:50,648 --> 00:39:53,587
and that's the new count
516
00:39:55,298 --> 00:39:57,916
Ok, great
But what's next?
517
00:39:59,162 --> 00:40:02,103
So that's, we now have the key idea
518
00:40:03,677 --> 00:40:05,810
we'll have to check the algebra
519
00:40:06,538 --> 00:40:11,962
But it's just checking a lot of sums
that come out correctly.
520
00:40:11,997 --> 00:40:16,025
This is like the right way to see
the fast Fourier transform
521
00:40:16,060 --> 00:40:17,633
one right way to see it
522
00:40:19,979 --> 00:40:22,272
Then you've got to see
what's the next idea
523
00:40:22,307 --> 00:40:28,209
The next idea is to break the
32s down, break those 32s down
524
00:40:28,244 --> 00:40:32,633
So we have this factor
and now we have the F32
525
00:40:32,668 --> 00:40:37,212
but that breaks into some guy here
526
00:40:37,247 --> 00:40:47,975
F16, F16 each of F32 is breaking
into two copies of F16
527
00:40:48,907 --> 00:40:52,026
and then we have the permutation
and then we...
528
00:40:52,962 --> 00:40:57,348
so this was like, this was
the 64 size permutation
529
00:40:57,383 --> 00:40:59,625
and this is a 32 size permutation
530
00:40:59,660 --> 00:41:02,661
Ah, I guess I've got it twice
531
00:41:02,696 --> 00:41:05,749
I'm just using the same
idea recursively
532
00:41:06,247 --> 00:41:07,934
Recursion is the key word
533
00:41:07,969 --> 00:41:12,152
then on each of those F32,
so here's zero, zero
534
00:41:12,187 --> 00:41:15,087
It's just to get F32
535
00:41:18,766 --> 00:41:21,482
this is the odd even permutation
536
00:41:22,258 --> 00:41:27,192
So you see we're, we're,
the combination of those permutations
537
00:41:27,227 --> 00:41:28,649
What's it doing?
538
00:41:29,598 --> 00:41:32,906
This guy separates in the odds,
in the evens and odds
539
00:41:32,907 --> 00:41:38,060
And then this guy separates
the evens into the 1...
540
00:41:39,190 --> 00:41:42,543
the numbers of the multi...
the even evens
541
00:41:42,974 --> 00:41:45,966
Which means 0, 4, 8, 16
542
00:41:45,966 --> 00:41:53,448
and even odds, which means 2, 6, 10, 14
543
00:41:53,448 --> 00:41:57,239
and then odd evens, and odd odds
544
00:41:57,274 --> 00:42:02,524
you see together, these permutations
then break our vectors
545
00:42:02,559 --> 00:42:06,865
down into X even even,
and three other pieces.
546
00:42:07,256 --> 00:42:11,616
Those are the four pieces that
separately get multiplied by F16
547
00:42:12,358 --> 00:42:17,850
Separately fixed up by
these Is and Ds and minus Ds.
548
00:42:21,033 --> 00:42:23,264
So this count is now reduced
549
00:42:24,460 --> 00:42:27,905
This count is now,
what's it reduced to?
550
00:42:28,338 --> 00:42:29,919
So that's going to be gone
551
00:42:31,634 --> 00:42:35,672
Because 32 squared, that's the
change I am making, right?
552
00:42:35,707 --> 00:42:39,323
The 32 squared, so it's this
553
00:42:39,358 --> 00:42:42,424
that's now reduced
so I still have 2 times this
554
00:42:42,459 --> 00:42:44,761
But now what's 32 squared?
555
00:42:45,283 --> 00:42:53,389
It's gone, in favor of
2 16 squares plus 16
556
00:42:54,208 --> 00:43:00,031
That was an original 32 to fix
557
00:43:05,391 --> 00:43:07,385
maybe you see what's happening
558
00:43:07,420 --> 00:43:09,730
even easier than this formula is...
559
00:43:09,765 --> 00:43:12,938
what's, when I do the
recursion more and more times
560
00:43:14,502 --> 00:43:17,952
I guess simpler and simpler factors
in the middle
561
00:43:17,987 --> 00:43:22,107
eventually I will be down to 2 point
or 1 point Fourier transforms.
562
00:43:23,617 --> 00:43:27,353
But I get more and more factors
piling up on their right and left
563
00:43:27,388 --> 00:43:30,108
On the right, I'm just getting
permutation matrices
564
00:43:30,143 --> 00:43:34,411
On the left, I'm getting these guys
these Is and Ds
565
00:43:35,339 --> 00:43:40,316
So that's, there's a 32 there
each one of these is causing 32
566
00:43:41,269 --> 00:43:45,169
Each one of those is causing 32
and how many will there be?
567
00:43:48,230 --> 00:43:53,056
You see the 32 for this original
fixed-up, this D had 32 numbers
568
00:43:53,810 --> 00:43:58,080
32 for this next fixed-up
because this 16 and 16 more
569
00:43:59,802 --> 00:44:05,821
I keep going, so the count in
the middle goes down the zip
570
00:44:05,856 --> 00:44:09,684
But the fixed-up counts
all I'm left with
571
00:44:09,719 --> 00:44:14,432
And how many factors, how many
fixes ups I've got loged in
572
00:44:16,077 --> 00:44:22,855
From 64, one step to 32
one step to 16, one step to 8, 4 2 and 1
573
00:44:22,890 --> 00:44:28,815
Six steps, so I've six fixed-up
six fixed-up factors
574
00:44:28,850 --> 00:44:34,457
Finally, I get a 6 times the 32
575
00:44:36,855 --> 00:44:38,928
that's my final count
576
00:44:38,963 --> 00:44:48,306
Instead of 64 squared, this is log
to the base 2 of the 64 times 64
577
00:44:48,513 --> 00:44:50,886
Actually half of 64
578
00:44:51,199 --> 00:44:56,827
so actually the final count
is n log2n
579
00:44:56,827 --> 00:45:02,703
That's the 32, a half
580
00:45:03,277 --> 00:45:11,443
so can I put a box around that wonderful
extremely important satisfying conclusion
581
00:45:12,506 --> 00:45:18,210
That a fast a transform multiplied
by an n*n matrix
582
00:45:18,245 --> 00:45:21,051
But it does not end
in n squared steps
583
00:45:21,086 --> 00:45:24,224
But in one half n log2n steps
584
00:45:24,954 --> 00:45:28,830
And we just complete by doing a count
585
00:45:28,865 --> 00:45:38,474
that suppose, suppose a typical
case would be 2 to the 10th
586
00:45:41,290 --> 00:45:46,230
Now n squared is bigger
than a million
587
00:45:50,399 --> 00:45:53,355
so it's 1024 times 1024
588
00:45:53,390 --> 00:45:56,881
But what's n, what's one half
589
00:45:56,881 --> 00:46:00,490
What's new count done
the right way?
590
00:46:01,265 --> 00:46:10,237
It's n, the 1024, times one half
and what's the log with them?
591
00:46:10,272 --> 00:46:16,122
It's ten, so times 10 over 2
so it's 5 times
592
00:46:16,157 --> 00:46:23,846
It's 5 times 1024, where this
one was 1024 times 1024
593
00:46:27,014 --> 00:46:30,576
We reduced the calculation
by a factor of 200
594
00:46:30,611 --> 00:46:33,906
just by factoring the
matrices properly
595
00:46:34,748 --> 00:46:39,314
This was the thousand times n
we're now down the 5 times n
596
00:46:40,304 --> 00:46:43,945
So we can do 200 Fourier transforms
597
00:46:44,710 --> 00:46:47,234
Well, before we could do one
598
00:46:47,269 --> 00:46:51,832
And in real scientific calculation for
Fourier transforms are
599
00:46:51,867 --> 00:46:53,159
happening all the time
600
00:46:53,194 --> 00:46:55,590
We are saving the factor of 200
601
00:46:55,625 --> 00:47:00,340
in one of the major steps of
modern scientific computing
602
00:47:01,452 --> 00:47:04,376
So that's the idea
of the fast Fourier transform
603
00:47:04,411 --> 00:47:13,022
you see the whole thing hinge on the
special matrix with orthnormal columns
604
00:47:13,057 --> 00:47:18,254
Ok, that's actually it for
complex numbers
605
00:47:18,953 --> 00:47:28,603
I'm back next time to real numbers
eigenvalues and eigenvectors
606
00:47:28,638 --> 00:47:34,229
and the key idea of positive definite
matrices is going to show up
607
00:47:34,641 --> 00:47:36,929
what's the positive definite matrix
608
00:47:36,964 --> 00:47:38,618
and it's the terrific of this course
609
00:47:38,653 --> 00:47:41,408
it's going to reach
positive definiteness
610
00:47:41,443 --> 00:47:45,790
because those are the matrices that
you see the most in the applications
611
00:47:46,518 --> 00:47:48,865
ok, see you next time, thanks.
Last Modified 4/5/08 12:54 AM
|
