Fourier Transform And Fourier Series

Continuous Variable

Given a function on interval , define its Fourier coefficients by

where since is viewed as a periodic function with period 1. The inverse formula, that is, expansion of by some periodic function , is

Practically, the domain of usually is not , we defined Fourier coefficients as

in the case of . The definition above is equivalent use previous definition to function . Similarly, the inverse formula turns out to be

One of the most common case is put function on circle by setting , and we have

and

If is defined on whole instead of bounded interval, we should not use series but integration because we can’t regard as part of some periodic function, i.e. the variable is no longer restricted in . We have Fourier transform in this case:

where . Respectively, inverse Fourier transform is defined by

However, there is a way to view Fourier transform as a limit version of Fourier series if is a continuous function support on some bounded interval . First we have its Fourier series

by restrict ourselves on where , is n-th Fourier coefficient. Note

since has bounded support. Now we have

where is Fourier transform (on ) of . If we denote as , then . It can be proved that

if is continuous and moderate decrease. Apply this fact to we get

as . In the end, we conclude that

Discrete Variable

Many famous algorithms concern about Fourier transform, unfortunately computer cannot deal with continuous variable, so we have to use discrete version of Fourier transform in numerical computing.
There is a trick to turn those formulas of continuous variable to discrete version directly. We change the measure used in integration from usual Lebesgue measure to counting measure.
Given a set of points , set of all subset of is denote as which is called power set of , let , define counting measure on is a function

where is the number of points in both and . is a measurable space.
If is a set of some point in , then the discrete Fourier transform of on is defined by

Mostly are equalized points on , defaultly, in this case we have

which is called discrete Fourier transform (DFT) of . Due to , , that is, is a periodic function with period , i.e. domain of become . Now we can derive from above formula:

And this is the inverse formula we need.
If is sampled from interval instead of , we need a normalization before doing DFT. Let , defined on , define DFT of on is

note the flexible invariance is NOT hold in general. As a consequence, we have

and

when .
In most software (such as MATLAB), is set to be , that is, . In this case DFT and inverse DFT are

and

respectively. (Remark: the factor is changed into inverse DFT instead of DFT:

in MATLAB fft and ifft commend.)
There is an extremely effective algorithm to compute DFT called fast Fourier transform (FFT), which is one of the most useful and important algorithm. In each step, FFT uses all previous information instead of only using values computed in last previous step. By using this idea, FFT could do DFT on points by only operations (direct algorithm need operations).
In the end, we consider a special case: is discrete but unbounded, for example . The unbounded properity of leads to the value of varible turn to continuous, and the Fourier transform on is

where and counting measure is no longer a finite measure (but semi-finite). We can also write this formula in series form:

Note in this case, the above integration and series may divergent, there usually are some restriction need to satisfy for convergence of these formulas. The inverse Fourier transform is

Similarily, the Fourier and inverse Fourier transform on is defined by

and

where .
In fact, there is another intersting way to get Fourier transform when is discrete which is based on a view of numerical anaylsis. For example, let’s consider : in continuous case () we have

now use value of on to approx this integration by trapezoidal rule

if this integration converges. The significant part of last line in the formula is exactly the Fourier transform we have defined before.