Assuming I have a length-$n$ real vector $x$ and have already computed its Fourier transform $\hat x$ (in time $O(n\log n)$), I would like to compute the Fourier transform of $y = x + \delta x$, where $\delta x$ is a small perturbation.

Does there exist a method for computing the Fourier transform of $y$ in less than $O(n\log n)$ time? Perhaps in linear time (e.g., asymptotically constant number of vector arithmetic operations)? In other words, is it possible to take advantage of knowing an "approximate" Fourier transform ($\hat x$) of the input data ($x+\delta x$)?

I have in mind the example where $x$ and $y$ are consecutive timesteps in solving a system of ODEs, where $|y-x|=O(\delta t)$ is small, but there might be other examples I don't know of.

  • 2
    $\begingroup$ The Discrete Fourier Transform is linear, so you could take any vector z, scale it down and compute the Fourier transform of $x+\epsilon z$ and then subtract the transform of $x$ and divide by $\epsilon$ to get the transform of $z$ in better than $O(n \log n)$ time. Would you be interested in methods that work for sparse vectors $z$? $\endgroup$ Feb 7 '16 at 20:35
  • $\begingroup$ @BrianBorchers Thanks for pointing that out. I was thinking that the better-than-$n\log n$ time would depend somehow on $\epsilon$ being small, so that if you try to divide $\hat y-\hat x$ by $\epsilon$ to get $\delta \hat x$, you'd get some error like $\mathit{tolerance}/\epsilon$ that would be large enough for this not to be equivalent to computing $\delta \hat x$ directly. As for sparsity, I want to ask specifically about "small" (in some sense) perturbations, rather than sparse, like in my ODE example. $\endgroup$
    – Kirill
    Feb 7 '16 at 20:47
  • 2
    $\begingroup$ What @BrianBorchers showed is that it can't be done if you're interested in the exact Fourier transform of $y$. But you could ask for an algorithm that computes an approximation of it, for example only updating the most affected modes of the Fourier series, or similar. $\endgroup$ Feb 8 '16 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.