Fourier transform for dummies [closed]

Question

So ... what is the Fourier transform? What does it do? Why is it useful (both in math and in engineering, physics, etc)?

(Answers at any level of sophistication are welcome.)

Answer 1

One of the main uses of Fourier transforms is to diagonalize convolutions. In fact, many of the most useful properties of the Fourier transform can be summarized in the sentence "the Fourier transform is a unitary change of basis for functions (or distributions) that diagonalizes all convolution operators." I've been ambiguous about the domain of the functions and the inner product. The domain is an abelian group, and the inner product is the L² inner product with respect to Haar measure. (There are more general definitions of the Fourier transform, but I won't attempt to deal with those.)

I think a good way to motivate the definition of convolution (and thus eventually of the Fourier transform) starts with probability theory. Let's say we have an abelian group (G, +, -, 0) and two independent random variables X and Y that take values in G, and we are interested in the value of X + Y. For simplicity, let's assume G = {x₁, ..., x_n} is finite. For example, X and Y could be (possibly biased) six-sided dice, which we can roll to get two independent elements of Z/6Z. The sum of the die rolls mod 6 gives another element of the group.

For x ∈ G, let f(x) be the probability P(X = x), and let g(x) = P(Y = x). What we care about is h(x) := P(X + Y = x). We can compute this as a sum of joint probabilities:

h(x) = P(X + Y = x) = Σ_y+z=xP(X = y & Y = z)

However, since X and Y are independent, P(X = y & Y = z) = P(X = y)P(Y = z) = f(y)g(z), so the sum is actually

h(x) = Σ_y+z=xf(y)g(z) = Σ_y∈Gf(y)g(x-y).

This is called the convolution of f and g and denoted by f*g. In words, the convolution of two probability distributions is the probability distribution of the sum of two independent random variables having those respective distributions. From that, one can deduce easily that convolution satisfies nice properties: commutativity, associativity, and the existence of an identity. Moreover, convolution has the same relationship to addition and scalar multiplication as pointwise multiplication does (namely, bilinearity). In the finite setting, there's also an obvious L² inner product on distributions, with respect to which, for each f, the transformation g -> f * g is normal. Since such transformations also commute, recalling a big theorem from finite-dimensional linear algebra, we know there's an orthonormal basis with respect to which all of them are diagonal. It's not difficult to deduce then that in such a basis, convolution must be represented by coordinatewise multiplication. That basis is the Fourier basis, and the process of obtaining the coordinates in the Fourier basis from coordinates in the standard basis (the values f(x) for x ∈ G) is the Fourier transform. Since both bases are orthonormal, that transformation is unitary.

If G is infinite, then much of the above has to be modified, but a lot of it still works. (Most importantly, for now, the intuition works.) For example, if G = Rⁿ, then the sum Σ_y∈Gf(y)g(x-y) must be replaced by the integral ∫_y∈Gf(y)g(x-y)dy to define convolution, or even more generally, by Haar integration over G. The Fourier "basis" still has the important property of representing convolution by "coordinatewise" (or pointwise) multiplication and therefore of diagonalizing all convolution operators.

The fact that the Fourier transform diagonalizes convolutions has more implications than may appear at first. Sometimes, as above, the operation of convolution is itself of interest, but sometimes one of the arguments (say f) is fixed, and we want to study the transformation T(g) := f*g as a linear transformation of g. A lot of common operators fall into this category. For example:

• Translation: T(g)(x) = g(x-a) for some fixed a. This is convolution with a "unit mass" at a.
• Differentiation: T(g)(x) = g'(x). This is convolution with the derivative of a negative unit mass at 0.
• Indefinite integration (say on R): T(g)(x) = ∫^x_-infinityg(t)dt. This is convolution with the Heaviside step function.

In the Fourier basis, all of those are therefore represented by pointwise multiplication by an appropriate function (namely the Fourier transform of the respective convolution kernel). That makes Fourier analysis very useful, for example, in studying differential operators.

Answer 2

Wikipedia article - very long, has explicit formulas, graphics, applications, etc.

A Fourier transform is a map from a space of functions on a (locally compact topological) abelian group A to functions on the Pontryagin dual group A' = Hom(A, U(1)), also a locally compact topological abelian group. If the chosen space of functions is good, like L^2 or smooth with rapid decay, then the map is an isomorphism. It is defined by integration against a canonical exponential kernel. When A = R, then so is A', and the a function f(t) is taken to a function F(s), defined as the integral of f(t)e^(-2i pi st) dt.

Here is an application in signal processing: Say you have a quantity that varies in time, like the ambient air pressure at some location (describing a sound wave). This is expressed as a function f(t), and taking the Fourier transform (A = time, A' = frequency), F(s) describes the decomposition into frequency components. If f(t) = sin(2 pi t), then it is a combination of pure exponentials with frequencies -1 and +1, and the Fourier transform is a sum of delta functions supported at -1 and 1. F isn't smooth, because f did not have rapid decay at infinity, so I'm implicitly using an extension of the transform to a larger space, like tempered distributions. Alternatively, if you're only working with periodic input, you can quotient the time domain A to a circle R/Z, and the frequency domain A' becomes a copy of the integers. In this case, the Fourier transform of sin(2 pi t) is a function supported at -1 and 1 with values i/2 and -i/2, respectively.

When A is finite, you get a discrete Fourier transform, which is amenable to computation because of the existence of fast algorithms (fft). One example of its use is in JPEG image compression, decomposing image data into a sum of waves (which actually uses cosines instead of exponentials). You can also multiply large integers quickly by pretending the sequence of digits is a signal. Multiplication is the same as convolving the signals, and it amounts to pointwise multiplication on the Fourier transforms.

I'm not really prepared to discuss the mathematical uses - it's big in harmonic analysis, but I only really see the part that touches number theory, like in Tate's thesis and automorphic forms in general.

Answer 3

I basically agree with the other answers so far, but here's the answer in a nutshell: The Fourier transform (and also Fourier series) writes a function as a superposition of functions of the form exp(iax). These exponential functions are eigenvectors both for translation and differentiation operators. It is because these operators are so natural and ubiquitous that one often wants to work in a "basis" adapted to them.

Answer 4

A representation of an arbitrary sheaf from derived category of sheaves on a stack G/G (action by conjugacy) in terms of "dual" basis. Abelian case — Fourier-Mukai transform for abelian varieties which relates sheaves on A with sheaves on A^v using the correspondence A\times A^v.

(there's some important property of Fourier missing above — I'll return to this tomorrow). It's something about relationship between G/G and G^\wedge/G^\wedge.

After passing to functions, you may think about the resulting version as rewriting an arbitrary conjugate-invariant function as a sum by characters. That specializes to abelian case — where all functions are conjugate-invariant.

As an example, for the real line you have to present f(x) as an integral of e^{2\lambda ix} (well, L^2, i and the appearance of integral are some important technical details because of non-compactness). The correspondence after all becomes integration with the kernel K(x, \lambda) = e^{2\lambda ix}.

Answer 5

In algebraic geometry, there is a Deligne-Fourier transform, from the bounded derived category of $\ell$-adic sheaves on the affine line over a finite field, say $\mathbb F_q,$ to itself. This operation depends on the choice of an additive character of $\mathbb F_q$ (into $\bar{\mathbb Q}\_{\ell}^*$), and it is an important technique in Laumon's simplified proof for Weil II. Under the sheaf-function correspondence this Fourier transform gives the classical Fourier transform for $\mathbb F_q.$

For instance, if $\chi$ is a multiplicative complex-valued character of $\mathbb F_q,$ then its Fourier transform is known as the Gauss sum. While $\chi$ takes values in roots of unity, which have absolute value 1 and hence weight 0, its Gauss sum takes values in weight 1 numbers.

Answer 6

As well as all the abstract reasons above, one of the reasons the discrete Fourier transform is so widely used in signal and image analysis is the existence of Fast Fourier Transforms (of which there are many versions), all of which compute the FT very speedily. This means that for convolution of large signals or images with large filters, it is much more efficient to use the FFT and the convolution theorem than a direct convolution. You may like to look at Fastest Fourier Transform in the West, which is the library used by Matlab.

Answer 7

Nobody seems to have said anything about Physics.

It underlies the Heisenberg uncertainty principle in quantum mechanics, which can be paraphrased as the fact that a function and its Fourier transform cannot both have compact support.

Answer 8

When you say "for dummies", this one is a very intuitive and step-by-step explanation: http://techhouse.brown.edu/~dmorris/projects/tutorials/fourier_tutorial.pdf

Answer 9

The electrical engineering answer goes something like this...

It converts your time domain to frequency domain.

It's quite good for cleaning up signals by removing certain parts of the signal, usually the very high frequency aspects, though you have to do so in very careful ways, b/c if you're not careful you'll remove a lot of good information.

Oh, it also allows you to pull out some interesting information very easily, like

it's linear you can pull out translations by a constant like F(f(x + x_0)) = CF(f(x)) (where c is power of e, it's specific but kind of messy) you can pull out dilations as

F(f(ax)) = 1/|a|F(f(x/a))

Answer 10

In mathematical physics many differential equations may be transformed by FT and gives some relations which may be solved algebraically. It is specially useful for analysing periodic structures and propagations of charges within it, for wave equation and many many others.

Also in Quantum Field Theory in path integral formulation formal power series approximation is easier in momentum space than in coordinate space, and relation between them is by FT.