Fourier transforms
In a typical Fourier transform, one uses basic forms such as Exp[ π r x/n] with r running from 1 to n. The weights associated with these forms can be found using Fourier, and given these weights the original data can also be reconstructed using InverseFourier. The pictures below show what happens in such a so-called discrete cosine transform when different fractions of the weights are kept, and others are effectively set to zero. High-frequency wiggles associated with the so-called Gibbs phenomenon are typical near edges.
Fourier[data] can be thought of as multiplication by the n × n matrix Array[Exp[2π #1 #2/n] &, {n, n}, 0]. Applying BitReverseOrder to this matrix yields a matrix which has an essentially nested form, and for size n = 2s can be obtained from
Nest[With[{c = BitReverseOrder[Range[0, Length[#] - 1]/ Length[#]]}, Flatten2D[MapIndexed[#1 {{1, 1}, {1, -1} (-1)^c〚Last[#2]〛} &, #, {2}]]] &, {{1}}, s]
Using this structure, one obtains the so-called fast Fourier transform which operates in n Log[n] steps and is given by
With[{n = Length[data]}, Fold[Flatten[Map[With[{k = Length[#]/2}, {{1, 1}, {1, -1}} . {Take[#, k], Drop[#, k](-1)^(Range[0, k - 1]/k)}] &, Partition[##]]] &, BitReverseOrder[data], 2^Range[Log[2, n]]]/√n]
(See also page 1080.)