# Discrete Fourier transform of an exponential decay

I have a vector with an exponential decay, using Numpy:

t=np.arange(128)
k=0.1
decay=np.exp(-k*t)


I would like to compute the discrete Fourier transform (DFT) of decay so I get the same result as applying np.fft.rfft(decay, n=128*2). I tried the formula described here plus some similar ones (without square terms in the denominator) but I never got the same result. The final result I want seems to be a one-sided Lorentzian? The reason I want to do this is because computing a Lorentzian is faster than computing an exponential and then applying fft.

To summarize, is there an easy way to compute the DFT for a given exponential decay function of known k?

This boils down to computing the sum of a geometric series. Given

$$x[n]=e^{-\alpha n},\qquad n=0,1,\ldots,N-1\tag{1}$$

the DFT is

\begin{align}X[k]&=\sum_{n=0}^{N-1}x[n]e^{-j2\pi nk/N}\\&=\sum_{n=0}^{N-1}e^{-\alpha n}e^{-j2\pi nk/N}\\&=\frac{1-e^{-\alpha N}}{1-e^{-\alpha}e^{-j2\pi k/N}},\qquad\alpha\neq 0,\quad k=0,1,\ldots N-1\tag{2}\end{align}

For $\alpha=0$, you have $X[0]=N$ and $X[k]=0$ for $k=1,2,\ldots,N-1$.

If you zero pad with $N$ zeros, i.e., if the DFT length is $2N$, the result can be computed in a very similar manner:

\begin{align}X[k]&=\sum_{n=0}^{N-1}x[n]e^{-j\pi nk/N}\\&=\sum_{n=0}^{N-1}e^{-\alpha n}e^{-j\pi nk/N}\\&=\frac{1-e^{-jk\pi}e^{-\alpha N}}{1-e^{-\alpha}e^{-j\pi k/N}}\\&=\frac{1-(-1)^ke^{-\alpha N}}{1-e^{-\alpha}e^{-j\pi k/N}},\qquad\alpha\neq 0,\quad k=0,1,\ldots 2N-1\tag{3}\end{align}

For $\alpha=0$ you get

$$X[k]=\begin{cases}N,\quad k=0\\0,\quad k\textrm{ even},k\neq 0\\\displaystyle\frac{2}{1-e^{-j\pi k/N}}, \quad k\textrm{ odd}\end{cases}\tag{4}$$

• Ok, this is good. I checked in numpy and the result is equivalent to np.fft.fft(decay), that is, the fft of a non-padded signal. Now, what I really need is to compute fft for a zero-padded decay. In my question, that is done by specifying n=128*2 (it pads input 128 zeros). Is there a way to compute that? – Brenlla Aug 14 '18 at 14:54
• @Brenlla: I've added the result for zero padding. – Matt L. Aug 14 '18 at 15:33
• Yep, that works fine. There is some floating-point precission loss for large N, since it is sitting inside an exponential – Brenlla Aug 14 '18 at 15:53