# 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. – AlexE Jan 25 '18 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. – AlexE Jan 25 '18 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. – Anton Menshov May 19 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. – rchilton1980 Jun 11 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. – Anton Menshov Jun 12 at 21:22

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 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 known solution.

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

For the sake of completeness, the quantity on 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