# Approximating improper integral with FFT

In d'Halluin et al. (2005) (http://imajna.oxfordjournals.org/content/25/1/87.short) the authors claim that the correlation integral $$I(x) = \int_{-\infty}^{\infty} V(x+y) f(y) dy$$ can be approximated with FFT methods by $$I_{k} = IFFT((FFT(V)_{k})(FFT(f))_{k}^{*})$$ where $(.)^{*}$ denotes the complex conjugate.

I have tried to program this in Matlab with $V = \max(90 e^{y} - K,0)$ and $f$ being the probability density function of the normal distribution with $\mu = 0.1$ and $\sigma = 0.2$. Analytically I get the result $I(0) = 8.783$ but in whatever way I try the FFT approximation the results are nowhere close to that.

My math background is really weak and I don't have any intuition or knowledge regarding the FFT method. I calculated a set of values (powers of 2) for $V()$ and $f()$, did both element-wise and matrix multiplications of the FFTs of the two vectors and checked the real part of the IFFT, but I never get the desired result.

What am I doing wrong? Can someone tell me how I get to the result?

Here's the code of one of the ways I did it:

S = 90;
K = 100;
mu = 0.1;
sig = 0.2;
AA = 2.5;
N = 255;
x = (linspace(-AA,AA,N+1))';

V = max(S.*exp(x) - K,0);
ffff = normpdf(x,mu,sig);

I_k = real(ifft(fft(V).*conj(fft(ffff))));

• We can't know what you did wrong, your code is not even in the post. Have you checked the Convolution theorem? – nicoguaro Jun 14 '16 at 15:14
• okay, I added the code, but that's just one of the possibilities I have tried – C. S. Jun 14 '16 at 15:33
• In your description, what is the index $k$ in the second formula? – Wolfgang Bangerth Jun 14 '16 at 18:41
• I'm not sure, but I guess it's the index for the discretized $x$, $x_{k}$ – C. S. Jun 14 '16 at 18:43

Even though this is a strict requirement, the authors explicitly mention that $x$ is equally spaced in the space of $log(S)$. They also generate it this way in the pseudocode. In that case $\bar{V}(log S) = V(S)$. I think you do not satisfy that. And in the paper, it is also the case that $\bar{f}$ is a probability density. This is just to warn in advance.
Their resolution to interpolation along non-equally spaced intervals comes at a later stage, where they explicitly interpolate the discrete values of the result onto the original $S$ grid.
So, theoretically, the equation is an altered cross-correlation, where $f$ is not a complex conjugate. Then in that case, the formula is correct (not an approximation) - with periodic border treatment of course.
• I don't understand. Both the analytic and the FFT integral are in the same space and the $x$ for the FFT are equidistant. – C. S. Jun 15 '16 at 13:16