Hacker News Reader

Comment by kkapelon | Hacker News Reader

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?

View on HN

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.

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

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

Here's a pretty good lecture on exactly that subject: 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.

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

If you understand the fourier transform, you should have some idea of its inverse. And that's exactly how (one part) of compressing an image or audio works.

You take a signal, take its fourier transform, and then cut off the frequencies above some threshold you don't care about (I'm ignoring certain complicating factors for simplicity). Let's say your original signal has frequencies up to 22KHz. If you're only interested in moderate fidelity human voices talking, maybe you cut off everything below 100 Hz and above 3.4 KHz. You just toss that information. Then on the receiving end, you do an inverse DFT and reconstruct the signal.

JPG and MP3 do something like this, along with a pile of other tricks.

Take a look at [0] to get a quick visual demonstration of how that works. As others have said, lossy compression often throws away high frequency data (for sound, it corresponds to high pitches that you can barely hear. For images, high frequency corresponds to fast changing parts of a picture, so think crisp edges, fine detail (e.g. hair or stubble), and noise/film grain). So a basic lossy compression algorithm might use a FT and then only store the lower frequencies. When you do the inverse transform without the high frequency data, you lose details.

Note that the spectrograms in [0] use what's called a short time fourier transform[1]. Basically, split your song into windows (e.g. 1 second each), and do a fourier transform on each window. This lets you get a picture of the spectrum over time.

[0] https://sound.stackexchange.com/questions/38709/320kbps-mp3-...

[1] https://en.wikipedia.org/wiki/Short-time_Fourier_transform

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.

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

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

We went from mostly fearing vibrations in a mechanical world to harnessing them in a chemical and electrical world. It entirely reshaped our relationship to the world and perhaps so fast that our brains haven't entirely caught up yet. I wonder how many well controlled oscillations of mostly electrical charges happened between me swyping this and you hearing it in your head. We rely on them instead of fearing them now.

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.

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