16
$\begingroup$

In mathematics you can take the double derivative, or double integral of a function. There are many cases where performing a double derivative models a practical real-world situation, like finding the acceleration of an object.

Since the Fourier transform takes a real or complex signal as an input, and produces a complex signal as an output, there is nothing stopping you from taking that output and applying the Fourier transform a second time... Are there any practical uses for doing this? Does it help to model some complex real-world situations?

With the same logic, nothing would stop you from taking the inverse Fourier transform of your original time-domain input signal... would this ever be useful? Why or why not?

Improve this question
$\endgroup$

6 Answers 6

Reset to default
16
$\begingroup$

"Is there any practical application?" Definitely yes, at least to check code, and bound errors. Especially for huge data or a large number of iterations

"In theory, theory and practice match. In practice, they don't." So, mathematically, no, as answered by Matt. Because (as already answered), $\mathcal{F}\left(\mathcal{F}\left(x(t)\right)\right)=x(-t)$ (up to a potential scaling factor). However, it can be useful computationally, because the above equation is usually implemented via the discrete Fourier transform, and its fast avatar, the FFT.

A first reason arises from the will to check that the Fourier implementation, whether coded by you, somebody else or from a library, does what it should do on your data. Sample ordering, scaling factors, limits on input type (realness, bit-depth) or length are sources of potential subsequent errors for Fourier implementations like the FFT. So as a sanity check, it is always good to check that the implemented versions inherit, at least approximately, the theoretical properties. As you will see, as shown by Machupicchu, you don't recover exactly a real input reversed: often, the imaginary part is not exactly zero, and real part is what expected, but within a small relative error, due to imperfect computer calculations (floating point) within a machine-dependent tolerance. This is made visible on the following picture. The FFT is applied twice on a random 32-sample signal, and flipped. As you can see, the error is small, using double precision floats.

data, its double flipped FFT and error

If the error is not relatively small, then there might be mistakes in the code you use.

A second relates to huge data volumes or large quantities of iterated FFT computations, like with tomography. There, the previous small relative errors can accumulate and propagate, and even induce computational divergence or errors some details here. This is made visible on the following picture. For a not so long signal $x_0$ ($10^6$ samples), we perform the following iterations: $$x_{k+1} = \mathrm{Re}\left(\mathcal{f}\left(\mathcal{f}\left(\mathcal{f}\left(\mathcal{f}\left(x_{k}\right)\right)\right)\right)\right)$$ where $f$ denotes the FFT. The displayed figure is subsampled. And we compute the maximum error $\max |x_{k}-x_{0}|$ at each iteration.

data, its four-fold FFT and maximum errors over iterations

As you can see, the order of magnitude of the error has changed, due the size of the signal. Plus, the maximum error steadily increases. After $1000$ iterations it remains small enough. But you can guess that, with a $1000 \times 1000 \times 1000 $-voxel cube, and millions of iterations, this error may become non negligible.

Bounding the error, and evaluating its behavior over iterations may help detect such behaviors, and reducing then by appropriate thresholding or rounding.

Additional information:

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I really do love this answer and I would have marked it as the accepted answer but I think that what most people who come to this question will be looking for is the theoretical information that Matt provided in the link. +1 though for a great answer. $\endgroup$
    – tjwrona1992
    Aug 24, 2019 at 3:20
  • 1
    $\begingroup$ I really do appreciate your comment. I however have updated the answer with appropriate figures, to show that errors in discrete Fourier implementations matter. $\endgroup$
    – Laurent Duval
    Aug 24, 2019 at 22:05
22
$\begingroup$

No, taking the Fourier transform twice is equivalent to time inversion (or inversion of whatever dimension you're in). You just get $x(-t)$ times a constant which depends on the type of scaling you use for the Fourier transform.

The inverse Fourier transform applied to a time domain signal just gives the spectrum with frequency inversion. Have a look at this answer for more details.

Improve this answer
$\endgroup$
7
  • 5
    $\begingroup$ You just recursively blew my mind. $\endgroup$
    – tjwrona1992
    Aug 21, 2019 at 14:12
  • $\begingroup$ Do I illustrate what Matt. L said but in 2D with my code? i.e. we get f(-x,-y). $\endgroup$
    – SheppLogan
    Aug 21, 2019 at 14:25
  • $\begingroup$ @Machupicchu, yes that looks right. $\endgroup$
    – tjwrona1992
    Aug 21, 2019 at 14:52
  • $\begingroup$ haha then you can select my answer ad the top one ^^ (he has 53K rep so it doe not mak any diff for him haha) $\endgroup$
    – SheppLogan
    Aug 21, 2019 at 14:53
  • $\begingroup$ Right after I said that I realized that there's probably easier ways than a double Fourier transform to time invert a signal haha $\endgroup$
    – tjwrona1992
    Aug 21, 2019 at 14:54
17
$\begingroup$

Whilst taking the Fourier transform directly twice in a row just gives you a trivial time-inversion that would be much cheaper to implement without FT, there is useful stuff that can be done by taking a Fourier transform, applying some other operation, and then again Fourier transforming the result of that. The best-known example is the autocorrelation, which is a kind of convolution of a signal with itself. And convolutions are O(n2) if implemented naïvely, but only O(n·log n) when taking a detour via Fourier transform. So autocorrelation is generally done by FT'ing a signal, taking the absolute-square, and IFT-ing that back into time domain.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ Also, there is cepstrum, the inverse Fourier transform of the logarithm of the Fourier transform. It can be used to detect periodic signals. $\endgroup$
    – Olli Niemitalo
    Aug 25, 2019 at 6:56
12
$\begingroup$

2D Fourier transform (2D DFT) is used in image processing since an image can be seen as a 2D signal. E.g. for a grayscale image $I$, $I(x,y)=z$, that means that at the coordinates $x$ and $y$ the image has intensity value z. Look at this for example:

https://ch.mathworks.com/help/matlab/ref/fft2.html

Try this:

x=imread('cameraman.tif');
X=fft2(fft2(x));
imagesc(abs(X));

and compare to :

x=imread('cameraman.tif');
X= ifft2(fft2(x));
imagesc(abs(X));

rather like that. I applied fft2 to times, not ifft2 the second time. I think this illustrates what @Matt L. said:

"taking the Fourier transform twice is equivalent to time inversion",

you can see the image is inverted because of the of the -i imaginary negative instead of positive in ifft().

enter image description here

I also did it for a 1D signal (e.g. temporal):

enter image description here

Improve this answer
$\endgroup$
11
  • $\begingroup$ I'm aware there is such a thing as a 2D Fourier transform, but that isn't the same as taking an input signal and running it through the algorithm then taking the output of that run and running it through again. $\endgroup$
    – tjwrona1992
    Aug 21, 2019 at 14:08
  • 1
    $\begingroup$ The Fourier transform is separable. $\endgroup$
    – SheppLogan
    Aug 21, 2019 at 14:09
  • $\begingroup$ My question would also apply for a 2D Fourier transform. You could in theory take a 2D input signal, apply the 2D Fourier transform, then take the 2D output signal and use it as an input and apply the 2D Fourier transform again. $\endgroup$
    – tjwrona1992
    Aug 21, 2019 at 14:09
  • $\begingroup$ look in Matlab what happends if you do the following: cf. I updated my answer $\endgroup$
    – SheppLogan
    Aug 21, 2019 at 14:10
  • 1
    $\begingroup$ I would suggest you to use the real part instead of the absolute value $\endgroup$
    – Laurent Duval
    Aug 21, 2019 at 21:43
6
$\begingroup$

To answer the second question, in digital communications there is a technique in use in cellphones right now that makes good use of applying the IFFT to a time-domain signal. OFDM applies an IFFT to a time-domain sequence of data at the transmitter, then reverses that with an FFT at the receiver. While the literature likes to use IFFT->FFT, it really makes no difference which one comes first.

diagram of OFDM transmitter

The key benefit here is heavily related to leftaroundabout's answer. There is a type of distortion that called multipath fading, and cellphones in dense urban areas have to deal with a lot of it. We like to model multipath fading as a convolution with unknown coefficients. Because the chain of events looks something like IFFT->Transmit->Apply multipath->Receive->FFT, the multipath fading will go through the FFT and become a simple point-by-point multiplication with unknown values. These values are a lot easier to predict and rectify than the convolution coefficients.

This effect also makes a signal more resilient to multipath /fading that could take out (or "null") an entire frequency channel. This article describes how

Such multipath propagation can create deep spectral nulls in the frequency passband of received radio signals due to the destructive interference of two copies of the signal arriving at slightly different times. A null in OFDM can take out one or more subcarriers. The same null in single-carrier QAM might drop a burst of sequentially adjacent symbols, depending on the specific data pattern at that instant. In extreme cases, loss of signal acquisition is even possible. It then gets down to the power of the FEC to recover the original data sequence.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Wow this is incredibly interesting! Thanks! :) $\endgroup$
    – tjwrona1992
    Aug 23, 2019 at 1:39
1
$\begingroup$

This information was provided by the user "Birdwes", but he didn't have enough reputation to post it himself so I will post it here for him because it does seem relevant and useful.

"I do not have enough points in this forum to add a comment, so I'm doing it here: take a look at the source code for Accord.Math Hilbert Transform and you will see why this can be a viable option: https://github.com/primaryobjects/Accord.NET/blob/master/Sources/Accord.Math/Transforms/HilbertTransform.cs

Practical uses include building SSB transmitters, or almost any modulation plan. Look up IQ modulation and you will see why the phase shift of -90 degrees is relevant. A product of trigonometric principles. e.g. https://user.eng.umd.edu/~tretter/commlab/c6713slides/ch7.pdf

The Hilbert Transform uses a middle step between the FFTs of zeroing out negative components. You can abuse it to filter out other frequencies too."

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.