4 ms·

It is super to easy to find resources on HOW the FT works. But I find it very difficult to find resources on WHY we need it and WHERE it is useful to have. Doe

It is super to easy to find resources on HOW the FT works. But I find it very difficult to find resources on WHY we need it and WHERE it is useful to have. Does anybody have some good sources that explain the practical applications and how it is useful on real world usage?

CaptainFever 3y ago
From TFA: Stop. Here's where most tutorials excitedly throw engineering applications at your face. Don't get scared; think of the examples as "Wow, we're finally seeing the source code (DNA) behind previously confusing ideas". If earthquake vibrations can be separated into "ingredients" (vibrations of different speeds & amplitudes), buildings can be designed to avoid interacting with the strongest ones. If sound waves can be separated into ingredients (bass and treble frequencies), we can boost the parts we care about, and hide the ones we don't. The crackle of random noise can be removed. Maybe similar "sound recipes" can be compared (music recognition services compare recipes, not the raw audio clips). If computer data can be represented with oscillating patterns, perhaps the least-important ones can be ignored. This "lossy compression" can drastically shrink file sizes (and why JPEG and MP3 files are much smaller than raw .bmp or .wav files). If a radio wave is our signal, we can use filters to listen to a particular channel. In the smoothie world, imagine each person paid attention to a different ingredient: Adam looks for apples, Bob looks for bananas, and Charlie gets cauliflower (sorry bud). The Fourier Transform is useful in engineering, sure, but it's a metaphor about finding the root causes behind an observed effect.
- kkapelon 3y ago
  Yes I saw that. But it still hides the "meaty" part. Where are the articles that explain those processes? For example I would love to find an article that starts with "let's make a wav file smaller". And then somewhere in the middle it just says "and here we will use FT to achieve X".
  - rescbr 3y ago
    It's not an article, but I found The Scientist and Engineer's Guide to Digital Signal Processing book to be very comprehensive. There are a couple of chapters on applications, but not much code. http://www.dspguide.com/pdfbook.htm http://www.dspguide.com/pdfbook.htm
  - AlotOfReading 3y ago
    Here's a pretty good lecture on exactly that subject: https://www.rose-hulman.edu/~bryan/invprobs/jpegtalk2.pdf https://www.rose-hulman.edu/~bryan/invprobs/jpegtalk2.pdf Honestly though, the Fourier transform is useful anywhere that it's easy to think in terms of frequency instead of time. 90% of use cases in the real world come about from trying to do something that's that's easy to express in terms of signal frequency and difficult to express in terms of signal time/space. You can just use the Fourier transform to convert between them efficiently. To give a morbid, but non-obvious example, I once did some work with a charity that was concerned with migrant deaths. They wanted to figure out where the migrants most at risk were working to approach the farmers hiring them directly. We got a dataset of when migrant bodies were found and did an FFT (among other processing) to find the periodicity of the crops that they were coming to harvest. There's only a few major crops and they tend to have distinct growing periods, so this is enough information to pinpoint certain crops like strawberries.
  - drtgh 3y ago
    FT breaks down a cyclic signal into the frequencies present, and their intensity. The longer the sample of the signal, the more precise becomes detecting the real frequencies present in the signal. Mainly is tool for to obtain information that will feed latter other algorithms. Also can be used as a signal filter with the Inverse FT. If this does help to understand, it is homologous to use several band pass filters repeatedly for trying to obtain the root signals, but without adjustments requirements, highly faster to compute, simpler, and with better result. So your question is, What are the uses of knowing the main elements that make up a signal? That information is useful for analysis of sounds or images, for to detect the presence of elements composing the signal out of the expected range. Also for pattern detection, as you may give the data a signal form of your own, and analyze the frequencies peaks for example. For compression, the above two, as knowing the main cyclic elements and their intensity allows to determine if some ones may be latter omitted (for loss compression), or what elements latter should be replaced as parameters that the decompression algorithm will use for to reconstruct the signal. Also it is important what said the other answer. It does not give information about the time/space moment in with is produced the element, it only tells the element is present (the frequency in the signal).
sizzzzlerz 3y ago
Your cell phone wouldn't exist without the Fourier Transform, or the discrete fourier transform, to be correct. Image compression is another application, albeit, a 2-dimensional version. Software defined radios, or SDR, are completely dependent on the DFT. Radar processing. Earthquake analysis. The list goes on and on. Basically, our technological society would not exist in its current form without the fourier transform. To me, it is one of the key mathematical algorithms of the 20th century.
- kkapelon 3y ago
  > Your cell phone wouldn't exist without the Fourier Transform, or the discrete fourier transform, to be correct Yes that is great to know. But where can I find an article that explains how exactly FT helps in my cell phone? What exactly do we do with FT in a cell phone?
  - rjeli 3y ago
    For example, to create a JPEG, part of the process is removing the "high frequency" parts of your image, since those take the most information to store. Here, high frequency refers to noise, or any large difference between neighboring pixels, as opposed to low frequency parts, which are averages over larger groups of pixels. So, at the extreme, if you average the whole image, you only have to store one pixel, so it's obviously less data to store, vs storing info about every single pixel. JPEG (and other lossy compression formats) tries to find a good middle ground between storing every pixel perfectly and storing just one pixel. So, how do you remove the high frequency parts? You apply a Fourier transform to the image (in this case, it's a "Discrete Cosine Transform", which is extremely similar to a DFT and has no differences for the purpose of this explanation) and get a 2d array. This 2d array has the low frequency parts in the upper left corner, and the high frequency parts everywhere else (to the right and down for horizontal and vertical frequencies). So your compression algorithm will simply zero out the high frequency parts so you don't have to store them. In the simplest case, this is equivalent to a simple blur of the image, but there are some heuristics about how much to remove (zero out) to minimize image degradation. To decode the image, you take the 2d array and apply the inverse FT to get the original image (now slightly blurry because it's been compressed). More details here: https://en.wikipedia.org/wiki/JPEG#Discrete_cosine_transform https://en.wikipedia.org/wiki/JPEG#Discrete_cosine_transform
adamnemecek 3y ago
Making convolution faster.
- kkapelon 3y ago
  This is circular logic. So what real world problems we have right now that depend on making convolution faster?
  - adamnemecek 3y ago
    Literally everything. The list of thing that are not some type of convolution is really short. Name 5 concepts and I'll try to connect it to convolution.
jezzamon 3y ago
Disclaimer: I wrote this, but it's a little more from an engineering POV than a Math POV, and covers some applications: jezzamon.com/fourier Hacker news folks seem to enjoy it :) Another thought on the "why": many things in the real world operate on frequencies, sound being the most obvious but also electrical signals, mechanical systems like springs, etc. Doing the analysis representing a signal as a bunch of frequencies makes more sense, and Fourier transforms lets us do that
photochemsyn 3y ago
Here's a nice example with the Fast Fourier Transform (an algorithm for computing the Dicrete Fourier Transform more efficiently): Source: PCA and Fourier Analysis (2010) J Banfelder, Weill Cornell Medical College > "A beautiful example of how this knowledge can be used in medicine is found in the cochlear implant. This device is used in patients with inner ear damage. The entire mechanical transduction mechanism is bypassed when the device is implanted. Instead, a microphone worn on the outer ear records sound that is digitized and sent to a signal processor. Here an FFT and an array of bandpass filters are applied. Results are passed to the implanted device, which electrically stimulates the neurons in the cochlea. Typical devices divide the frequency range of 0 to 4 kHz into about 15 or 20 bands, and stimulate neurons accordingly. However, profoundly deaf patients have recovered their hearing and have been able to understand speech even when as few as five bands are used." See also: https://allsignalprocessing.com/lessons/the-four-fourier-representations/ https://allsignalprocessing.com/lessons/the-four-fourier-rep...
duped 3y ago
I don't think there's a satisfying concise answer to this question. You're asking to boil down multiple semesters of engineering and mathematics courses to explain something that isn't simple. The "why" we need it is because it's a convenient mathematical tool to simplify complex problems dealing with sequences/series. It decomposes sequences of numbers (*) into another sequence of numbers that represents a summation of repeating patterns in the original sequence. The "where" we use it is anywhere that knowing about which patterns show up in sequence of numbers might be more convenient than looking at the original sequence. There are other nice properties, too. There's a mathematical operation called convolution that's very useful in domains operating with sequences of numbers (machine learning, control systems, audio and image processing, etc). It happens that convolution in the original signal's domain is equivalent to multiplication in the fourier domain. Why that's useful is that convolution is an O(N^2) algorithm but we can compute the Fourier transform in O(nlogn) complexity (**) and multiplication is constant. We can even do things like deconvolution (taking an output signal that we know was convolved with something else) and extract one of the inputs. Another nice property of the Fourier transform is that most sequences of numbers do not have lots of energy (meaning magnitude) in "high frequency" (meaning fastly repeating patterns in the original domain). The FT of a sequence of numbers will naturally compact most of the information of the sequence into few places. We can exploit this for lossy compression (***). Ultimately, it's a way of taking information that is hard to grok and transforming it to a domain that's more meaningful and operations/analysis are easier. Both for humans and machines. * And it works on continuous functions too, but let's not get into that ** Technically this is a variant called "circular" convolution *** The FT is not the most convenient tool for this job, so very closely related transforms like the DCT can be used, which have the same computational advantages of the FT.
gwbas1c 3y ago
Some of the more well-known examples are: Low-bitrate audio compression (MP3) use Fourier transforms. Image and video compression use Fourier transforms. Less-well-known: AC electricity has to run at (almost) exactly 60hz / 50hz. The power plants use Fourier transforms to measure the exact frequency. (And then use the measurement to adjust accordingly.) Some telecommunications techniques may use Fourier transforms: IE, the dial-up modems used in the 1990s used Fourier transforms to interpret the analog signal and determine what the bits were. This article explains using a Fourier transform to remove the "dots" from an image that was printed in a book: https://matzjb.se/2015/08/08/smoothing-a-halftone-photo-using-fft/ https://matzjb.se/2015/08/08/smoothing-a-halftone-photo-usin...
throwaway3091 3y ago
[dead]

CaptainFever 3y ago

From TFA: Stop. Here's where most tutorials excitedly throw engineering applications at your face. Don't get scared; think of the examples as "Wow, we're finally seeing the source code (DNA) behind previously confusing ideas". If earthquake vibrations can be separated into "ingredients" (vibrations of different speeds & amplitudes), buildings can be designed to avoid interacting with the strongest ones. If sound waves can be separated into ingredients (bass and treble frequencies), we can boost the parts we care about, and hide the ones we don't. The crackle of random noise can be removed. Maybe similar "sound recipes" can be compared (music recognition services compare recipes, not the raw audio clips). If computer data can be represented with oscillating patterns, perhaps the least-important ones can be ignored. This "lossy compression" can drastically shrink file sizes (and why JPEG and MP3 files are much smaller than raw .bmp or .wav files). If a radio wave is our signal, we can use filters to listen to a particular channel. In the smoothie world, imagine each person paid attention to a different ingredient: Adam looks for apples, Bob looks for bananas, and Charlie gets cauliflower (sorry bud). The Fourier Transform is useful in engineering, sure, but it's a metaphor about finding the root causes behind an observed effect.

kkapelon 3y ago
Yes I saw that. But it still hides the "meaty" part. Where are the articles that explain those processes? For example I would love to find an article that starts with "let's make a wav file smaller". And then somewhere in the middle it just says "and here we will use FT to achieve X".
- rescbr 3y ago
  It's not an article, but I found The Scientist and Engineer's Guide to Digital Signal Processing book to be very comprehensive. There are a couple of chapters on applications, but not much code. http://www.dspguide.com/pdfbook.htm http://www.dspguide.com/pdfbook.htm
- AlotOfReading 3y ago
  Here's a pretty good lecture on exactly that subject: https://www.rose-hulman.edu/~bryan/invprobs/jpegtalk2.pdf https://www.rose-hulman.edu/~bryan/invprobs/jpegtalk2.pdf Honestly though, the Fourier transform is useful anywhere that it's easy to think in terms of frequency instead of time. 90% of use cases in the real world come about from trying to do something that's that's easy to express in terms of signal frequency and difficult to express in terms of signal time/space. You can just use the Fourier transform to convert between them efficiently. To give a morbid, but non-obvious example, I once did some work with a charity that was concerned with migrant deaths. They wanted to figure out where the migrants most at risk were working to approach the farmers hiring them directly. We got a dataset of when migrant bodies were found and did an FFT (among other processing) to find the periodicity of the crops that they were coming to harvest. There's only a few major crops and they tend to have distinct growing periods, so this is enough information to pinpoint certain crops like strawberries.
- drtgh 3y ago
  FT breaks down a cyclic signal into the frequencies present, and their intensity. The longer the sample of the signal, the more precise becomes detecting the real frequencies present in the signal. Mainly is tool for to obtain information that will feed latter other algorithms. Also can be used as a signal filter with the Inverse FT. If this does help to understand, it is homologous to use several band pass filters repeatedly for trying to obtain the root signals, but without adjustments requirements, highly faster to compute, simpler, and with better result. So your question is, What are the uses of knowing the main elements that make up a signal? That information is useful for analysis of sounds or images, for to detect the presence of elements composing the signal out of the expected range. Also for pattern detection, as you may give the data a signal form of your own, and analyze the frequencies peaks for example. For compression, the above two, as knowing the main cyclic elements and their intensity allows to determine if some ones may be latter omitted (for loss compression), or what elements latter should be replaced as parameters that the decompression algorithm will use for to reconstruct the signal. Also it is important what said the other answer. It does not give information about the time/space moment in with is produced the element, it only tells the element is present (the frequency in the signal).

sizzzzlerz 3y ago

Your cell phone wouldn't exist without the Fourier Transform, or the discrete fourier transform, to be correct. Image compression is another application, albeit, a 2-dimensional version. Software defined radios, or SDR, are completely dependent on the DFT. Radar processing. Earthquake analysis. The list goes on and on. Basically, our technological society would not exist in its current form without the fourier transform. To me, it is one of the key mathematical algorithms of the 20th century.

kkapelon 3y ago
> Your cell phone wouldn't exist without the Fourier Transform, or the discrete fourier transform, to be correct Yes that is great to know. But where can I find an article that explains how exactly FT helps in my cell phone? What exactly do we do with FT in a cell phone?
- rjeli 3y ago
  For example, to create a JPEG, part of the process is removing the "high frequency" parts of your image, since those take the most information to store. Here, high frequency refers to noise, or any large difference between neighboring pixels, as opposed to low frequency parts, which are averages over larger groups of pixels. So, at the extreme, if you average the whole image, you only have to store one pixel, so it's obviously less data to store, vs storing info about every single pixel. JPEG (and other lossy compression formats) tries to find a good middle ground between storing every pixel perfectly and storing just one pixel. So, how do you remove the high frequency parts? You apply a Fourier transform to the image (in this case, it's a "Discrete Cosine Transform", which is extremely similar to a DFT and has no differences for the purpose of this explanation) and get a 2d array. This 2d array has the low frequency parts in the upper left corner, and the high frequency parts everywhere else (to the right and down for horizontal and vertical frequencies). So your compression algorithm will simply zero out the high frequency parts so you don't have to store them. In the simplest case, this is equivalent to a simple blur of the image, but there are some heuristics about how much to remove (zero out) to minimize image degradation. To decode the image, you take the 2d array and apply the inverse FT to get the original image (now slightly blurry because it's been compressed). More details here: https://en.wikipedia.org/wiki/JPEG#Discrete_cosine_transform https://en.wikipedia.org/wiki/JPEG#Discrete_cosine_transform

adamnemecek 3y ago

Making convolution faster.

kkapelon 3y ago
This is circular logic. So what real world problems we have right now that depend on making convolution faster?
- adamnemecek 3y ago
  Literally everything. The list of thing that are not some type of convolution is really short. Name 5 concepts and I'll try to connect it to convolution.

jezzamon 3y ago

Disclaimer: I wrote this, but it's a little more from an engineering POV than a Math POV, and covers some applications: jezzamon.com/fourier Hacker news folks seem to enjoy it :) Another thought on the "why": many things in the real world operate on frequencies, sound being the most obvious but also electrical signals, mechanical systems like springs, etc. Doing the analysis representing a signal as a bunch of frequencies makes more sense, and Fourier transforms lets us do that

photochemsyn 3y ago

Here's a nice example with the Fast Fourier Transform (an algorithm for computing the Dicrete Fourier Transform more efficiently): Source: PCA and Fourier Analysis (2010) J Banfelder, Weill Cornell Medical College > "A beautiful example of how this knowledge can be used in medicine is found in the cochlear implant. This device is used in patients with inner ear damage. The entire mechanical transduction mechanism is bypassed when the device is implanted. Instead, a microphone worn on the outer ear records sound that is digitized and sent to a signal processor. Here an FFT and an array of bandpass filters are applied. Results are passed to the implanted device, which electrically stimulates the neurons in the cochlea. Typical devices divide the frequency range of 0 to 4 kHz into about 15 or 20 bands, and stimulate neurons accordingly. However, profoundly deaf patients have recovered their hearing and have been able to understand speech even when as few as five bands are used." See also: https://allsignalprocessing.com/lessons/the-four-fourier-representations/ https://allsignalprocessing.com/lessons/the-four-fourier-rep...

duped 3y ago

I don't think there's a satisfying concise answer to this question. You're asking to boil down multiple semesters of engineering and mathematics courses to explain something that isn't simple. The "why" we need it is because it's a convenient mathematical tool to simplify complex problems dealing with sequences/series. It decomposes sequences of numbers (*) into another sequence of numbers that represents a summation of repeating patterns in the original sequence. The "where" we use it is anywhere that knowing about which patterns show up in sequence of numbers might be more convenient than looking at the original sequence. There are other nice properties, too. There's a mathematical operation called convolution that's very useful in domains operating with sequences of numbers (machine learning, control systems, audio and image processing, etc). It happens that convolution in the original signal's domain is equivalent to multiplication in the fourier domain. Why that's useful is that convolution is an O(N^2) algorithm but we can compute the Fourier transform in O(nlogn) complexity (**) and multiplication is constant. We can even do things like deconvolution (taking an output signal that we know was convolved with something else) and extract one of the inputs. Another nice property of the Fourier transform is that most sequences of numbers do not have lots of energy (meaning magnitude) in "high frequency" (meaning fastly repeating patterns in the original domain). The FT of a sequence of numbers will naturally compact most of the information of the sequence into few places. We can exploit this for lossy compression (***). Ultimately, it's a way of taking information that is hard to grok and transforming it to a domain that's more meaningful and operations/analysis are easier. Both for humans and machines. * And it works on continuous functions too, but let's not get into that ** Technically this is a variant called "circular" convolution *** The FT is not the most convenient tool for this job, so very closely related transforms like the DCT can be used, which have the same computational advantages of the FT.

gwbas1c 3y ago

Some of the more well-known examples are: Low-bitrate audio compression (MP3) use Fourier transforms. Image and video compression use Fourier transforms. Less-well-known: AC electricity has to run at (almost) exactly 60hz / 50hz. The power plants use Fourier transforms to measure the exact frequency. (And then use the measurement to adjust accordingly.) Some telecommunications techniques may use Fourier transforms: IE, the dial-up modems used in the 1990s used Fourier transforms to interpret the analog signal and determine what the bits were. This article explains using a Fourier transform to remove the "dots" from an image that was printed in a book: https://matzjb.se/2015/08/08/smoothing-a-halftone-photo-using-fft/ https://matzjb.se/2015/08/08/smoothing-a-halftone-photo-usin...

throwaway3091 3y ago

[dead]