# Error propagation through an FFT

If I take the Fourier transform of data $$x \pm \sigma$$, is there a standard approach to what the error in the outputs will be? Would the best way be a direct evaluation of the upper and lower bounds?

• The Fourier transform is linear - the error in Fourier domain should thus be the Fourier transform of the error in x domain. Jan 25, 2018 at 5:41
• If sigma is understood as a spread or variance instead of as a function of x, you can use the Fourier transform's uncertainty relation. Jan 25, 2018 at 22:11
• @AlexE would you consider converting your comment into an answer? also, you might want to mention this post where this is demonstrated on a particular example with some python code. May 19, 2019 at 6:31

The Fourier transform is linear, so the error in the Fourier domain is the Fourier transform of the error in the spatial (original) domain.

So, if $$\sigma$$ is understood as a variance spread not being a function of $$x$$, one can use the Fourier transform's uncertainty relation.

This StackOverflow post demonstrates this behaviour using Python code.

• I don't think that appealing just to linearity is enough, shouldn't the conditioning / condition number be mentioned here? That said, the Fourier transform is unitary (condition number of 1) so I don't disagree with the conclusion. Jun 11, 2019 at 19:42
• @rchilton1980 I agree. I would be happy for a reference with some rigorous analysis that I can read without diving into deep derivations. Jun 12, 2019 at 21:22
• The important point is that the Fourier transform is unitary, not just linear. Jul 7, 2023 at 23:18

In Higham's book there is throughout and easily understandable treatment of the error in the Cooley-Tuckey algorithm. Unluckily the matrix pproach proposed by mathew gunther leds to overestimates, since it does not take advantage of the divide and conquer strategy. Essentially, the error in the fft is small because we do few fl point operations

I've pondered this question before. The best I can come up with is as follows.

The Fourier transform y = fft(x) can be expressed as some matrix, $$X$$, dot producted with $$x$$.

See scipy documentation examples for how to generate the fourier Fourier matrix here

This matrix representation means that the Fourier transform can be thought of as a linear least squares problem. That is, the Fourier coefficients are the fit parameters. The problem of estimating the fit parameters' standard deviation has a known solution.

See the Wikipedia article here Unbiasedness and variance of $$\beta$$ for how to do so.

For the sake of completeness, the quantity one wishes to find is the standard deviation of the fit parameters, $$\sigma_\beta$$.

Using the wikipedia article above

$$\sigma_\beta^2 =E[(\hat{\beta}-\beta)(\hat{\beta}-\beta)] = \sigma \sigma^T (X^T X)^{-1}$$

Where $$X$$ is the fourier matrix.

Note that $$\sigma \sigma^T$$ is a covariance matrix, not a scalar. In your case, it will most likely be a diagonal matrix

EDIT: Unless the data is irregularly spaced, some frequency coefficients are known and fixed/truncated higher frequencies, or the original measurements have a confidence interval, then the residuals of the ft will always be zero. That means the coefficients uncertainty will also be zero.