The Discrete Fourier Transform: Most Important Algorithm Ever?

  Рет қаралды 103,875

Reducible

Reducible

Күн бұрын

Go to nordvpn.com/reducible to get the two year plan with an exclusive deal PLUS 1 bonus month free! It’s risk free with NordVPN’s 30 day money back guarantee!
The Discrete Fourier Transform (DFT) is one of the most essential algorithms that power modern society. In this video, we go through a discovery-oriented approach to deriving the core ideas of the DFT.
We start by defining ideal conditions and properties of our transform. We define a similarity measure and come up with an idea that the transform we are looking for is fundamentally a matrix multiplication. Within the context of simple cosine waves, we develop an initial version of our transform using cosine wave analysis frequencies that seems to fit the parameters of what we are looking for. But we discover some key issues with that transform involving the phase of the signal.
To solve the phase problem, we take a look a sine wave analysis frequencies and observe how using a combination of sine and cosine wave analysis frequencies perfectly solves the phase problem. The final step involves representing these sine and cosine wave analysis frequencies as complex exponentials. We finish the video by analyzing some interesting properties of the DFT and their implications.
Chapters:
0:00 Intro
1:50 Sampling Continuous Signals
3:41 Shannon-Nyquist Sampling Theorem
4:36 Frequency Domain Representations
5:38 Defining Ideal Behavior
6:00 Measuring SImilarity
6:57 Analysis Frequencies
8:58 Cosine Wave Analysis Frequency Transform
9:58 A Linear Algebraic Perspective
13:51 Sponsored Segment
15:20 Testing our "Fake Fourier Transform"
18:33 Phase Problems
19:18 Solving the Phase Problem
21:26 Defining the True DFT
28:21 DFT Recap/Outro
Animations created jointly by Nipun Ramakrishnan and Jesús Rascón.
References:
Great written guide on the DFT: brianmcfee.net/dstbook-site/c...
Proof of orthonormality of the DFT: math.stackexchange.com/questi...
More on the Shannon Nyquist sampling theorem: brianmcfee.net/dstbook-site/c...
Great intuition on the continuous Fourier Transform: • But what is the Fourie...
This video wouldn't be possible without the open source library manim created by 3blue1brown and maintained by Manim Community.
The Manim Community Developers. (2022). Manim - Mathematical Animation Framework (Version v0.11.0) [Computer software]. www.manim.community/
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Music in this video comes from Jesús Rascón and Aaskash Gandhi
Socials:
Patreon: / reducible
Twitter: / reducible20
Big thanks to the community of Patreons that support this channel. Special thanks to the following Patreons:
Nicolas Berube
kerrytazi
Brian Cloutier
Andreas
Matt Q
Winston Durand
Adam Dřínek
Burt Humburg
Ram Kanhirotentavida
Jorge
Dan
Eugene Tulushev
Mutual Information
Sebastian Gamboa
Zac Landis
Richard Wells
Asha Ramakrishnan

Пікірлер: 185
@Reducible
@Reducible Жыл бұрын
Check out nordvpn.com/reducible to get the two year plan with an exclusive deal PLUS 1 bonus month free! It’s risk free with NordVPN’s 30 day money back guarantee!
@phizc
@phizc Жыл бұрын
PSA: Nord VPN is all well and good the first 2-3 years, but if you don't cancel then and your credit card information is stored, you'll get billed for another year. $99 per year for the standard plan, which is Hella more expensive than original price (I paid $107 for 3 years).
@user-rd6ho9kg4g
@user-rd6ho9kg4g Жыл бұрын
Hey I really love your video and the effort you put into it is truly heroic! I wanted to say thank you and also correct me if Im wrong but on 10:45, in the second "requirement" it should be Fj, not Fk right?
@viacheslavnovakovskyi7703
@viacheslavnovakovskyi7703 Жыл бұрын
How can I contact you? Email
@agatasoda
@agatasoda 9 ай бұрын
I love the way you explain things please do a video on wavelets!
@nikhilpokale
@nikhilpokale Ай бұрын
Why no new videos? Please make more videos
@srijanpaul
@srijanpaul Жыл бұрын
I'd love to see a similar explanation for the Laplace or Z-transform. I've yet to see a bottom up explanation of these transforms from first principles.
@federicomuciaccia9191
@federicomuciaccia9191 Жыл бұрын
agree
@victormagalhaes1204
@victormagalhaes1204 Жыл бұрын
so true, that would be awesome!
@mujomuric446
@mujomuric446 11 ай бұрын
Geil
@alexmarroquin69
@alexmarroquin69 3 ай бұрын
MATLAB actually did release a video about a similar way of deriving the DFT and a another video on how the Z-transform arises from the DFT. The animations are not as good as the ones here but it is very informative and clear.
@AMR-555
@AMR-555 Жыл бұрын
Unbelievable. I spent all day reading about DFT and thought this video popped up because of my search history. Seeing that it was released 5 mins ago blew my mind!
@orterves
@orterves Жыл бұрын
This video is worth more than just a like - both for the subject matter and the enthralling presentation.
@jessewilliams6214
@jessewilliams6214 Жыл бұрын
This is fantastic. While going through my CS curriculum at university I feel like I got a good grasp of what the DFT accomplishes and how it's useful - even used the fft functions in numpy like you showed. I was always so confused about why there were complex numbers in the outputs if that function though, and nobody ever bothered to explain it to me. I think I never really grasped that the potential for signals to be out of phase with each other introduces an ambiguity that needs a solution. The way you walked through that just made it all click for me after years of not fully understanding.
@mikumikuareka
@mikumikuareka Жыл бұрын
This is very well explained. As someone who studied computer science in the university, I must admit, it's a real shame they don't explain this topic as clearly as you do.
@theastuteangler9642
@theastuteangler9642 Жыл бұрын
blah blah blah computer science blah blah blah. i am very smart.
@dl1083
@dl1083 Жыл бұрын
@@theastuteangler9642 Someone's jealous 😂
@theastuteangler9642
@theastuteangler9642 Жыл бұрын
@@dl1083 as someone who is not jealous, I must admit, that I can speak authoritatively on jealousy. I am very smart.
@racefan7616
@racefan7616 Жыл бұрын
@@theastuteangler9642 oh yeah, smart guy? If Bob has 36 candy bars and eats 29 of them, what does he have left?
@theastuteangler9642
@theastuteangler9642 Жыл бұрын
@@racefan7616 as a fat ass, I can confirm that Bob has a stomach ache. I am very smart.
@alonkellner5375
@alonkellner5375 Жыл бұрын
One of the best videos on this channel so far, concise and deliberate, very well done!
@minhazurrahman7520
@minhazurrahman7520 Жыл бұрын
Remarkable video. It’s hard enough to create animations and lectures to clearly explain a topic. You have managed to combined both and presented a clear picture of an algorithm that is quite complex to understand from examining the procedures only. The harmony of precise animation and a trial-error approach to solving the problem has resulted in quite possibly the best video on DFT.
@chenxin1416
@chenxin1416 10 ай бұрын
Wow, this video is pure gold! I've been trying to wrap my head around the Discrete Fourier Transform for many times and this video made it so much clearer. Seriously, thanks a ton for this!
@gregarityNow
@gregarityNow 2 ай бұрын
I have had a mental block on the DFT for nine years, it is now lifted. Thank you oh so much!
@zianwang2897
@zianwang2897 Жыл бұрын
This video is fantastic for me to understand what a dft matrix is in a visual way. understanding from a pespective of using dot product to compare similarity between analyzing frequency signal and target signal is really cool.
@NoNTr1v1aL
@NoNTr1v1aL Жыл бұрын
Absolutely amazing video! My BSc Maths project was about the Shannon-Nyquist theorem.
@bubblesort8760
@bubblesort8760 Жыл бұрын
Finally another amazing video. I love this channel's videos. Keep the good work up. Thanks for your efforts.
@aibasei3254
@aibasei3254 Жыл бұрын
That's practical and theoretical description of FT. Beautifully explained 👏
@parikshithk8289
@parikshithk8289 Жыл бұрын
I look forward to comprehend and grasp more concepts ur explanation is super amazing i really enjoyed learning. visual memory is what makes us easy to remember and uptake execution
@stephenpaek9175
@stephenpaek9175 7 ай бұрын
Great content, wish I had access to this when I was in graduate school. It would have made it so much more enjoyable when learning DSP
@mastershooter64
@mastershooter64 Жыл бұрын
Never stop making videos my man you rock!
@kwan3217
@kwan3217 Жыл бұрын
The transform-as-matrix-multiply makes sense now. I have been considering a transform to figure out the notes of music, and have always wondered if I could do a frequency analyzer that was spaced along the musical scale, rather than evenly in frequency. Your explanation makes that easy -- just put the samples of the frequencies I care about in the rows, and just skip the rest. I can put any frequency I want, not just ones that fit evenly into the time range of the input samples. So for instance if analzying a signal sampled at 100Hz for 1s, I would have 100 evenly spaced time samples, and the normal Fourier transform would do waves from -50Hz to +49Hz. I could instead put in any logarithmically scaled waves I wanted on the rows, like all the powers of the 12th root of 2. It also shows why no one does that -- first, if the matrix isn't square, it isn't invertible, and therefore there is no inverse transform. I have to have as many frequencies as there are samples, or else information is lost. Second, I don't think that the rows would be orthogonal in this case, meaning that a pure tone, even at one of the frequencies I was selecting for, would show a nonzero coefficient in the other frequencies.
@zhipingang8168
@zhipingang8168 Жыл бұрын
Got to love the Computer Modern font that is used in the presentation!
@DudeWhoSaysDeez
@DudeWhoSaysDeez Жыл бұрын
I love these videos about fourier transformations
@correcthorsebatterystaple4831
@correcthorsebatterystaple4831 Жыл бұрын
The sequel we all needed!
@newklear2k
@newklear2k 6 ай бұрын
You just in like 5 minutes made me understand the DFT when two semesters in a sandstone university could not.
@mwerensteijn
@mwerensteijn Жыл бұрын
Best explaination I could have wished for, thank you!
@Renslay
@Renslay Жыл бұрын
It is such a beautiful and elegant explanation!
@mehdimabed4125
@mehdimabed4125 Жыл бұрын
The video is sooo cool !! Congrats ! By the way, I'm wondering, at the beginning, it is specified that the matrix should be invertible, but in fact the only requirement is that it should be left invertible, so does a similar process/algorithm exists with non-square matrix unsing pseudo-inverse? Thanks again for the amaizing content !
@loading685
@loading685 Жыл бұрын
Love this video! (As well as the complex pun 😂😂) Although I'm a year 12 student, I find it simple enough to understand the whole video, while having enough places to stop and think on my own, for example why did the matrix representation 'broke'. Maybe you could try to make a video on CQT as an extension to this video?🤔
@NerdCloud-IT
@NerdCloud-IT 7 ай бұрын
True, this video has explained to me, 9th grader, how to perform a DFT. It's just so simply described.
@netsrac95
@netsrac95 2 ай бұрын
One of the best Videos I have ever seen on zhis kind of topic. Thanks a lot!
@punditgi
@punditgi 8 ай бұрын
Beautiful explanation and video! 🎉😊
@seedmole
@seedmole Жыл бұрын
I've been working on a DIY audio workstation thing in Pure Data lately, and the one piece of black magic it's using so far is a noise cancellation patch from one of the example files. I know enough about that visual programming language to work the mono example into a stereo version, and so I'm using it to clean up the input on a stereo delay/looper. But yeah, I could not build that process from scratch.
@fhools
@fhools 8 ай бұрын
Just a beautiful exposition. *chef's kiss*
@ItsMeTheUser
@ItsMeTheUser 3 ай бұрын
Great work man, we really appreciate it!
@henrynwosu6277
@henrynwosu6277 10 ай бұрын
1:35 into the video, he said " from first principles" 😢😢😢😢😢😢😢. Just wonderful!!!😢😢
@loading685
@loading685 Жыл бұрын
Grandpa, you favourite youtuber uploaded a video!
@z3r0slab96
@z3r0slab96 Жыл бұрын
Im not that old xD
@bmwe46lover65
@bmwe46lover65 Жыл бұрын
It's been so god damm long
@mikip3242
@mikip3242 Жыл бұрын
I don't care if It takes time to make such awesome quality.
@harriehausenman8623
@harriehausenman8623 Жыл бұрын
That's what time travel is for! 🤣
@imnimbusy2885
@imnimbusy2885 9 ай бұрын
“Just eat the damn orange already!”
@quirtt
@quirtt Жыл бұрын
I was literally thinking of coming up with fourier stuff myself just an hour ago. Miracles you love to see
@scotth.hawley1560
@scotth.hawley1560 Жыл бұрын
Oooo! Excellent. Very well done! Will send to my colleagues and students. Liked and Subscribed. Request for next time: STFT, windowing, and the MDCT! ;-)
@huyvuquang2041
@huyvuquang2041 Жыл бұрын
Thank you so much. You make me such a huge favor on explaining these concept intuitively. Keep up your great work!!! +1 subscribe
@sunbear2340
@sunbear2340 11 ай бұрын
Nah yt algo did this guy dirty this video is so good
@ddichny
@ddichny Жыл бұрын
Outstanding presentation.
@Ken-S
@Ken-S Жыл бұрын
It is amazing! I can't believe how we can process these signal in our brain.
@tpb2
@tpb2 2 ай бұрын
Really excellent presentation!
@mdtanvirahmedsagor6146
@mdtanvirahmedsagor6146 11 ай бұрын
This is purely quality content. I don't understand why this doesn't get enough viewers 😅
@m4rc0k1tt3L
@m4rc0k1tt3L Жыл бұрын
Yesterday i was into algorithm geometry and thought about the fourth quadrants in a coordinate system. I thought about the simple forsign relations in each quadrants and how sinus and cosinus acts when your points are located in a quadrant. And i am a big fan of audio processing, watching this videos about discrete points and their inverse relation in time and frequency domain and seeing similar pattern in this, is like Joy, happyness, thankfulness. Iove your Videos, because they are art. The art of describing things simple on the one hand and exact on the other hand without any needs for Interpretation is so valueable. For me it offers the possibility for cross thinking, so how to apply this concept in Quantum mechanic to transfer Newtons physical relations to a wave core while moving in space in relation to an constant observer, so to change Position without moving while moving. And now i see in your Video that it will work about probabilty phase shifting to invent a quantum drive, in a relative position to an constant observer, to reduce the error while moving to constant zero in a linear way. Thanks a lot for this insights. More of that please.
@harriehausenman8623
@harriehausenman8623 Жыл бұрын
You user name sounds like you are also a fan of Ben Krasnow! 😄
@m4rc0k1tt3L
@m4rc0k1tt3L Жыл бұрын
@@harriehausenman8623 😁😁😁😁
@raxneff
@raxneff 6 ай бұрын
Very intuitive! Thanks!
@svilen2006
@svilen2006 Жыл бұрын
Keep up the good work!
@TheJara123
@TheJara123 11 ай бұрын
Damn what a brilliaaaaaant presentation of complex concept to concrete !!!
@chaiyihein
@chaiyihein 3 ай бұрын
this is absolute art
@ribamarsantarosa4465
@ribamarsantarosa4465 4 ай бұрын
Thanks!! Suggestion for video: a meta video explaining how you code the videos on your videos, i find incredibly useful how you get the visual effects synchronized for signals, I believe that you might have programmed it, right???
@MrDestroys
@MrDestroys Жыл бұрын
YES!! THE LEGEND IS BACK!!!
@anwerarif894
@anwerarif894 Жыл бұрын
Thank you Why we use Fourier transform in communication and laplace in control system?? Thanks
@sitrakaforler8696
@sitrakaforler8696 Жыл бұрын
Dude...it's superbe:! Bravo!
@davidhicks8290
@davidhicks8290 Жыл бұрын
Get on Nebula! Love your work
@guillaume6373
@guillaume6373 Жыл бұрын
loved this video!!!
@quasiker1879
@quasiker1879 Жыл бұрын
Great video! It's taken me an hour to get to minute 10:38 ^^ I think there's a small mistake here: Shouldn't there be an arrow above a_j because it's a vector?
@joelflanagan7132
@joelflanagan7132 Жыл бұрын
Great work!
@Ajay-ib1xk
@Ajay-ib1xk 5 ай бұрын
sir Great explaination
@Z3rgatul
@Z3rgatul Жыл бұрын
I still can't imagine how much time you need to draw all these awesome animations. Maybe you consider making simple video about how you make your videos?
@jordanbtucker
@jordanbtucker 9 ай бұрын
I believe they are using manim, the Mathematical Animation Engine created a used by 3Blue1Brown.
@titusfx
@titusfx Жыл бұрын
Hi thanks for ur videos. I've a doubt it would be nice if you can help me out with it 1. When you expose the similarity of two function, your drawns make me realise that ur similarity function is related with the points that have in common. Which I don't think is a good measure. Why not make similarity by the amount of operations requiered? E.g: in one of ur examples you draw the exact function but negative, and the similarity was almost zero. And the only difference was multiplying but -1. I think about this similarity as the algorithm in computer science that is given a word, how many operations I can make to the word to make it a correct word (works for mispelling). Is not a better similarity measurement? 2. I can't stop thinking about: can we considere the set of frequencies to the function that we want to approach as a set of prime numbers that its multiplication con generate a number? Exist there some relation between those domains? Thanks again for your vídeos.
@martinkunev9911
@martinkunev9911 Жыл бұрын
25:00 shouldn't it be unitary (not orthogonal)?
@son_et_lumiere9
@son_et_lumiere9 Жыл бұрын
Is this still made with manim? or are you using new stuff? It looks beyond great, by the way! You've become one of my favorite channels
@asmwarriorYT
@asmwarriorYT 10 ай бұрын
This is the great tutorial. My question is how to make such great animation? Do you use Python manim?
@anwerarif894
@anwerarif894 Жыл бұрын
I have question Why we always use Fourier in communication and laplace in control system??
@samuelthecamel
@samuelthecamel Жыл бұрын
Wow, that was actually really simple
@aakashprasad114
@aakashprasad114 4 ай бұрын
Unrelated but at 21:50 if you look at the cos x and sinx graphs from the side it looks like sec x and csc x respectively
@bereck7735
@bereck7735 Жыл бұрын
Nice video, very informative.
@zyansheep
@zyansheep Жыл бұрын
Bro the video hasn't even been out for 3 minutes yet
@bereck7735
@bereck7735 Жыл бұрын
@@zyansheep I know, I previewed the video entirely so its parts and it has a lot of information.
@zyansheep
@zyansheep Жыл бұрын
@@bereck7735 ah ok
@harriehausenman8623
@harriehausenman8623 Жыл бұрын
Nice comment, very informative. 😄
@el_lahw__el_khafi
@el_lahw__el_khafi Жыл бұрын
Perfect Brilliant Maaaaan ! I love you
@iamtraditi4075
@iamtraditi4075 Жыл бұрын
That sponsorship integration was slick. Great video!
@harriehausenman8623
@harriehausenman8623 Жыл бұрын
A perfect Ed (Educational Ad) 😄
@programmieraufgaben8391
@programmieraufgaben8391 Жыл бұрын
Nice video !
@japedr
@japedr Жыл бұрын
22:25 a bit convoluted... I see what you did there :)
@JochemKuijpers
@JochemKuijpers Жыл бұрын
I'm still somewhat lost on how a DFT can be used to analyze and e.g. equalize music, since we're not dealing with constant frequencies here. How do you expand this to a dynamically changing frequency domain?
@1990JRW
@1990JRW 5 ай бұрын
Remember how each frequency or frequency bin has its own amplitude when you have a DFT. An equalizer is just a scaler on each frequency bin...or a "weight". So an equalizer can be made by doing a FFT, applying your "weights" and doing a IFFT, to get back to having the data as voltage vs time samples. That can be run in real time using dedicated hardware or in software.
@subhadipkarmakar2841
@subhadipkarmakar2841 Жыл бұрын
Really amazing ✴️
@General12th
@General12th Жыл бұрын
Your voice has a pretty strong echo in this video. It sounds quite different from your previous videos.
@hashdankhog8578
@hashdankhog8578 Жыл бұрын
didnt you go over this when you talked about the fft?
@dogslife4831
@dogslife4831 6 ай бұрын
This video is worth a few million views 💪🏻😎
@user-eb6wt3cn6q
@user-eb6wt3cn6q 11 ай бұрын
this is magical
@vit78ify
@vit78ify Жыл бұрын
It would be interesting to learn about how that works 'in real time', as in how software manages to split different frequencies in a piece of audio that isn't just a stable set of sine waves, which is how it becomes useful for daily use as pretty much nothing in the real world is just a stable set of sine waves. Does the software just split the audio into tiny chunks and do a simple FFT on each segment? If it's something more complicated I'm sure it's very interesting, though I guess it also starts becoming more a problem of audio engineering than CS, and drifts away from the focus of this channel
@electrified4251
@electrified4251 4 ай бұрын
Yes in real time audio processing what you do is buffer your input signal into chunks. The length of these chunks corresponds to the time window you have defined freely in your planning stage and it depends how fast your hardware can process one of your chunks. Luckily with the Fast Fourier transform and its children we have an algorithm with a good runtime. This is important because the buffering time needs to be longer than the guaranteed processing time of the the previous sample. Also, since we saw in the video the length of the input and output vectors of the dft is the same so the resolution of your DFT corresponds directly with the length of our Time Signal. This can be mitigated with so called "zero padding" of the input vector and calculating a longer DFT(some lengths of fft are faster to calculate than others, in most algorithms these are power of 2 length ffts)
@angelorf
@angelorf Жыл бұрын
I don't understand what you say about the imaginary parts canceling out. Why would we add the complex numbers of multiple frequencies together? Why would we want to cancel out the imaginary part, if it's used to get the magnitude of each frequency?
@anim8dideas849
@anim8dideas849 Жыл бұрын
nice video but it sounds like the audio is off and is a little muffled and hard to hear on my headphones.
@briefcasemanx
@briefcasemanx 2 күн бұрын
The Shannon-Nyquist explanation is pretty misleading here, I think. You only need 2 points to sample a 7hz (or any other hz) wave. It's about the speed of sampling, not the number of points. The only reason you need 15 points here is specifically because of the length of the waveform shown.
@sounakkundu6115
@sounakkundu6115 7 ай бұрын
My question is regarding your thought experiment at around 3:30 . You say that we cannot sample 14 evenly spaced points because they can be arranged as a constant signal(on line y=0). But we can also arrange 15 evenly spaced points to give a constant signal(also on y=0) ....then why is it also not insufficient. Am i missing something here??
@sounakkundu6115
@sounakkundu6115 7 ай бұрын
Also another doubt, if we can represent a signal as multiple frequencies, why cannot we represent sin(x) by multiple frequencies other than its own? Why must sin(x) be only represented as all 0's except at frequency 2*pi, instead of 0 at 2*pi and some non zero value at other frequencies?
@professeurredstone2134
@professeurredstone2134 Жыл бұрын
Love it !
@init_yeah
@init_yeah Жыл бұрын
Hes alive!!!!
@AmCanTech
@AmCanTech Жыл бұрын
like the FFT video about nuclear testing
@mdtanvirahmedsagor6146
@mdtanvirahmedsagor6146 11 ай бұрын
Quality content 🫰
@rherydrevins
@rherydrevins Жыл бұрын
Alternatively: What if instead of using pairs of cosines and sines at a particular frequency, you used a single sinusoid with 45-degree phase, so that it has a non-zero dot product with both sines and cosines which are matched with its frequency? The result is the discrete Hartley transform.
@angeldude101
@angeldude101 Жыл бұрын
Ultimately it has the same problem. The cosine wave projects the result onto a 0° phase; the sine wave projects it onto a 90° phase, and your suggestion projects it onto a 45° phase. As it turns out, real waveforms have phases other than those specific 3 (or 6 if you include their opposites). Besides, sine and cosine are just two halves of a whole anyways. Just use the whole circle.
@rherydrevins
@rherydrevins Жыл бұрын
@@angeldude101 FYI, I didn't invent the discrete Hartley transform. It has the nice properties that for real-valued signals, you get real-valued output, and there is no redundancy in the results (unlike for the Fourier transform, where for real-valued signals the negative-frequency components are simply the complex conjugate of the positive-frequency components). Fast algorithms to calculate it generally lean on the FFT, though, so practically speaking it's more of a curiosity than anything else.
@angeldude101
@angeldude101 Жыл бұрын
@@rherydrevins The Hartley transform being completely ℝeal actually made it very useful for what I was just doing, which was applying Fourier to a 2D image in-place with a shader, so the standard Fourier transform would've needed 6 components per pixel (2 per color channel) when I only have 4. (A quaternion Fourier transform on the other hand...)
@Xayuap
@Xayuap Жыл бұрын
thanks
@alexvass
@alexvass Жыл бұрын
Thanks
@johnraviella6561
@johnraviella6561 Жыл бұрын
lol, now one of the little science youtube channels does a video on the DFT. thanks buddies.
@bhuvan1036
@bhuvan1036 11 ай бұрын
"is best understood through the lens of music" me: synthwave lessgooooo
@ankarl6492
@ankarl6492 Жыл бұрын
why does the cosine have k/N?
@realcygnus
@realcygnus Жыл бұрын
Nifty !
@blakemorris1300
@blakemorris1300 Жыл бұрын
Why is it so important that it's invertible? We already have the inverse, it's the signal we're analysing
@japanada11
@japanada11 Жыл бұрын
because in signal processing you often want to _change_ the signal in some way. You convert time domain to frequency domain, then do something to the frequencies (e.g. strengthen or weaken certain frequencies to your liking), but then how do you turn that new frequency information back into a time-domain signal?
@blakemorris1300
@blakemorris1300 Жыл бұрын
@@japanada11 Ahh of course. That makes a lot of sense, thank you!
@harriehausenman8623
@harriehausenman8623 Жыл бұрын
You are right. For pure analysis this is not important, but for the DFT it is, as it mathematically makes sense and also represents the usecases, as JL pointed out, much better. Thanks for making me think about that (no irony!) 🤗
@deepjoshi356
@deepjoshi356 Жыл бұрын
Imagine by tasting the dish and being able to tell all the ingredients of it. Now try to keep the same taste with only 5% of items available. That is how jpeg works using DFT.
@kwan3217
@kwan3217 Жыл бұрын
So if the DFT is a matrix multiplication, and the FFT is a quick way to evaluate the DFT, then can some form of divide-and-conquer algorithm be used to multiply general matrices? I would be interested to see how an FFT works in the context of this matrix representation of DFT. I've tried watching this channel's other video on FFT, but the polynomials lost me. I'd love to see a combination of this DFT video and that FFT video, focusing on signal processing and maybe showing the DFT matrix being partitioned into smaller and smaller pieces.
@peroaman5903
@peroaman5903 3 ай бұрын
Sorry! But I'm going to download all your videos too watch offline, without being disturbed by ads. Forgive me 💜💜
@112Nelo
@112Nelo Жыл бұрын
I liked the parts where the lines moved
@merseyless
@merseyless Жыл бұрын
Now just cover windowing functions and my life will be complete.
@harriehausenman8623
@harriehausenman8623 Жыл бұрын
*pretty please* 🥺
@armanhasan-pl4oi
@armanhasan-pl4oi 8 ай бұрын
Awesome
@mertaliyigit3288
@mertaliyigit3288 Жыл бұрын
NTT when
@viktorloshak638
@viktorloshak638 Жыл бұрын
To be honest, it was very difficult for me to understand all the author was saying. I understood 3blue1brown video on FT on the first try, this video on the contrary I had to rewatch about 4 times in total. And I'm still not totally getting it. The visualizations you make are not explained enough. For example the animation you have in the end( the part is called defining true dft) why are there 2 points on the circle. Why is multiplying base frequency sample by analysis frequency matrix results in one unit circle and not the vector like it was before when we were talking about pure cosine analysis signals(see 10.10 time code). Why does the matrix have to be orthogonal in order to satisfy first two properties of the fourier transform we are looking for(namely if y=a the f is not 0, else f=0, see timecode at 11.20). I'm not a physics student so what is angular frequency (author mentions it at the end when explains winding around the unit circle)? Many things in this video are not intuitive to me, although I tend to think that I have the prerequisites for understanding this algorithm, yeah..... The main thing I took away from here is the dot product prospective on the fourier transform part under the integral, which contrasts with 3b1b prospective of thinking about it as finding the center of mass. You already made the video 30 minutes long. Would it be worse to make it 45 but explain all the details???
@viktorloshak638
@viktorloshak638 Жыл бұрын
Everyone is saying " Wow, it's really simple in the coments". I wonder how many of them actually understood everything the author was saying. I'm not trying to hate, I'm just disappointed.
@viktorloshak638
@viktorloshak638 Жыл бұрын
Looks like at the end you just got lazy and stopped animating, and just read text and that's why understanding of what you are explaining decreases closer to the end. What does it mean " the second peak corresponds to the complex exponential that has an underlying frequency that is moving in the opposite direction and perfectly cancels out the imaginary component of the first complex exponential" What does it mean for a frequency to be moving? How does it cancel out the imaginary component. I don't understand it.
@sounakkundu6115
@sounakkundu6115 7 ай бұрын
I think I have an answer. In last part of video...the author combines the sampled analysis frequency points for both sin and cosine into a single matrix. So each element of the matrix [i,j] is a pair of the form (cos(j*i), sin(j*i)). NOTE: Here 'i' is what the author refers to as "frequency". It is called so because its value determines how "frequent"-ly the function will repeat itself. Observe how as we move down the rows, the number of cycles of the sine and cosine keep increasing i the fixed range under consideration. Now for all real number 'j' if we plot pairs of this form as points on cartesian coordinate plane then we get the circle. Depending on the points sampled in the matrix we will get the different bold points on this circle (sometimes 1 sometimes 2 etc.)
@sounakkundu6115
@sounakkundu6115 7 ай бұрын
For the other question....first consider the following definition of orthogonality: 2 vectors A and B are orthogonal iff A.B = 0 (dot product is 0) Now for the matrix to be orthogonal, the dot product of any 2 rows must be zero. This fact follows from the properties 1 and 2. It can be observed by considering as the "base frequency" column, different rows of the analysis frequency matrix (i.e. different analysis frequencies) and then evaluating the equation using the assumed properties in our transform.
@kngod5337
@kngod5337 Жыл бұрын
Is this video particularly well animated or is it just me?
@martinkunev9911
@martinkunev9911 Жыл бұрын
not sure but it looks like it uses 3blue1brown's the manim library
@kngod5337
@kngod5337 Жыл бұрын
@@martinkunev9911 i know i mean compared to previous videos this one seems more polished. For example i think it's the first time i see that intro sequence
@harriehausenman8623
@harriehausenman8623 Жыл бұрын
@@kngod5337 Yeah, that intro was sick! BESTAGONS FTW 😄
Wavelets: a mathematical microscope
34:29
Artem Kirsanov
Рет қаралды 588 М.
The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?
28:23
одни дома // EVA mash @TweetvilleCartoon
01:00
EVA mash
Рет қаралды 4,2 МЛН
Duck sushi
00:54
Alina Saito / 斎藤アリーナ
Рет қаралды 35 МЛН
白天使和小丑帮助黑天使。#天使 #超人不会飞 #超人夫妇
00:42
Самый большой бутер в столовке! @krus-kos
00:42
Кушать Хочу
Рет қаралды 6 МЛН
#0_ZeroToHero - Introduction
8:07
TheP9er
Рет қаралды 10
But what is a convolution?
23:01
3Blue1Brown
Рет қаралды 2,4 МЛН
The Fourier Series and Fourier Transform Demystified
14:48
Up and Atom
Рет қаралды 758 М.
But what is the Riemann zeta function? Visualizing analytic continuation
22:11
The Traveling Salesman Problem: When Good Enough Beats Perfect
30:27
The Discrete Fourier Transform (DFT)
17:36
Steve Brunton
Рет қаралды 322 М.
We should use this amazing mechanism that's inside a grasshopper leg
19:19
одни дома // EVA mash @TweetvilleCartoon
01:00
EVA mash
Рет қаралды 4,2 МЛН