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.
Does there exist a Fourier transform algorithm for perturbed data?
linear algebra;fourier analysis