1
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ 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". $\endgroup$
    – ZR Han
    Jun 28, 2022 at 2:35
  • $\begingroup$ @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 ? $\endgroup$
    – Gze
    Jun 28, 2022 at 2:46
  • $\begingroup$ I don't quite understand, is it a vector in length of 4, and you want to perform a 4-sample FFT? $\endgroup$
    – ZR Han
    Jun 28, 2022 at 2:56
  • $\begingroup$ @ZRHan I updated the question, I think it's clearer now. $\endgroup$
    – Gze
    Jun 28, 2022 at 3:06
  • $\begingroup$ 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. $\endgroup$
    – ZR Han
    Jun 28, 2022 at 3:11

1 Answer 1

1
$\begingroup$

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$

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

Your Answer

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

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