DFT of $g(\omega) \exp(i C \omega^2)$. How to do it ,if uniform sampling requires too much memory?

Question

I have a following problem : I want to transform a function $g(\omega) \exp(i C \omega^2)$. $g(\omega)$ is real and limited. It changes slowly compered to $\exp(i C \omega^2)$. I have a black box that I can ask for the values of that function at any specific point in frequency domain. I want to get $g(\omega) \exp(i C \omega^2)$ representation in time domain. If I try to apply a uniform DFT then (if I understand DFT correctly) I have to sample my $g(\omega)$ with sampling frequency that correspond to the highest frequency of $\exp(i C \omega^2)$. And that would be $C \omega_{max}$ where $\omega_{max}$ is the largest $\omega$ for which $g(\omega)$ is non-zero.

Unfortunately doing it like that requires too much memory since $C$ is extremely large. I calculated that sampling would required $\approx 10^{14}$ points. I have no idea how to proceed. Would NUFFT-II be better then FFT?

Answer 1

Expanding upon my comment above, if you only need a few digits of accuracy you can probably use the method of stationary phase. We can follow the procedure on Wikipedia. We can write the transform as follows: $$ f(t) = \int_{-\infty}^{\infty} g(\omega)e^{i\phi(\omega,t)}d\omega, $$ where $\phi(\omega,t)=C\omega^2-\omega t$. The principal contribution of the integrand to the value of the integral comes in the vicinity of the stationary point of the phase function $\phi$, which can be found by solving $$ \frac{\partial\phi}{\partial\omega}=0 \rightarrow \omega_0=t/2C. $$ The Taylor series expansion of $\phi$ in the vicinity of the stationary point $\omega_0$ is given, to quadratic degree, by $$ \phi(\omega,t) \approx \frac{t^2}{4C} + C (\omega-\omega_0)^2. $$ Substituting this into the transform integral, we find $$ f(t) \approx \left|g\left(\frac{t}{2C}\right)\right| e^{it^2/4C} \int_{-\infty}^{\infty} e^{iC(\omega-\omega_0)^2}d\omega. $$ Substituting an approximation with an error term that goes as $\mathcal{O}(C^{-1})$ for the remaining highly-oscillatory integral, we find that $$ f(t) \approx \left|g\left(\frac{t}{2C}\right)\right| e^{i(t^2/4C+\pi/4)} \sqrt{\frac{\pi}{C}}. $$

Using $g(\omega)=e^{-\omega^2}$ and $C=10^{12}$, this approximation is accurate to 6 digits up to $t=1000$ (verified with Wolfram Alpha).

Answer 2

You could try the logarithmic Fourier transform. The idea is that if one desires the time values in a log-spaced fashion one also only needs the frequency values in a log-spaced fashion. Moreover, if one plugs these log spaced assumptions into the Fourier transform one obtains a convolution type relationship. Or in other words, in log spaced coordinates the Fourier transform becomes a convolution. This convolution is calculable with the normal Fourier transform, but typically needs much less datapoints. It could be of benefit for your problem as well, since there is the $\omega^2$ term. However due to the log-spacing some limitations apply, e.g. the $\omega=0$ and $t=0$ value can not be included.

A classical paper on the log-spaced Fourier transform can be found here. Since then it has been re-invented several times (and perhaps it is also not the first on this topic).