# Fast Fourier Inversion: Functions of a Complex Argument $f:\mathbb{C} \rightarrow \mathbb{R}$

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?

EDIT

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.

• 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? – Andy Walls Oct 13 '20 at 19:12
• 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 – Marcus Müller Oct 13 '20 at 23:31
• @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. – tommym Oct 14 '20 at 1:46
• 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. – Marcus Müller Oct 14 '20 at 6:35
• 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. – Andy Walls Oct 14 '20 at 11:49