Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Unified Theory of Fourier Transforms

DZone's Guide to

Unified Theory of Fourier Transforms

Dive into how the unified theory of Fourier transforms unifies a bunch of related but different components of artificial intelligence.

· AI Zone
Free Resource

Find out how AI-Fueled APIs from Neura can make interesting products more exciting and engaging. 

You can either take a periodic function and analyze it into its Fourier coefficients or use the Fourier coefficients in a sum to synthesize a periodic function. You can take the Fourier transform of a function defined on the whole real line and get another such function. And you can compute the discrete Fourier transform via the FFT algorithm.

Is there a general theory that unifies all these related but different things? Why yes, yes there is.

Groups

Everything in the opening paragraph is simply a Fourier transform, each in a different context. And the contexts correspond to groups — specifically, locally compact Abelian groups.

Some of these groups are easier to see than others. Clearly, the real numbers with addition form a group: the sum of two real numbers is a real number, etc. But where are the groups in the other contexts?

You can think of a periodic function as a function on a circle. The function values have to agree at both ends of an interval, so you might as well think of those two points as the same point, i.e. join them to make a circle. Shifting along an interval, wrapping around if necessary, corresponds to a rotation of the circle, and rotations form a group. So analyzing a periodic function into a set of Fourier coefficients is a Fourier transform on the circle.

You can think of a set of Fourier coefficients as a function on the integers, mapping n to the nth coefficient. Synthesizing a set of Fourier coefficients into a periodic function is a Fourier transform on the group of integers.

What about a discrete Fourier transform (DFT)? If you have a function sampled at m points, you could think of those points as the group of integers mod m. Your sampled points constitute a function on the integers mod m, and the DFT is a Fourier transform on that group.

Note that the DFT is a Fourier transform in its own right. It's not an approximation per se, though it's nearly always used as part of an approximation process. You can start with a continuous function, approximate it by a finite set of samples, and compute the DFT of these samples, and the result will give you an approximation to the Fourier transform of the original continuous function.

What about functions of several variables? These are functions on groups, too. A function of two real variables, for example, is a function on R², which is a group with (vector) addition.

Dual Groups

A Fourier transform takes a function defined on a group and returns a function defined on the dual of that group. I go into exactly what a dual group is in my next post, but for now, just note that the Fourier transform takes a function defined on one group and returns a function defined on another group.

The dual of the circle is the integers and vice versa. That's why the Fourier transform of a function on the circle is an infinite set of Fourier coefficients, which we think of as a function on the integers. The Fourier transform of the function on the integers, i.e. a set of Fourier coefficients, is a function on the circle, i.e. a periodic function.

The dual group of the real numbers is the real numbers again. That's why the Fourier transform of a function on the real line is another function on the real line.

The integers mod m is also its own dual group. So the DFT takes a set of m numbers and returns a set of m numbers.

Locally Compact Abelian (LCA) Groups

What do "locally compact" and "Abelian" mean? And why do we make these assumptions?

Let's start with Abelian. This just means that the group operation is commutative. When we're adding real numbers or composing rotations of a circle, these operations are commutative.

Locally, compactness is a more technical requirement. The circle is compact, and so are the integers mod m. But if we restricted our attention to compact groups, that would leave out the integers and the real numbers. These spaces are not compact, but they're locally compact, and that's enough for the theory to go through.

It turns out that LCA groups are a sort of theoretical sweet spot. Assuming groups are LCA is generally enough to include the examples we care about the most, but it's not so general that the theory becomes harder and the results less powerful.

More Connections

This post relates Fourier series (analysis and synthesis) to Fourier transforms (on the real line) by saying they're both special cases of Fourier analysis on LCA groups. There are a couple other ways to connect Fourier series and Fourier transforms.

You can take the Fourier transform (not Fourier series) of a periodic function two ways: by restricting it to one period and defining it to be zero everywhere else or by letting it repeat forever across the real line and taking the Fourier transform in the sense of generalized functions. You can read more about these two approaches in this post.

To find out how AI-Fueled APIs can increase engagement and retention, download Six Ways to Boost Engagement for Your IoT Device or App with AI today.

Topics:
fourier analysis ,ai ,tutorial ,algorithms

Published at DZone with permission of John Cook, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}