### Why is the Fourier transform so important?

Everyone discusses the Fourier transform when discussing signal processing. Why is it so important to signal processing and what does it tell us about the signal?

Does it only apply to digital signal processing or does it apply to analog signals as well?

cf. **this answer** for some excellent historical background. Fourier series date at least as far back as Ptolemy's epicyclic astronomy. Adding more eccentrics and epicycles, akin to adding more terms to a Fourier series, one can account for *any* continuous motion of an object in the sky.

Lorem Ipsum Correct answer

9 years agoThis is quite a broad question and it indeed is quite hard to pinpoint

*why exactly*Fourier transforms are important in signal processing. The simplest, hand waving answer one can provide is that it is an*extremely*powerful mathematical tool that allows you to view your signals in a different domain, inside which several difficult problems become very simple to analyze.Its ubiquity in nearly every field of engineering and physical sciences, all for different reasons, makes it all the more harder to narrow down a reason. I hope that looking at some of its properties which led to its widespread adoption along with some practical examples and a dash of history might help one to understand its importance.

### History:

To understand the importance of the Fourier transform, it is important to step back a little and appreciate the power of the Fourier series put forth by Joseph Fourier. In a nut-shell, any periodic function $g(x)$ integrable on the domain $\mathcal{D}=[-\pi,\pi]$ can be written as an infinite sum of sines and cosines as

$$g(x)=\sum_{k=-\infty}^{\infty}\tau_k e^{\jmath k x}$$ $$\tau_k=\frac{1}{2\pi}\int_{\mathcal{D}}g(x)e^{-\jmath k x}\ dx$$

where $e^{\imath\theta}=\cos(\theta)+\jmath\sin(\theta)$.

*This idea that a function could be broken down into its constituent frequencies (i.e., into sines and cosines of all frequencies) was a powerful one and forms the backbone of the Fourier transform.*### The Fourier transform:

The Fourier transform can be viewed as an extension of the above Fourier series to non-periodic functions. For completeness and for clarity, I'll define the Fourier transform here. If $x(t)$ is a continuous, integrable signal, then its Fourier transform, $X(f)$ is given by

$$X(f)=\int_{\mathbb{R}}x(t)e^{-\jmath 2\pi f t}\ dt,\quad \forall f\in\mathbb{R}$$

and the inverse transform is given by

$$x(t)=\int_{\mathbb{R}}X(f)e^{\jmath 2\pi f t}\ df,\quad \forall t\in\mathbb{R}$$

### Importance in signal processing:

First and foremost, a Fourier transform of a signal tells you

**what frequencies are present in your signal and in what proportions**.**Example:**Have you ever noticed that each of your phone's number buttons sounds different when you press during a call and that it sounds the same for every phone model? That's because they're each composed of two different sinusoids which can be used to uniquely identify the button. When you use your phone to punch in combinations to navigate a menu, the way that the other party knows what keys you pressed is by doing a Fourier transform of the input and looking at the frequencies present.Apart from some very useful elementary properties which make the mathematics involved simple, some of the other reasons why it has such a widespread importance in signal processing are:

- The magnitude square of the Fourier transform, $\vert X(f)\vert^2$ instantly tells us how much power the signal $x(t)$ has at a particular frequency $f$.
- From Parseval's theorem (more generally Plancherel's theorem), we have $$\int_\mathbb{R}\vert x(t)\vert^2\ dt = \int_\mathbb{R}\vert X(f)\vert^2\ df$$ which means that
*the total energy in a signal across all time is equal to the total energy in the transform across all frequencies*. Thus, the transform is energy preserving. Convolutions in the time domain are equivalent to multiplications in the frequency domain, i.e., given two signals $x(t)$ and $y(t)$, then if

$$z(t)=x(t)\star y(t)$$ where $\star$ denotes convolution, then the Fourier transform of $z(t)$ is merely

$$Z(f)=X(f)\cdot Y(f)$$

For discrete signals, with the development of efficient FFT algorithms, almost always, it is faster to implement a convolution operation in the frequency domain than in the time domain.

- Similar to the convolution operation, cross-correlations are also easily implemented in the frequency domain as $Z(f)=X(f)^*Y(f)$, where $^*$ denotes complex conjugate.
By being able to split signals into their constituent frequencies, one can easily block out certain frequencies selectively by nullifying their contributions.

**Example:**If you're a football (soccer) fan, you might've been annoyed at the constant drone of the vuvuzelas that pretty much drowned all the commentary during the 2010 world cup in South Africa. However, the vuvuzela has a constant pitch of ~235Hz which made it easy for broadcasters to implement a notch filter to cut-off the offending noise.^{[1]}A shifted (delayed) signal in the time domain manifests as a phase change in the frequency domain. While this falls under the elementary property category, this is a widely used property in practice, especially in imaging and tomography applications,

**Example:**When a wave travels through a heterogenous medium, it slows down and speeds up according to changes in the speed of wave propagation in the medium. So by observing a change in phase from what's expected and what's measured, one can infer the excess time delay which in turn tells you how much the wave speed has changed in the medium. This is of course, a very simplified layman explanation, but forms the basis for tomography.Derivatives of signals (n

^{th}derivatives too) can be easily calculated(see 106) using Fourier transforms.

### Digital signal processing (DSP) vs. Analog signal processing (ASP)

The theory of Fourier transforms is applicable irrespective of whether the signal is continuous or discrete, as long as it is "nice" and absolutely integrable. So yes, ASP uses Fourier transforms as long as the signals satisfy this criterion. However, it is perhaps more common to talk about Laplace transforms, which is a generalized Fourier transform, in ASP. The Laplace transform is defined as

$$X(s)=\int_{0}^{\infty}x(t)e^{-st}\ dt,\quad \forall s\in\mathbb{C}$$

The advantage is that one is not necessarily confined to "nice signals" as in the Fourier transform, but the transform is valid only within a certain region of convergence. It is widely used in studying/analyzing/designing LC/RC/LCR circuits, which in turn are used in radios/electric guitars, wah-wah pedals, etc.

This is pretty much all I could think of right now, but do note that

*no amount*of writing/explanation can fully capture the true importance of Fourier transforms in signal processing and in science/engineeringNice answer in giving some realworld application using FT and its properties. +1.

"This idea that a function could be broken down into its constituent frequencies was a powerful one" I think the Taylor series was first. http://en.wikipedia.org/wiki/Taylor_series#History http://en.wikipedia.org/wiki/Fourier_analysis#History "a Fourier transform of a signal tells you what frequencies are present in your signal and in what proportions." Like a prism shows you what frequencies of light are present in a light source

@endolith I didn't say the Fourier transform was first, just that it is _powerful_. Note that a Taylor series is _not_ an expansion in terms of the constituent frequencies. For e.g., the Taylor series of $\sin(\alpha x)$ about $0$ is $\alpha x-\alpha^3x^3/3!+\alpha^5x^5/5!\ldots$, whereas the Fourier transform of $\sin(\alpha x)$ is $\left[\delta(\omega-\alpha)-\delta(\omega+\alpha)\right]/(2\jmath)$ (give or take some normalization factors). The latter is the correct frequency representation, so I'm not sure if any comparisons with Taylor series is apt here.

@yoda: Yes, I miscomprehended as "broken down into a sum of simpler functions", and was just pointing out an alternative way to do that

When I started reading this response, somehow I knew @yoda wrote it before I scrolled down to see who it actually was = )

To elaborate on #3: Convolution is what you do when you apply a filter to an image, such as an average filter, or a Gaussian filter (though you can't Fourier-transform non-linear filters).

Yoda's answer is missing factors of $\frac{1}{2\pi}$ in some key places such as the definition of the Fourier Tranform, Parseval's Theorem, etc. This really should have been a comment on his post, and he could have edited his answer to correct the errors, but I do not have enough reputation on this site to make comments, and so an answer will have to make do.

Peter K's point is really critical. Signals can be represented with respect to *many* different bases. Sines and cosines are special because they are the eigenfunctions of LTI systems.

would this answer be a great candidate to become a community wiki and continuously updated/worked on by the community? This seems like a pretty important question for the community and @yoda has already done a fantastic job but we can update it with the answers below, other communities, etc

Re the vuvuzela example: there are several adequate pure signal-domain solutions for this problem as well, so I wonder if another FFT-only example might be more illuminating here.

This is a lovely answer, but a tiny correction: not every merely *integrable* function is the sum of its Fourier series. This definitely fails pointwise as soon as the function has discontinuities (even at the endpoints), but can even fail in the $\mathrm L^1$ sense (see https://en.wikipedia.org/wiki/Convergence_of_Fourier_series#Convergence_almost_everywhere).

Lorem Ipsum's great answer misses one thing: The Fourier transform decomposes signals into constituent complex exponentials:

$$ e^{\jmath \omega t}$$

and complex exponentials are the

**eigenfunctions**for linear, time invariant systems.Put simply, if a system, $H$ is linear and time-invariant, then its response to a complex exponential will be a complex exponential of the same frequency but (possibly) different phase, $\phi$, and amplitude, $A$, --- and the amplitude may be zero:

$$y = H[e^{\jmath \omega t}] = A e^{\jmath \phi} e^{\jmath \omega t} $$

So the Fourier transform is a useful tool for analyzing linear, time-invariant systems.

@Peter K. I think that following the philosophy of choice on the (academic) correctness over "popularity" of an answer, your answer should be be integrated into the above answer provideded by Lorem Ipsum, which despite being selected as the answer with 96 points by the users, lacks this very important point of view.

@Peter Sorry to disturb you with this request, but you are 1) a moderator, 2) your name appeared on the list of users "active" with your beamforming tag. Can you give a quick opinion whether this post in Math.SE would be well received here? I am not sure, whether DSP.SE, Math.SE or EE.SE has the best chance of helping that asker. I am considering migration (which I can do as a Math.SE moderator).

@Peter K., Could you please reopen the question at: http://dsp.stackexchange.com/questions/37468. I fixed it. Thank You.

@Royi it's already open?

Peter (How come some people can be approached using `@` and some can't? Where is the option for that?), It seems someone opened it. Thank You.

@Royi only the poster of the thing commented on or the commenters or editors can be @-ed.

Another reason:

It's

**fast**(e.g. useful for convolution), due to its linearithmic time complexity (specifically, that of the FFT).

I would argue that, if this were not the case, we would probably be doing a lot more in the time domain, and a lot less in the Fourier domain.### Edit: Since people asked me to write why the FFT is fast...

It's because it cleverly avoids doing extra work.

To give an concrete example of how it works, suppose you were multiplying two polynomials, $a_0 x^0 + a_1 x^1 + \ldots + a_nx^n$ and $b_0 x^0 + b_1 x^1 + \ldots + b_nx^n$.

If you were to do this naively (using the FOIL method), you would need approximately $n^2$ arithmetic operations (give or take a constant factor).

However, we can make a seemingly mundane observation: in order to multiply two polynomials,

*we don't need to FOIL the coefficients*. Instead, we can simply*evaluate*the polynomials at a (sufficient) number of points, do a*pointwise*multiplication of the evaluated values, and then*interpolate*to get back the result.Why is that useful? After all, each polynomial has $n$ terms, and if we were to evaluate each one at $2n$ points, that would still result in $\approx n^2$ operations, so it doesn't seem to help.

But it does, if we do it correctly! Evaluating a single polynomial at

*many*points at once is*faster*than evaluating it at those points individually,*if we evaluate at the "right" points*. What are the "right" points?It turns out those are the roots of unity (i.e. all complex numbers $z$ such that $z^n = 1$). If we choose to evaluate the polynomial at the roots of unity, then a lot of expressions will turn out the same (because a lot of monomials will turn out to be the same). This means we can do their arithmetic

*once*, and re-use it thereafter for evaluating the polynomial at all the other points.We can do a very similar process for interpolating through the points to get back the polynomial coefficients of the result, just by using the

*inverse*roots of unity.There's obviously a lot of math I'm skipping here, but effectively, the FFT is basically the algorithm I just described, to evaluate and interpolate the polynomials.

One of its uses, as I showed, was to multiply polynomials in a lot less time than normal. It turns out that this saves a tremendous amount of work, bringing down the running time to being proportional to $n \log n$ (i.e. linearithmic) instead of $n^2$ (quadratic).Thus the ability to use the FFT to perform a typical operation (such as polynomial multiplication) much faster is what makes it useful, and that is also why people are now excited by MIT's new discovery of the Sparse FFT algorithm.

What is linearithmic time complexity? I won't downvote this answer but I don't think it adds anything of value to this discussion on Fourier **transforms**.

@DilipSarwate I suspect he's using it as shorthand for O(n*log(n)).

@DilipSarwate: Jim is right. It has **everything** to do with (discrete) Fourier transforms. Without the FFT, your Fourier transforms would take time proportional to the *square* of the input size, which would make them a lot less useful. But with the FFT, they take time proportional the size of the input (times its logarithm), which makes them much more useful, and which speeds up a lot of calculations. Also this might be an interesting read.

You should mention WHY its fast. Where its fast and why do we care that its fast?

@CyberMen: I don't understand what you mean... what do you mean "why is it fast"? It's fast because the algorithm is fast... and we care because, well, if you have 10000 points to process, there's a huge difference between an algorithm taking 10000^2 time versus 10000*4 time...

@Mehrdad "It's fast because its fast" What makes the algorithm fast, how is it different than brute force, what does the algorithm take advantage of to make it fast?

@CyberMen: Oh so you want me to describe the whole algorithm? ok lemme edit...

@CyberMen: Updated.

@Downvoters: Is it still that bad? x_x

I think that this answer is legitimate. It should be paraphrased - "Beside all the nice characteristics explained in other peoples answer, FFT allows it to become a feasible approach in real-time applications".

Additional to Peter's answer, there is another reason which is also related to the eigenfunction. That's, $e^{kx}$ is the eigenfunction of the differential operator $\frac{d^n}{dx^n}$. That's why Fourier transform (corresponding to pure imaginary $k$) and Laplace transform (corresponding to complex $k$) can be used to solve differential equations.

Since $e^{kx}$ is the eigenfunction of both convolution and differential operator, maybe that's one the of the reasons why LSIV system can be represented by differential equations.

EDIT: As a matter of fact, differential (and integral) operators are LSIV operators, see here.

Some of the other answers in this thread have excellent mathematical discussions of the definition and properties of the Fourier transform; as an audio programmer, I merely want to provide my own personal intuition as to

*why*it's important to me.The Fourier transform permits me to answer questions about a sound that are difficult or impossible to answer with other methods. It makes hard problems easy.

A recording contains a set of three musical notes. What are the notes? If you leave the recording as a set of amplitudes over time, this is not an easy problem. If you convert the recording to a set of frequencies over time, it's really easy.

I want to change the pitch of a recording without changing its duration. How do I do this? It's possible, but not easy to do, by just manipulating the amplitude of an input signal. But it's easy if you know the frequencies that comprise the signal.

Does this recording contain speech or does it contain music? Super hard to do using only amplitude-based methods. But there are good solutions that guess the right answer nearly all of the time based on the Fourier transform and its family.

Almost every question you'd like to ask about a digital audio recording is made easier by transforming the recording using a discrete version of the Fourier transform.

In practice,

*every*modern digital audio device relies heavily on functions very similar to the Fourier transform.Again, forgive the highly informal description; this is merely my personal intuition as to

*why*the Fourier transform is important.Hey John, I have a silly question. I want to calculate the TWA (https://www.osha.gov/pls/oshaweb/owadisp.show_document?p_table=STANDARDS&;p_id=9736) from the sound we recorded in a workplace, I wonder if I could measure this value more precisely if I employ Fourier Transformation in analyzing my audio file.

Not unless the microphone and the recording environment were calibrated, no.

The other people have given great, useful answers. Just think about some signal: you only care what frequencies are in it (and their phase), not about the time domain.

**I do not know that this is a final or complete answer, but just another reason why the Fourier transform is useful.**When you have some signal, it could be composed of an infinite (or close to) number of frequencies, depending on your sampling rate. But, that's not the case: we know that most signals have the fewest number of frequencies possible, or that we're sampling at a high enough rate.

If we know that, why can't we use it? That's what the field of compressed sensing does. They know that the most likely signal is one that has the least error and has the fewest frequencies. So, they minimize the overall error relative to our measurements as well as the magnitude of the Fourier transform.

A signal of a few frequencies often has a minimal Fourier transform, or mostly zeros (aka "sparse," as they say in compressed sensing). A signal of one frequency just has a delta function as the transform, for example.

We can use the formal mathematical definition too.

$\bar{x} = \textrm{arg min } ||y-Ax|| + \lambda||F(x)||$

Here, all we're doing is minimizing the error (first set of $||\cdot||$) and minimizing the Fourier transform (second set of $||\cdot||$). Here, we have

- $\bar{x}$ as our reconstructed signal (most likely close to the original)
- $y$, our measurements
- $A$, a selection matrix
- $x$, our signal
- $\lambda$ some constant
- $F(x)$ the Fourier transform.

You may recall that Nyquist said that you have to measure at twice the highest frequency to get a good representation. Well, that was assuming you had infinite frequencies in your signal. We can get past that!

The field of compressed sensing can reconstruct any signal that's mostly zeros (or sparse) in some domain. Well, that's the case for the Fourier transform.

The main importance of the Fourier transform lies with system analysis. The main constituent of our universe is vacuum, and vacuum is a fundamentally linear and time-invariant carrier of fields: different fields superimpose by adding their respective vectors, and regardless of when you repeat the application of certain fields, the outcome will be the same.

As a consequence, a lot of systems also involving physical matter are to a good approximation behaving as linear, time-invariant systems.

Such LTI systems can be described by their "impulse response", and the response to any time-distributed signal is described by convolving the signal with the impulse response.

Convolution is a commutative and associative operation, but it is also quite computationally and conceptually expensive. However, the convolution of functions is mapped by Fourier transform into piecewise multiplication.

That means that the properties of linear time invariant systems and their combinations are much better described and manipulated after Fourier transformation.

As a result, things like "frequency response" are quite characteristic for describing the behavior of a lot of systems and become useful for characterizing them.

Fast Fourier transforms are in the "almost, but not quite, entirely unlike Fourier transforms" class as their results are not really sensibly interpretable as Fourier transforms though firmly routed in their theory. They correspond to Fourier transforms completely only when talking about a sampled signal with the periodicity of the transform interval. In particular the "periodicity" criterion is almost always not met.

There are several techniques for working around that, like the use of overlapping windowing functions.

However the FFT

*can*be employed for doing discrete-time convolution when doing things right, and is it is an efficient algorithm, that makes it useful for a lot of things.One can employ the basic FFT algorithm also for number theoretic transforms (which work in discrete number fields rather than complex "reals") in order to do fast convolution, like when multiplying humongous numbers or polynomials. In this case, the "frequency domain" is indistinguishable from white noise for basically any input and has no useful interpretation before you do the inverse transform again.

the physics relevance of fourier transform is that it tells the relative amplitude of frequencies present in the signal . it can be defined for both discrete time and continuous time signal. Any signal can be represented as mixture of many harmonic frequencies. Fourier transform help in filter applications , where we need only certain range of frequencies then we first need to know what are the amplitudes of frequencies contains in the signal.

License under CC-BY-SA with attribution

Content dated before 6/26/2020 9:53 AM

Dilip Sarwate 9 years ago

Recently a discussion about Fourier transforms was revived on math.SE, and I thought that people on this site might find some of it worthwhile, and might even want to participate.