Consider a discrete signal $x$ of size $n$, and write $c$ its discrete Fourier transform. Unless I'm mistaken, the relations between the two look something like:

\begin{split}c_k = \sum_{j=0}^{n-1} x_j \exp\left(-2i\pi k\tfrac{j}{n} \right) \\ x_k = \frac{1}{n}\sum_{j=0}^{n-1} c_j \exp\left(2i\pi k\tfrac{j}{n} \right) \\\end{split}

Thanks to FFT-type algorithms, it is possible to compute those transformations in $\mathcal{O}(n \ln(n))$.

Now suppose that $x$ has a sub-period $m < n$ with $n=0 \pmod m$, that is $x_{i+m \pmod n} = x_{i}$ for all $i$. Then, the coefficients $c_k$ are sparse in the sense that $c_k = 0$ unless $k=0 \pmod m$. Moreover, the nonzero coefficients can be retrieved from a FFT of $x$ using only the first $m$ values.

This idea of a known sparsity pattern of the coefficients / signal leading to more efficient computation is also exploited in RFFT, DCT and DST.

My question is the following: Suppose I know a periodic sparsity pattern for the coefficients, how can I use this kind of trick to avoid redondant computation.

Related question: I've heard of "sparse" fast Fourier transforms. Is this what I'm describing or is this something else? Are "sparse" fast Fourier transform algorithms the answer to my question? Where can I read/learn more about them?


1 Answer 1


The simplest way is to just do an FFT over $M$ samples and than expand to the desired FFT length by inserting zeros between samples and dividing by the ratio of the FFT length to the period $R = N/M$

$$C_{k,N} = \frac{M}{N}\begin{cases} C_{k/R,M} & k = r \cdot R, r \in \mathbb{Z} \\ 0 & \text{otherwise} \end{cases} $$

  • $\begingroup$ Thank you @Hilmar for your answers. It describes in greater length what I too briefly stated as "Moreover, the nonzero coefficients can be retrieved from a FFT of x using only the first m values." My question is a bit more general though. I think I should take a bit more time to reformulate with more precise terms and ask again in a separate question. $\endgroup$ Commented Aug 21, 2023 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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