Discrete Fourier Transform with known periodic sparsity pattern or constraints

Question

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?

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