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

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?

• For your example, $x = x_1 * [1,1,1,1]^T$ and the FFT of $[1,1,1,1]^T$ can be pre-calculated offline. So you'd better give more details about what you mean "the input vector is repeating". Jun 28, 2022 at 2:35
• @ZRHan $x_1$ is a vector, and it's repeating for four times. yes we can consider it as $x_1*[1,1,1,1]^T$. so will the complexity be reduced in that case ?
– Gze
Jun 28, 2022 at 2:46
• I don't quite understand, is it a vector in length of 4, and you want to perform a 4-sample FFT? Jun 28, 2022 at 2:56
• @ZRHan I updated the question, I think it's clearer now.
– Gze
Jun 28, 2022 at 3:06
• The FFT of $[1,1,1,1]$ is $[4,0,0,0]$, and thus the FFT of $x_1*[1,1,1,1]$ is $[4x_1,0,0,0]$. If $x_1$ is changing, you can simply update the FFT result. Jun 28, 2022 at 3:11

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

• can not he simply repmat y assuming the first x_1 only? Jun 29, 2022 at 1:19