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

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?

• Maybe the DFT isn't the right approach? You might be able to apply the method of stationary phase to obtain values at each time point that are accurate to several digits, depending on the value of $C$. – smh Jan 7 '19 at 16:15

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).
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.