Can I reduce the complexity of multiplication with FFT if the input vector is repeating?

Question

I have a Fourier matrix $F$ with size $N \times N$, such that $y = F \times x$, if I have the vector $x$ contains four identical parts, for example $x = [x_1, x_2,x_3,x_4]’$ and $x_1 = x_2 = x_3 = x_4$ can I simplify the multiplication $y = F \times x$ into smaller matrix to reduce the complexity? . For example use smaller matrix of Fourier matrix $F$ to be multiplied only with $x_1$ or any other way.

I am talking here about the complexity of radix-2 FFT, which is $O(N log_2N)$

Example

I have the vector $x_1$ which is repeated four times yielding $x = [x_1, x_1,x_1,x_1]^T$, and I need to perform $y = F \times x$, can the complexity in that case be reduced compared if $x_1$ is not repeating?

Answer 1

A few clarifications may help.

You can implement the Discrete Fourier Transform (DFT) using a multiplication with Fourier Transform Matrix that's made up of the twiddle factors but this is NOT an FFT. An FFT is a different algorithm to implement the DFT but it's based on breaking down the DFT into separate "stages".

Matrix multiplication has complexity $N^2$, the FFT has complexity $N\log_2(N)$

If your input is periodic, you can indeed simplify the computation. Let's assume we have a core sequence $x[n]$ of length $N$ and it's DFT $X(k)$. We form a new sequence $y[n]$ my repeating $x[n]$ L times and want to calculate its DFT $Y[k]$. The length of the new sequence is obviously $M = N\cdot L$

We find that

$$Y(k) = \left\{\begin{matrix} L\cdot X(k/L) & x/L \in \mathbb{Z} \\ 0 & else \\ \end{matrix}\right. $$

In other words you can obtain $Y(k)$ by the following procedure

1. Calculate the DFT of the core sequence
2. Insert $L-1$ zeros between each sample
3. Multiply by $L$

The gain in efficiency depends a bit on your original algorithm. For matrix multiplication it will be roughly $L^2$. For an FFT it will be on the order of $L$