I originally posted this question on math stack exchange, but I think it may be better suited for this community.

I'm interested in functions $f: \mathbb{C} \rightarrow \mathbb{R}$ with associated Fourier decompositions $$ f(a + ib) = \int_{-\infty}^{\infty} F(\lambda) \ e^{i \lambda (a + ib)} \ d\lambda.$$

We can assume these functions are band-limited in that there exists some $\mu \in \mathbb{R}$ such that $F(\lambda)$ is finite for $\lambda \leq \lvert \mu \rvert$ and $F(\lambda) = 0$ for $\lambda > \lvert \mu \rvert$.

I'd like to be able to express the above integral (or its discretization as a sum) in such a way that would allow me to perform an FFT (or other fast integral transform), though this has escaped me thus far. From what I've read, it seems like a Fourier-Mellin transform would be a good candidate (or maybe a clever application of the residue theorem), however I haven't been able to find this case in the literature.

Is it possible to evaluate this integral in a numerically efficient manner, and if so, how would I do so?


Per the suggestions of Andy and Marcus, the problem I'd like to solve is really a discretized version of the above. Specifically, I have a discrete set of Fourier coefficients $$\{ {\bf F}_\lambda \}, \ \lambda \in \mathbb{Z}, \ -\frac{N}{2} \leq \lambda \leq \frac{N}{2}.$$ I know that these coefficients correspond to a function $f(z)$ defined on a sub-interval of the complex line such that $$ f(z) = \sum_{\lambda = -\frac{N}{2}}^{\frac{N}{2}} {\bf F}_{\lambda} \ e^{i \lambda z},$$ where $$ \Re(z) \in [0, \ 2\pi), \ \ \Im(z) \in \mathbb{R}.$$

My aim is to recover the values of $f$ on a discrete sampling of points in its domain.

One way to do this is as follows. Writing $z = a + ib$, the above sum can be written as $$ f(z) = \sum_{\lambda = -\frac{N}{2}}^{\frac{N}{2}} {\bf F}_n \ e^{i \lambda (a + ib)} = \sum_{\lambda = -\frac{N}{2}}^{\frac{N}{2}} \widetilde{\bf F}_{\lambda}(b) \ e^{i \lambda a},$$where $\widetilde{\bf F}_{\lambda}(b) = {\bf F}_{\lambda} \ e^{-\lambda b}.$ From here it's clear that for any $b \in \mathbb{R}$, we can recover the values of $f$ at the set of points $\left\{ \frac{\pi n}{N} + ib \in \mathbb{C} \ \vert \ 0 \leq n < 2N \right \}$, by running a 1D inverse FFT. Assuming we want to sample $b$ at $M$ discrete points, we’ll perform $M$ inverse FFTs, giving a total complexity of $O(MN \log N)$ in evaluating $f$ at the sample points.

I want to know if it's possible to do this more efficiently, though the odds seem long. In my application, almost anything would be fair game - assuming $f$ is periodic in $b$ on some finite sub-interval of $\mathbb{R}$, etc.

  • 1
    $\begingroup$ What is the path for $a+ib$, constant $b$ with varying $a$ (i.e. $t+ib$)? The reason I ask is that the FFT is going to return a whole range of values in the time domain. Do you really only anticipate computing a single output value? $\endgroup$ – Andy Walls Oct 13 '20 at 19:12
  • 1
    $\begingroup$ Just a thought:$$f(a + ib) = \int_{-\infty}^{\infty} F(\lambda) \ e^{i \lambda (a + ib)} \ d\lambda=\int_{-\infty}^{\infty} F(\lambda)e^{-\lambda b} \ e^{i \lambda a} \ d\lambda = \int_{-\infty}^{\infty} \tilde F(\lambda) \ e^{i \lambda a} \ d\lambda$$ You can transform this into a problem that can be approached with a Fourier table and the convolution property of the Fourier transfrom $\endgroup$ – Marcus Müller Oct 13 '20 at 23:31
  • $\begingroup$ @AndyWalls Thanks for your comment. I'm not sure what you mean by path. In my application, I'd like to recover a discretization of $f(a + ib)$ in the variables $a$ and $b$ - hence I'm interested in an FFT-like approach. I do not want a single output value. $\endgroup$ – tommym Oct 14 '20 at 1:46
  • 1
    $\begingroup$ hm, by the way, the FFT is not really a discretization of that integral - it's also cyclical. That makes this solvable, where in general, there's no solution to your integral equation. $\endgroup$ – Marcus Müller Oct 14 '20 at 6:35
  • 1
    $\begingroup$ What I meant by path was what @MarcusMüller assumes, and what you confirmed you are currently doing: holding $b$ constant and letting $a$ be the independent variable in the time (or spatial) domain. I'll note that for $f(a+ib) \in \mathbb{R}$ in this case, $F(\lambda)e^{-b\lambda}$ must have even symmetry in its real part and odd symmetry in its imaginary part (about $\lambda = 0$). Thus $F(\lambda)$ will have to be a function of $b$ as well, I believe. $\endgroup$ – Andy Walls Oct 14 '20 at 11:49

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.