Fourier
Details and Options
- The discrete Fourier transform vs of a list ur of length n is by default defined to be
ure2π i(r-1)(s-1)/n. » - Note that the zero frequency term appears at position 1 in the resulting list.
- Other definitions are used in some scientific and technical fields.
- Different choices of definitions can be specified using the option FourierParameters.
- With the setting FourierParameters->{a,b}, the discrete Fourier transform computed by Fourier is
ure2π i b(r-1)(s-1)/n. » - Some common choices for {a,b} are {0,1} (default), {-1,1} (data analysis), {1,-1} (signal processing).
- The setting
effectively corresponds to conjugating both input and output lists. - To ensure a unique inverse discrete Fourier transform, b must be relatively prime to n. »
- The list of data supplied to Fourier need not have a length equal to a power of two.
- The list given in Fourier[list] can be nested to represent an array of data in any number of dimensions.
- The array of data must be rectangular.
- If the elements of list are exact numbers, Fourier begins by applying N to them.
- Fourier[list,{p1,p2,…}] is typically equivalent to Extract[Fourier[list],{p1,p2,…}]. Cases with just a few positions p are computed using an algorithm that takes less time and memory but is more subject to numerical error, particularly when the length of list is long.
- Fourier can be used on SparseArray objects.
Examples
open all close allBasic Examples (2)
Scope (3)
x = {1, 0, 0, 1, 0, 0, 1};Compute the Fourier transform with machine arithmetic:
Fourier[x]Compute using 24-digit precision arithmetic:
Fourier[N[x, 24]]Compute a 2D Fourier transform:
Fourier[RandomComplex[1 + I, {3, 6}]]x is a rank 3 tensor with nonzero diagonal:
x = ConstantArray[0, {2, 3, 4}];x[[1, 1, 1]] = 1;x[[2, 2, 2]] = 1;Compute the 3D Fourier transform:
Fourier[x]Options (2)
FourierParameters (2)
a = Fourier[{1, 0, 1, 0, 0, 1, 0, 0, 0, 1}, FourierParameters -> {1, 1}]
Fourier[{1, 0, 1, 0, 0, 1, 0, 0, 0, 1}]%Sqrt[10]
Fourier[{1, 0, 1, 0, 0, 1, 0, 0, 0, 1}, FourierParameters -> {-1, 1}]Data from a Sinc function with noise:
n = 100;
x = Table[Sinc[x - 10], {x, n}] + RandomReal[{-.05, .05}, {n}];ListPlot[x, PlotRange -> All]Ordinary spectrum without normalization:
s = Fourier[x, FourierParameters -> {1, 1}];p = Fourier[Take[x, 20], FourierParameters -> {1, 20 / n}];Show[ListPlot[Abs[s] ^ 2], ListPlot[Abs[p] ^ 2, PlotStyle -> Red]]Applications (10)
Computing Spectra (6)
Fourier spectrum of "white noise":
ListLinePlot[Abs[Fourier[RandomReal[1, 200]]] ^ 2]Show the logarithmic spectrum, including the first (DC) component:
ListLinePlot[Log[10, Abs[Fourier[RandomReal[1, 200]]] ^ 2], PlotRange -> All]The spectrum of a "pulse" is completely flat:
ListLinePlot[Abs[Fourier[Table[KroneckerDelta[i], {i, 0, 200}]]]]Power spectrum of the Thue–Morse nested sequence [more info]:
ListLinePlot[Abs[Fourier[Nest[Flatten[# /. {1 -> {1, 0}, 0 -> {0, 1}}]&, {1}, 7]]]]Power spectrum of the Fibonacci nested sequence [more info]:
ListLinePlot[Abs[Fourier[Nest[Flatten[# /. {1 -> {0}, 0 -> {1, 0}}]&, {0}, 10]]], PlotRange -> All]2D power spectrum of a nested pattern:
data = Table[Mod[Binomial[i, j], 2], {i, 0, 63}, {j, 0, 63}];ArrayPlot[data]Find the logarithmic power spectrum:
ArrayPlot[Log[Abs[Fourier[data]]]]Find the Fourier transform of the rule 30 cellular automaton pattern:
ArrayPlot[CellularAutomaton[30, {{1}, 0}, 50]]ArrayPlot[Log[Abs[Fourier[CellularAutomaton[30, {{1}, 0}, 50]]]]]Filtering Data (1)
Compute discrete cyclic convolutions to smooth a discontinuous function with a Gaussian:
n = 100;dx = 1. / (n - 1);
a = Table[UnitStep[x - 1 / 2], {x, 0, 1, dx}];
b = Table[If[x ≤ 1 / 2, Exp[-100x ^ 2], Exp[-100(1 - x) ^ 2]], {x, 0, 1, dx}];
b = b / Total[b];{ListPlot[a, Filling -> Axis, DataRange -> {0, 1}], ListPlot[b, Filling -> Axis, PlotRange -> All, DataRange -> {0, 1}]}Compute the cyclic convolution:
c = Chop[InverseFourier[Fourier[a] Fourier[b]]Sqrt[n]];Show the original and smoothed function:
ListPlot[{a, c}, DataRange -> {0, 1}]The convolution is consistent with ListConvolve:
Max[Abs[c - ListConvolve[a, b, {1, 1}]]]Frequency Identification (1)
Here is some periodic data with some noise:
n = 1000;
per = 12.34;
pdata = Table[Sin[2 π x / per], {x, n}] + RandomReal[.1, {n}];
ListPlot[pdata]Find the maximum modes in the spectrum:
f = Abs[Fourier[pdata]];
peaksize = Last[TakeLargest[f, 2]];
peaks = Flatten[Position[f, x_ /; x ≥ peaksize]]Get the position corresponding to positive frequencies and show the position on a plot of the spectrum:
pos = First[peaks];Show[ListPlot[f], Graphics[{Red, Point[{pos, f[[pos]]}]}], PlotRange -> All]Find a high-resolution spectrum between modes where the maximum was found:
fr = Abs[Fourier[pdata Exp[2 Pi I (pos - 2) N[Range[0, n - 1]] / n], FourierParameters -> {0, 2 / n}]];
frpos = Position[fr, Max[fr]][[1, 1]]Show[ListPlot[fr], Graphics[{Red, Point[{frpos, fr[[frpos]]}]}], PlotRange -> All]Determine the period from the frequencies:
N[n / (pos - 2 + 2 (frpos - 1) / n)]Computing Eigenvectors (1)
m is a circulant differentiation matrix:
n = 1000;
m = N[SparseArray[{{i_, i_} -> -2, {i_, j_} /; Abs[i - j] == 1 -> 1, {n, 1} -> 1, {1, n} -> 1}, {n, n}]]Because 
, the eigenvalues of m are:
d = Chop[Table[Block[{ω = 2. Pi I j / n}, (E^-ω + E^ω) - 2], {j, 0, n - 1}]];The eigenvectors are the columns of the DFT matrix, so Fourier diagonalizes m:
Max[Abs[m - Map[Fourier, ConjugateTranspose[Map[Fourier, DiagonalMatrix[d]]]]]]This allows very efficient computation of MatrixExp[m,r] for a particular vector:
r = N[n / 2 - Abs[n / 2 - Range[n]]];Max[Abs[Fourier[Exp[ d] InverseFourier[r]] - MatrixExp[m, r]]]Show the approximate evolution of the heat equation 
on the unit interval:
x = N[Range[n] / n];ListPlot[Table[Transpose[{x, Fourier[Exp[t d n ^ 2] InverseFourier[r]]}], {t, 0, 0.05, 0.01}], PlotRange -> All]Fractional Fourier Transform (1)
Define a fractional Fourier transform using different choices of FourierParameters:
data = Table[N[Sin[x + y]], {x, 100}, {y, 100}];Partition[Table[ArrayPlot[Abs[Fourier[data, FourierParameters -> {1, b}]], ColorFunction -> "Rainbow", ColorFunctionScaling -> False, Mesh -> False],
{b, {1, 1.6, 2.2, 2.8}}], 2]Properties & Relations (6)
InverseFourier inverts Fourier:
Fourier[{1, 0, 1, 0, 1, 0}]InverseFourier[%]For real inputs, all elements after the first come in complex conjugate pairs:
Fourier[{1, 2, 3, 4, 5, 6}]The power spectrum is symmetric:
Abs[Fourier[{1, 2, 3, 4, 5, 6}]] ^ 2Cyclic convolution corresponds to multiplication of Fourier transforms:
a = RandomReal[1, {1000}];
b = RandomReal[1, {1000}];c1 = InverseFourier[Fourier[a]Fourier[b]]Sqrt[1000];c2 = ListConvolve[a, b, {1, 1}];c1 - c2//NormFourier of a constant array is nonzero only at the zero-frequency component:
Fourier[{1, 1, 1, 1, 1, 1}]The power spectrum of a list of 
unit values has zero-frequency component 
and 0 elsewhere:
Abs[Fourier[{1, 1, 1, 1, 1, 1}]] ^ 2
u = N[{1, 2, 3, 4, 5, 6, 7}];
n = Length[u];v = Table[(1/Sqrt[``n``])Underoverscript[∑, r = 1, n]Indexed[u, {r}] E^(2 I π (r - 1) (s - 1)/n), {s, 1, n}]Chop[v - Fourier[u]]Fourier is equivalent to multiplication with FourierMatrix:
FourierMatrix[6]//MatrixFormv = FourierMatrix[6].N[{1, 2, 3, 4, 5, 6}]Chop[v - Fourier[{1, 2, 3, 4, 5, 6}]]The conjugate transpose of the matrix is equivalent to InverseFourier:
Chop[ConjugateTranspose[FourierMatrix[6]].N[{1, 2, 3, 4, 5, 6}] - InverseFourier[{1, 2, 3, 4, 5, 6}]]Possible Issues (4)
If 
is not relatively prime to 
, the transform may not be invertible:
m = Map[Fourier[#, FourierParameters -> {0, 2}]&, IdentityMatrix[8]];
MatrixRank[m]Lengths that are powers of 2 or factorizable into a product of small primes will be faster:
Timing[Fourier[RandomReal[1, 2 ^ 20 + 1]];]FactorInteger[2 ^ 20 + 1]Timing[Fourier[RandomReal[1, 2 ^ 20]];]Timing[Fourier[RandomReal[1, 2 ^ 20 - 1]];]FactorInteger[2 ^ 20 - 1]Fourier uses an efficient algorithm when only a small number of coefficients is needed:
data = RandomReal[1, 2 ^ 20 - 1];AbsoluteTiming[Fourier[data, {{1}, {3}, {5}}];]MaxMemoryUsed[]AbsoluteTiming[Extract[Fourier[data], {{1}, {3}, {5}}];]MaxMemoryUsed[]The fast and efficient implementation may result in significant numerical error:
bdata = RandomReal[1, 2 ^ 20, WorkingPrecision -> 50];data = N[bdata];pos = {{1}, {3}, {2 ^ 20 - 5}};
AbsoluteTiming[res = Extract[Fourier[bdata], pos]]AbsoluteTiming[Extract[Fourier[data], pos] - res]AbsoluteTiming[Fourier[data, pos] - res]Related Links
NKS|OnlineText
Wolfram Research (1988), Fourier, Wolfram Language function, https://reference.wolfram.com/language/ref/Fourier.html (updated 2012).
CMS
Wolfram Language. 1988. "Fourier." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2012. https://reference.wolfram.com/language/ref/Fourier.html.
APA
Wolfram Language. (1988). Fourier. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/Fourier.html