-
Notifications
You must be signed in to change notification settings - Fork 0
/
fourier.html
687 lines (626 loc) · 26.3 KB
/
fourier.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
<!DOCTYPE html>
<html lang="en">
<head>
<!-- 2019-10-21 一 15:06 -->
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>MoreLinear \\ Fourier</title>
<meta name="generator" content="Org mode">
<meta name="author" content="George Kontsevich">
<meta name="description" content="linear algebra methods in Clojure"
>
<link rel="stylesheet" type="text/css" href="../web/worg.css" />
<link rel="shortcut icon" href="../web/panda.svg" type="image/x-icon">
</head>
<body>
<div id="org-div-home-and-up">
<a accesskey="h" href="./index.html"> UP </a>
|
<a accesskey="H" href=".."> HOME </a>
</div><div id="content">
<h1 class="title">MoreLinear \\ Fourier</h1>
<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#orgd779ea3">Goal</a></li>
<li><a href="#org2fa013f">Complex numbers</a></li>
<li><a href="#org5263d29">Complex Conjugates</a></li>
<li><a href="#orga82574e">The Unit Circle</a></li>
<li><a href="#org0547d9d">Euler's Formula</a></li>
<li><a href="#org291313c">The roots of unity</a></li>
<li><a href="#orgfb0daba">Fourier series</a></li>
<li><a href="#org0bf804d">Fourier Vectors</a></li>
<li><a href="#org70d3188">Fourier Matrix</a></li>
<li><a href="#org6f6fd8a">Frequency Space?</a>
<ul>
<li><a href="#org3c8cfb6">How does a sinusoidal look in this basis?</a></li>
<li><a href="#orgf8efeb3">How does a phase shift look in this basis?</a></li>
<li><a href="#orgaa487e5">How does a frequency who's period isn't a whole fraction of the sample rate come out in this basis?</a></li>
</ul>
</li>
</ul>
</div>
</div>
<div id="outline-container-orgd779ea3" class="outline-2">
<h2 id="orgd779ea3">Goal</h2>
<div class="outline-text-2" id="text-orgd779ea3">
<p>
Using the multiplicative properties of complex numbers we construct an easily-invertible orthogonal basis in which periodic components of our input become apparant. This basis allows us to carry out a class of operations that are numerically intensive in the standard basis but much quicker in the frequency-basis.
</p>
</div>
</div>
<div id="outline-container-org2fa013f" class="outline-2">
<h2 id="org2fa013f">Complex numbers</h2>
<div class="outline-text-2" id="text-org2fa013f">
<p>
Complex numbers are of the form <b>a+ib</b> where <b>i= √(-1)</b> and <b>a</b> and <b>b</b> are known as the real and imaginary components of the complex number. The pair (a,b) are often referred to as a point on the complex plane. However the implicit analogy to 2D coordinates is a bit probematic
</p>
<p>
To envision a complex plane we treat the <i>real</i> component <b>a</b> acting as the <i>x</i> and the <i>imaginary</i> component <b>b</b> acting as the <i>y</i>.
Like 2D coordinates, we can add/translate them and they can be scaled
</p>
<ul class="org-ul">
<li>(a+ib) + (c+id) = (a+c) + i(bd)</li>
<li>c * (a+ib) = ca +icb</li>
</ul>
<p>
However unlike 2D [x,y] coordinates, complex numbers can be multiplied:
</p>
<ul class="org-ul">
<li>(a+ib) * (c+id) = (ac-bd) + i(ad+bc)</li>
</ul>
<p>
Normally if we are given 2 coordinates [x<sub>0</sub>,y<sub>0</sub>] and [x<sub>1</sub>,y<sub>1</sub>] we never ask ourselves to multiple them because multiplication between two points is simply no a defined operation. However in the complex-number case this operation comes naturally and it generates a new complex number
</p>
<blockquote>
<p>
Note: You can do a dot and cross product between two [x,y] coordinates but:
</p>
<ul class="org-ul">
<li>[x<sub>0</sub>,y<sub>0</sub>] • [x<sub>1</sub>,y<sub>1</sub>] → <i>scalar</i></li>
<li>[x<sub>0</sub>,y<sub>0</sub>] × [x<sub>1</sub>,y<sub>1</sub>] → <i>requires an extra <code>z</code> dimension</i></li>
</ul>
</blockquote>
<p>
So points in the complex plane have this extra "feature" so it's important to not stretch the 2D coordinate interpretation too far. As far as I can tell there is no easy way to visualize what the result of a multiplication looks like in the general case.
</p>
</div>
</div>
<div id="outline-container-org5263d29" class="outline-2">
<h2 id="org5263d29">Complex Conjugates</h2>
<div class="outline-text-2" id="text-org5263d29">
<p>
Just like points and vectors, complex numbers have a "length" or magnitude
</p>
<ul class="org-ul">
<li>||a+ib|| = √(a<sup>2</sup>+b<sup>2</sup>}</li>
</ul>
<p>
And just like for points and vectors, this norm is a real scalar value
</p>
<p>
The square of the norm is ofcourse just <i>a<sup>2</sup>+b<sup>2</sup></i> and this often comes up in things like the inner product. For instance given a vector [x y] we can take its inner product with itself [x y][x y]<sup>T</sup> to get its norm-squared. In the trivial <code>1x1</code> case this will be [z][z]<sup>T</sup> which is z<sup>2</sup>.
</p>
<p>
In the complex case where <i>z</i> is a complex number <i>a+ib</i> then we'd get <i>z*z<sup>T</sup>=z<sup>2</sup>=(a+ib)<sup>2</sup>=a<sup>2</sup>+i2ab-b<sup>2</sup></i> which is non-real and doesn't match our magnitude-squared. So using the transpose no longer works. But this norm-squared is still easy to express as a product
</p>
<ul class="org-ul">
<li>a<sup>2</sup>+b<sup>2</sup> = (a+ib)(a-ib)</li>
</ul>
<p>
With <i>a-ib</i> known as the <i>complex conjugate</i> of <i>a+ib</i>
</p>
<p>
And what's convenient is that this actually still works for real values. Since a real value <i>a</i> can be written as the complex number a+i*0 we can write its complex conjugate as a-i*0 and see that it's norm is
</p>
<ul class="org-ul">
<li>a<sup>2</sup>+0<sup>2</sup> = (a+i0)(a-i0) = a<sup>2</sup></li>
</ul>
<p>
Which is just the absolute value of <i>a</i> squared
</p>
<p>
So instead of doing a transpose we need to introduce a new transposition called the Hermitian transpose
</p>
<ul class="org-ul">
<li>[a+ib c+id]<sup>*</sup> = [a-ib c-d]<sup>T</sup></li>
</ul>
<p>
The Hermitian transpose is denoted with a star. It simply take a normal transpose and replaces the terms with their complex conjugates.
</p>
<p>
When the vector values are all real it will behave exactly like a transpose and when the values are complex, it will take their conjugates and give us scalar/real values of each complex values' magnitude
</p>
</div>
</div>
<div id="outline-container-orga82574e" class="outline-2">
<h2 id="orga82574e">The Unit Circle</h2>
<div class="outline-text-2" id="text-orga82574e">
<p>
Notice that when the <i>norm-squared</i> is equal to <i>1</i> the magnitude is also equal to <i>1</i>. All these special points who's length is equal to <i>1</i> lie on what's called the <i>unit cirle</i>. If we start with two complex numbers <i>a+ib</i> and <i>c+id</i> then
</p>
<ul class="org-ul">
<li>(a<sup>2</sup>+b<sup>2</sup>)<sup>1/2</sup> = 1 <i>and therefore</i> a<sup>2</sup>+b<sup>2</sup> = 1</li>
<li>(c<sup>2</sup>+d<sup>2</sup>)<sup>1/2</sup> = 1 <i>and therefore</i> c<sup>2</sup>+d<sup>2</sup> = 1</li>
</ul>
<p>
As we saw, their product is the point <i>(ac-bd) + i(ad+bc)</i> and its length is also equal to 1. Proof:
</p>
<ul class="org-ul">
<li>[ (ac-bd)<sup>2</sup> + (ad+bc)<sup>2</sup> ]<sup>(1/2)</sup></li>
<li>[ a<sup>2</sup>c<sup>2</sup>-2acbd+b<sup>2</sup>d<sup>2</sup>+a<sup>2</sup>d<sup>2</sup>+2adbc+b<sup>2</sup>c<sup>2</sup> ]<sup>1/2</sup></li>
<li>[ a<sup>2</sup>c<sup>2</sup>+b<sup>2</sup>b<sup>2</sup>+a<sup>2</sup>d<sup>d</sup>+b<sup>2</sup>c<sup>2</sup> ]<sup>1/2</sup></li>
<li>[ c<sup>2</sup>(a<sup>2</sup>+b<sup>2</sup>) + d<sup>2</sup>(a<sup>2</sup>+b<sup>2</sup>) ]<sup>(1/2)</sup></li>
</ul>
<p>
Through some subsitution we see that the length of the product is also equal to <i>1</i>
</p>
<p>
This tells us that while the general complex product is hard to think about, we know that least the product of any two points on the unit circle gives us a new point on the unit circle
</p>
</div>
</div>
<div id="outline-container-org0547d9d" class="outline-2">
<h2 id="org0547d9d">Euler's Formula</h2>
<div class="outline-text-2" id="text-org0547d9d">
<p>
To make the multiplicative rotations more natural we would like to start describing the points in terms of polar coordinates. The initial conversion is straightforward:
</p>
<ul class="org-ul">
<li>radius = r = (a<sup>2</sup>+b<sup>2</sup>)<sup>1/2</sup></li>
<li>angle = θ = atan(b/a)</li>
</ul>
<p>
Going back is also easy
</p>
<ul class="org-ul">
<li>a = rcos(θ)</li>
<li>b = rsin(θ)</li>
</ul>
<p>
So the complex number <i>z=a+ib</i> can now be defined in terms of <i>r</i> and <i>theta</i>:
</p>
<ul class="org-ul">
<li>z = rcos(θ) + irsin(θ)</li>
</ul>
<p>
A more compact representation of this is given by <b>Euler's formula</b>:
</p>
<ul class="org-ul">
<li>re<sup>iθ</sup>=rcos(θ)+irsin(θ)</li>
</ul>
<p>
A complete proof of this identity is a bit long, but the steps are:
</p>
<ul class="org-ul">
<li>Show that the derivative of e<sup>x</sup> is e<sup>x</sup> (it's the only equation of the form a<sup>x</sup> that have this "stable" property)</li>
<li>Using the chain rule we see that the <i>n<sup>th</sup></i> derivative of e<sup>ix</sup> will be equal to i<sup>n</sup>e<sup>ix</sup></li>
<li>i<sup>n</sup> is a cyclic function with half it's terms imaginary and half real</li>
<li>We then describe e<sup>iθ</sup> around <i>0</i> in terms of the Taylor/Maclaurin Series</li>
<li>Half the terms of the Taylor/Maclaurin Series will be imaginary and half real.</li>
<li>The real terms will match the Maclaurin Series of a cosine function and the imaginary will match those of the sine function</li>
</ul>
<p>
Using the trigonometric properties (which are self evident if you think of the graph and even/odd functions)
</p>
<ul class="org-ul">
<li>sin(-θ)=-sin(θ)</li>
<li>cos(-θ)= cos(θ)</li>
</ul>
<p>
We can rewrite the complex conjugate as
</p>
<ul class="org-ul">
<li>a - ib</li>
<li>r cos(θ) - <i>i</i> r sin(θ)</li>
<li>r cos(-θ) + <i>i</i> r sin{-θ) = <b>re<sup>-θ</sup></b></li>
</ul>
<p>
As we just saw in the previous section, the radius in the products of points on the unit cirle is always equal to one. so a polar coordinate system will bring the problem down from 2 variables, <i>a</i> and <i>b</i>, to just one constant <i>radius</i> of size <i>1</i> and one variable <i>angle</i> θ. The points on the unit circle can all be written down as:
</p>
<ul class="org-ul">
<li>e<sup>iθ</sup></li>
</ul>
<p>
And we can say the magnitude of the product of two of these is always equal to <i>1</i>
</p>
<ul class="org-ul">
<li>|| e<sup><i>i</i>θ</sup> * e<sup><i>i</i>ω</sup> || = 1</li>
</ul>
<p>
Now notice that if <i>ω=2π-θ</i> that:
</p>
<ul class="org-ul">
<li>e<sup> <i>i</i> (θ+ω)</sup> = e<sup> <i>i</i> 2π</sup> = cos(2π) + <i>i</i> sin(2π) = 1 + <i>i</i> 0 = 1</li>
</ul>
</div>
</div>
<div id="outline-container-org291313c" class="outline-2">
<h2 id="org291313c">The roots of unity</h2>
<div class="outline-text-2" id="text-org291313c">
<p>
Furthermore if <i>α=2π/n</i> then:
</p>
<ul class="org-ul">
<li>[e<sup>iα</sup>]<sup>n</sup> = e<sup>inα</sup> = e<sup>i2π</sup> = 1</li>
</ul>
<p>
This tells us that taking the n<sup>th</sup> root of <i>1</i> has a complex numbers solution! (in addition to the trivial solution of <i>1</i>)
</p>
<ul class="org-ul">
<li>1<sup>1/n</sup> = e<sup>i2π/n</sup></li>
</ul>
<p>
The typical notation here is to say
</p>
<ul class="org-ul">
<li>ξ = e<sup>-i2π/n</sup> = cos(2π/n)+isin(2π/n)</li>
<li>ξ<sup>n</sup>=1</li>
</ul>
<p>
This ξ is called the <b>n<sup>th</sup> root of unity</b>
By extension we can also see that:
</p>
<ul class="org-ul">
<li>ξ<sup>n+j</sup> = ξ<sup>n</sup>ξ<sup>j</sup> = ξ<sup>j</sup></li>
<li>ξ<sup>nk</sup> = [ξ<sup>n</sup>]<sup>k</sup> = [e<sup>-i2π</sup>]<sup>k</sup> = 1<sup>k</sup> = 1</li>
</ul>
</div>
</div>
<div id="outline-container-orgfb0daba" class="outline-2">
<h2 id="orgfb0daba">Fourier series</h2>
<div class="outline-text-2" id="text-orgfb0daba">
<p>
The Fourier series is a very special sum of the exponents of an n<sup>th</sup> root of unity <b>ξ</b>
</p>
<ul class="org-ul">
<li>1 + ξ<sup>k</sup> + ξ<sup>2k</sup> + … + ξ<sup>(n-2)k</sup> + ξ<sup>(n-1)k</sup></li>
</ul>
<p>
Here the <i>k</i> can be any integer value, but the sum will always maintain the property that if it's multiplied by <i>ξ<sup>k</sup></i> we get the same sequence back. The last term goes to <i>ξ<sup>nk</sup> = 1</i> and the remaining terms in effect shift places giving us:
</p>
<ul class="org-ul">
<li>ξ<sup>k</sup> + ξ<sup>2k</sup> + ξ<sup>3k</sup> + … + ξ<sup>(n-1)k</sup> + 1</li>
</ul>
<p>
So we can write
</p>
<ul class="org-ul">
<li>ξ<sup>k</sup> * <i>fourier-series</i> = <i>fourier-series</i></li>
</ul>
<p>
Therefore
</p>
<ul class="org-ul">
<li>ξ<sup>k</sup> * <i>fourier-series</i> - <i>fourier-series</i> = 0</li>
<li><i>fourier-series</i> * (ξ<sup>k</sup> - 1) = 0</li>
</ul>
<p>
And therefore..
</p>
<ul class="org-ul">
<li><i>fourier-series</i> = 0</li>
</ul>
<p>
.. or to write it out again in full form - for all integer values of <i>k</i>
</p>
<ul class="org-ul">
<li>1+ξ<sup>k</sup>+ξ<sup>2k</sup>+…+ξ<sup>(n-2)k</sup>+ξ<sup>(n-1)k</sup> = 0</li>
</ul>
</div>
</div>
<div id="outline-container-org0bf804d" class="outline-2">
<h2 id="org0bf804d">Fourier Vectors</h2>
<div class="outline-text-2" id="text-org0bf804d">
<p>
It turns out that Fourier series, when places in a vector with different values of <i>k</i>, form mutually orthogonal vectors - here I choose <i>r</i> and <i>s</i> for <i>k</i> and carry out the Hermitian inner product:
</p>
<ul class="org-ul">
<li>[ 1 ξ<sup>r</sup> ξ<sup>2r</sup> … ξ<sup>(n-1)r</sup> ] [ 1 ξ<sup>s</sup> ξ<sup>2s</sup> … ξ<sup>(n-1)s</sup> ]<sup>*</sup></li>
<li>[ 1 ξ<sup>r</sup> ξ<sup>2r</sup> … ξ<sup>(n-1)r</sup> ] [ 1 ξ<sup>-s</sup> ξ<sup>-2s</sup> … ξ<sup>-(n-1)s</sup> ]<sup>T</sup></li>
<li>1*1 + ξ<sup>r</sup>*ξ<sup>-s</sup> + ξ<sup>2r</sup>*ξ<sup>-2s</sup> + … + ξ<sup>(n-2)r</sup>ξ<sup>-(n-2)s</sup>} + ξ<sup>(n-1)r</sup>ξ<sup>-(n-1)s</sup></li>
<li>1 + ξ<sup>r-s</sup> + ξ<sup>2(r-s)</sup> + … + ξ<sup>(n-2)(r-s)</sup> + ξ<sup>(n-1)(r-s)</sup></li>
</ul>
<p>
Now <i>r-s</i> is just another <i>k</i> value from our Fourier series and so the sum will go to <i>0</i> <b>except</b> when <i>r=s</i>:
</p>
<ul class="org-ul">
<li>[ 1 ξ<sup>k</sup> ξ<sup>2k</sup> … ξ<sup>(n-1)k</sup> ] [ 1 ξ<sup>k</sup> ξ<sup>2k</sup> … ξ<sup>(n-1)k</sup> ]<sup>*</sup></li>
<li>1*1 + ξ<sup>k</sup>ξ<sup>-k</sup> + ξ<sup>2k</sup>ξ<sup>-2k</sup> + … + ξ<sup>(n-1)k</sup> ξ<sup>-(n-1)k</sup></li>
<li>1*1 + ξ<sup>0</sup> + ξ<sup>0</sup> + … + ξ<sup>0</sup></li>
<li>1 + 1 + 1 + … + 1 = n</li>
</ul>
<p>
You could also just view the <i>r=s</i> case as the sum of the 2-norms of the roots of unity. There are <i>n</i> terms and each one is necessarily of length <i>1</i>. Either way, the answer will always be <i>n</i> no matter what <i>k</i> you choose
and therefore the 2-norm/length all all fourier vectors is <i>n<sup>1/2</sup></i>
</p>
<p>
It's important to note that if you drop all the complex terms none of this works! You can't construct mutually orthogonal vectors out of purely real sine/cosine waves
</p>
</div>
</div>
<div id="outline-container-org70d3188" class="outline-2">
<h2 id="org70d3188">Fourier Matrix</h2>
<div class="outline-text-2" id="text-org70d3188">
<p>
We've just shown that the fourier vectors are orthogonal as long as the <i>k</i>'s are different. The only caveat is that when <i>k=n</i> then the result is identical to <i>k=0</i> and when <i>k=n+1</i> it's identical to <i>k=1</i> .. etc. So there are actually only <i>n</i> distinct fourier vectors. The next step is self evident. We just choose take the <i>n</i> distinct vectors and slap them together into a fourier matrix <b>F</b> and end up withh an orthogonal basis:<br>
<b>F</b> =
</p>
<table>
<colgroup>
<col class="org-right">
<col class="org-left">
<col class="org-left">
<col class="org-left">
<col class="org-left">
</colgroup>
<tbody>
<tr>
<td class="org-right">1</td>
<td class="org-left">1</td>
<td class="org-left">1</td>
<td class="org-left">1</td>
<td class="org-left">..</td>
</tr>
<tr>
<td class="org-right">1</td>
<td class="org-left">ξ</td>
<td class="org-left">ξ<sup>2</sup></td>
<td class="org-left">ξ<sup>3</sup></td>
<td class="org-left">..</td>
</tr>
<tr>
<td class="org-right">1</td>
<td class="org-left">ξ<sup>2</sup></td>
<td class="org-left">ξ<sup>4</sup></td>
<td class="org-left">ξ<sup>6</sup></td>
<td class="org-left">..</td>
</tr>
<tr>
<td class="org-right">1</td>
<td class="org-left">ξ<sup>3</sup></td>
<td class="org-left">ξ<sup>6</sup></td>
<td class="org-left">ξ<sup>9</sup></td>
<td class="org-left">..</td>
</tr>
<tr>
<td class="org-right">1</td>
<td class="org-left">…</td>
<td class="org-left">…</td>
<td class="org-left">…</td>
<td class="org-left">..</td>
</tr>
<tr>
<td class="org-right">1</td>
<td class="org-left">ξ<sup>n-1</sup></td>
<td class="org-left">ξ<sup>n-2</sup></td>
<td class="org-left">…</td>
<td class="org-left">..</td>
</tr>
</tbody>
</table>
<p>
Looking at the real components of the columns - there is one constant component (the first column) and then <i>n</i> samples of the <i>cosine</i> function over one oscillation for the second column, <i>n</i> samples over 2 periods for the 3rd column, <i>n</i> samples over 3 periods.. etc. <br>
ℜ(<b>F</b>) =
</p>
<table>
<colgroup>
<col class="org-right">
<col class="org-left">
<col class="org-left">
<col class="org-left">
<col class="org-left">
</colgroup>
<tbody>
<tr>
<td class="org-right">1</td>
<td class="org-left">1</td>
<td class="org-left">1</td>
<td class="org-left">1</td>
<td class="org-left">..</td>
</tr>
<tr>
<td class="org-right">1</td>
<td class="org-left">cos(1*2π/n)</td>
<td class="org-left">cos(2*2π/n)</td>
<td class="org-left">cos(3*2π/n\)</td>
<td class="org-left">..</td>
</tr>
<tr>
<td class="org-right">1</td>
<td class="org-left">cos(2*2π/n)</td>
<td class="org-left">cos(4*2π/n)</td>
<td class="org-left">cos(6*2π/n)</td>
<td class="org-left">..</td>
</tr>
<tr>
<td class="org-right">1</td>
<td class="org-left">cos(3*2π/n)</td>
<td class="org-left">cos(6*2π/n)</td>
<td class="org-left">cos(9*2π/n)</td>
<td class="org-left">..</td>
</tr>
<tr>
<td class="org-right">1</td>
<td class="org-left">…</td>
<td class="org-left">…</td>
<td class="org-left">…</td>
<td class="org-left">..</td>
</tr>
<tr>
<td class="org-right">1</td>
<td class="org-left">cos([n-1]*2π/n)</td>
<td class="org-left">cos(2[n-1]2π/n)</td>
<td class="org-left">cos(3[n-1]*2π/n)</td>
<td class="org-left">..</td>
</tr>
</tbody>
</table>
<p>
If your input is over 1 second then this maps to a sampled cosine function of 1Hz, 2Hz, 3Hz, etc..<br>
<b>TODO</b>: Add a proof that these don't form an orthogonal basis
</p>
<p>
Since each series (irrespective of the <i>k</i> exponent) has length <i>n<sup>1/2</sup></i> (remember that the self-inner norms equal <i>n</i>), all the columns of <b>F</b> can be normalized in one go by dividing the matrix by <i>n<sup>1/2</sup></i>. The resulting matrix <b>(1/n<sup>1/2</sup>)F</b> is now even better b/c it's orthonormal/unitary. Therefore its inverse is just its Hermitian transpose.
</p>
<ul class="org-ul">
<li>[(1/n<sup>1/2</sup>)F]<sup>-1</sup> = [(1/n<sup>1/2</sup>)F]<sup>*</sup></li>
<li>F<sup>-1</sup> = (1/n)F<sup>*</sup></li>
</ul>
<p>
In <b>F<sup>-1</sup>F</b> the diagonal elements will be the column magnitudes, which have been normalized to <i>1</i>, and the off diagonal elements will be inner products of orthogonal vectors and therefore <i>0</i> - so the product will give us the identity matrix <b>I</b>
</p>
</div>
</div>
<div id="outline-container-org6f6fd8a" class="outline-2">
<h2 id="org6f6fd8a">Frequency Space?</h2>
<div class="outline-text-2" id="text-org6f6fd8a">
<p>
We constructed a very convenient basis that's easily invertible and independent of the input and we can now easily move to the basis and back but it's not exactly what one would imagine as "frequency space" and a few things are unresolved
</p>
</div>
<div id="outline-container-org3c8cfb6" class="outline-3">
<h3 id="org3c8cfb6">How does a sinusoidal look in this basis?</h3>
<div class="outline-text-3" id="text-org3c8cfb6">
<p>
Since each column is a mixture of real and imaginary samples of sine/cosine functions we at first glance don't have a straight correspondance between frequencies and the column number.<br>
Reusing the trigonometric identities:
</p>
<ul class="org-ul">
<li>sin(-θ) = -sin(θ)</li>
<li>cos(-θ) = cos(θ)</li>
</ul>
<p>
We can carefully pair Euler functions to get back bare sine/cosine functions with no imaginary parts
</p>
<ul class="org-ul">
<li>[e<sup>iθ</sup> + e<sup>-iθ</sup>]/2 = [cos(θ) + isin(θ) + cos(-θ) + isin(-θ)]/2 = <b>cos(θ)</b></li>
<li>[e<sup>iθ</sup> - e<sup>-iθ</sup>]/2i = [cos(θ) + isin(θ) - cos(-θ) - isin(-θ)]/2i = <b>sin(θ)</b></li>
</ul>
<p>
If we put in <i>-2πφ/n</i> for <i>θ</i> we back our familiar roots of unity:
</p>
<ul class="org-ul">
<li>[ξ<sup>-φ</sup> + ξ<sup>φ</sup>]/2 = cos(2πφ/n)</li>
<li>n*[ξ<sup>-φ</sup> + ξ<sup>φ</sup>]/2 = cos(2πφ)</li>
<li>[ξ<sup>-φ</sup> - ξ<sup>φ</sup>]/2i = sin(2πφ/n)</li>
<li>n*[ξ<sup>-φ</sup> - ξ<sup>φ</sup>]/2i = sin(2πφ)</li>
</ul>
<blockquote>
<p>
<b>Note</b>: b/c these are cyclical functions:
</p>
<ul class="org-ul">
<li>sin(-θ) = sin(2π - θ)</li>
<li>cos(-θ) = cos(2π - θ)</li>
<li>e<sup>-iθ</sup> = e<sup>i(2π-θ)</sup></li>
<li>ξ<sup>-k</sup> = ξ<sup>n-k</sup></li>
</ul>
</blockquote>
<p>
With some rearranging we can rewrite these as:
</p>
<ul class="org-ul">
<li>cos(2πφ) = n*[ξ<sup>n-φ</sup> + ξ<sup>φ</sup>]/2</li>
<li>sin(2πφ) = n*[ξ<sup>n-φ</sup> - ξ<sup>φ</sup>]/2i</li>
</ul>
<p>
and if <i>φ</i> is equal to a <i>k</i> value, then this will be equal to basis vectors in our fourier matrix.
</p>
<p>
For instance if <i>φ</i> = 3 we can pick an <i>x</i>
</p>
<ul class="org-ul">
<li>x = [ 0 0 n/2 0 0 .. 0 0 n/2 0 0]<sub>1,n</sub></li>
</ul>
<p>
So that:
</p>
<ul class="org-ul">
<li>cos(2π * 3) = F<sup>*</sup>x<sup>T</sup></li>
</ul>
<p>
Similarly with the sine function, except with an extra minus sign:
</p>
<ul class="org-ul">
<li>y = [ 0 0 -n/2i 0 0 .. 0 0 n/2i 0 0]<sub>1,n</sub></li>
</ul>
<p>
So that:
</p>
<ul class="org-ul">
<li>sin(2π * 3) = F<sup>*</sup>y<sup>T</sup></li>
</ul>
<p>
Both of these matrix-vector products are always producing real values and complex coordinate value has a real and imaginary part, so it stands for both a have a sine and a cosine of it's corresponding basis vector frequency.
</p>
<p>
Furthermore there is a consistent symmetry between the n<sup>th</sup> and (n-φ)<sup>th</sup> coordinate. This symmetry in both real and imaginary terms the first n/2 terms tell us everything about the oscillating components of our input. You can completely disregard the second n/2 terms.
</p>
<blockquote>
<p>
<b>Note</b> This doesn't represent a loss of information. The input had <b>n</b> real values the output has <b>n/2</b> complex coordinates (each made of 2 values).<br>
<b>Note</b> If the input is complex then this symmertry won't hold. But in most applications a complex input is not meaningful
</p>
</blockquote>
</div>
</div>
<div id="outline-container-orgf8efeb3" class="outline-3">
<h3 id="orgf8efeb3">How does a phase shift look in this basis?</h3>
<div class="outline-text-3" id="text-orgf8efeb3">
<p>
Notice how each the real part of the coordinate is making <i>cosine</i> waves and the <i>imaginary</i> is making sine waves. Both are present in the final complex coordinate value and an arbitrary coordinate value will generate one of both.
</p>
<ul class="org-ul">
<li>v = ℜ(v) + ℑ(v)</li>
<li>vF<sup>*</sup> = ℜ(v)F<sup>*</sup> + ℑ(v)F<sup>*</sup> = α sin(…) + β cos(…)</li>
</ul>
<p>
Sinusoidals have an amazing property, that if you add sinusoidals that have the same frequency but different amplitudes and/or phase you always get back just one sinusoidal of that frequency.
</p>
<p>
In our case we are simply adding a <i>sine</i> and <i>cosine</i> and this additive property as the consequency of the trig identity:
</p>
<ul class="org-ul">
<li>sin(A+B) = sin(A)cos(B)+cos(A)sin(B)</li>
</ul>
<p>
Now given any <i>sine</i> wave with a phase shift we can decompose it into the sum of a <i>sine</i> and <i>cosine</i>
</p>
<ul class="org-ul">
<li>Asin(ω t + φ)</li>
<li>= Asin(φ)cos(ωt)+Acos(φ)sin(ω t)</li>
<li>= A<sub>1</sub>cos(ω t) + A<sub>2</sub>sin(ω t) <i>.. bc φ is a constant</i></li>
</ul>
<p>
Working back we get the general rules for <b>harmonic addition</b>
</p>
<ul class="org-ul">
<li>α sin(ωt) + β cos(ωt) = γ sin(ωt+θ)</li>
<li>γ = √[α<sup>2</sup>+β<sup>2</sup>]</li>
<li>θ = atan(β/α)</li>
</ul>
<p>
So these sine/cosine functions of the same frequency in conjuction represent a phase shifted sine function.
</p>
<p>
It also means that if your phase shifts (say your input is delayed) then the real and imaginary coordiante components will fluctuate, but the norm/length will remain constant b/c √[α<sup>2</sup>+β<sup>2</sup>] will always be equal to the sine wave's amplitude γ.
</p>
<p>
If you take the norm of <b>Fx</b> (or more simply just do <b>Fx(Fx)^{</b>}*) you will get the amplitude at each frequency component (at the expense of loosing all phase information) and you can then draw a spectrogram
</p>
</div>
</div>
<div id="outline-container-orgaa487e5" class="outline-3">
<h3 id="orgaa487e5">How does a frequency who's period isn't a whole fraction of the sample rate come out in this basis?</h3>
<div class="outline-text-3" id="text-orgaa487e5">
<p>
All the previous math had assumed for simplicity that the input was at a frequency that matches one of the basis vectors - that it in effect produced one coordinate point. But how about if <i>φ</i> is not equal to a <i>k</i> value?
</p>
</div>
</div>
</div>
</div>
</body>
</html>