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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ The Fourier transform is linear - the error in Fourier domain should thus be the Fourier transform of the error in x domain. $\endgroup$– AlexECommented Jan 25, 2018 at 5:41
-
3$\begingroup$ 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. $\endgroup$– AlexECommented Jan 25, 2018 at 22:11
-
$\begingroup$ @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. $\endgroup$– Anton Menshov ♦Commented May 19, 2019 at 6:31
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
3
Assembled from comments of @AlexE:
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.
-
7$\begingroup$ 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. $\endgroup$ Commented Jun 11, 2019 at 19:42
-
$\begingroup$ @rchilton1980 I agree. I would be happy for a reference with some rigorous analysis that I can read without diving into deep derivations. $\endgroup$– Anton Menshov ♦Commented Jun 12, 2019 at 21:22
-
2$\begingroup$ The important point is that the Fourier transform is unitary, not just linear. $\endgroup$ Commented Jul 7, 2023 at 23:18
$\begingroup$
$\endgroup$
2
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.
-
2$\begingroup$ But most importantly, the Fourier transform matrix $X$ is unitary (with a 1/n scaling), so that $X^{T}X=nI$! This is a version of Parseval's theorem for the discrete Fourier transform. $\endgroup$ Commented Apr 28 at 19:54
-
$\begingroup$ @BrianBorchers Yes, it's unitary when the sampling interval is constant (i.e. the data is regularly spaced ) $\endgroup$ Commented Sep 9 at 16:56
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
This has been derived in G. Betta, C. Liguori, and A. Pietrosanto "Propagation of uncertainty in a discrete Fourier transform algorithm, " Measurement, vol. 27, no. 4, pp. 231-239, Jun. 2000. Full-text seems to be available via ResearchGate.
Both the uncertainty in magnitude and phase are provided there assuming a number of noise sources. Specifically, for some additive input noise and data length $N$, the uncertainty in magnitude at a given frequency is:
$$\sigma_M^2 = 2\sigma_i^2 /N$$
