# Discrete Fourier Transform with known periodic sparsity pattern or constraints

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?

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