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


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}$$

  • $\begingroup$ 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? $\endgroup$
    – Brenlla
    Aug 14 '18 at 14:54
  • $\begingroup$ @Brenlla: I've added the result for zero padding. $\endgroup$
    – Matt L.
    Aug 14 '18 at 15:33
  • $\begingroup$ Yep, that works fine. There is some floating-point precission loss for large N, since it is sitting inside an exponential $\endgroup$
    – Brenlla
    Aug 14 '18 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.