1
$\begingroup$

I used to read some white papers online, where they mention the below statement:

If we have a real vector $\mathbf{y} \in \mathbb{R}^{N \times 1}$ which is an output of $IFFT$ process with size $N \times N$; $\mathbf{y} = \mathbf{F'} \times \mathbf{x}$ where $\mathbf{F}$ is the fast fourier transform matrix and $\mathbf{x}$ is the input complex vector. If $\mathbf{y}$ can be written as $\mathbf{y} = [ \mathbf{v}, - \mathbf{v}]$, that means the first half of $\mathbf{y}$ which is $\mathbf{v}$ can be generated using $IFFT$ whose size is $\frac{N}{2} \times \frac{N}{2}$.

For example:

To have the output of the inverse fourier transform as mention above, the input must be Hermitian symmetry and odd values are used as following:

$\mathbf{x} = [0, x_1,0,x_2,...,x_{N/2-1},0,x^*_{N/2-1},....,x^*_2,0,x^*_1]$.

where $x^*$ is the complex conjugate of $x$. So, taking the inverse Fourier transform for $\mathbf{x}$ will result a real vector $\mathbf{y} = [ \mathbf{v}, - \mathbf{v}]$ where $\mathbf{v}$ is a real vector too.

My question, how can I get the vector $\mathbf{v}$ using the non-zeros values of $\mathbf{x}$ and $\frac{N}{2} \times \frac{N}{2}$ inverse Fourier transform? If the answer is supported by sample matlab example, I would appreciate it.

$\endgroup$
4
  • $\begingroup$ What's your goal here? While you CAN implement the DFT as a matrix multiplication, it's rarely done this way since it is very inefficient. That's what the FFT is for: it's a fast algorithm to implement the DFT that does NOT use matrix multiplication. It would help to define clearly what you mean by "IFFT". $\endgroup$
    – Hilmar
    Apr 26, 2023 at 13:59
  • $\begingroup$ Do you want to see the explicit math that modifies an $\frac{N}{2}$-point complex DFT into a real-input DFT having $N$ real samples input? $\endgroup$ Apr 26, 2023 at 17:35
  • $\begingroup$ @OverLordGoldDragon Yes ifft([0, 1, 0, 2, 0, 3, 0, 3, 0, 2, 0, 1]) is a vector $\mathbf{y} = [\mathbf{v},-\mathbf{v}]$ where in this vase $\mathbf{v}$ is 1.0000 -0.2887 0 0 0 0.2887 $\endgroup$
    – Sajjad
    Apr 27, 2023 at 7:06
  • $\begingroup$ @Sajjad Sorry, I made a mistake. $\endgroup$ Apr 27, 2023 at 7:44

2 Answers 2

2
$\begingroup$

If $\mathbf{x}$ is such that $\texttt{iFFT}(\mathbf{x}) = [\mathbf{v}, -\mathbf{v}]$, where $\mathbf{v}$ is real-valued, then

v = ifft(x(2:2:end)) .* exp(1j * 2 * pi * (0:numel(x)/2-1) / numel(x)) / 2;

This applies Subsampling in time <=> Folding in Fourier, as explained under "Details" here. We omit A as x(1:2:end) is all zeros, so we're only operating on odd-indexed (non-zero) $\mathbf{x}$.

DFT form

Let $\mathbf{x}_o$ be the "original" vector, without zeros, that's packed into $\mathbf{x}$. Then we have, with $N$ being the length of $\mathbf{x}$ and $M=N/2$ the length of $\mathbf{x}_o$:

$$ \begin{align} [\mathbf{v}, \mathbf{-v}] = \texttt{iDFT}(\mathbf{x}) &= \frac{1}{N}\sum_{n=0}^{N-1} \mathbf{x}[n] e^{2\pi j (k/N) n} \tag{1} \\ \texttt{iDFT}(\mathbf{x_o}) &= \frac{1}{M}\sum_{m=0}^{M - 1} \mathbf{x_o}[m] e^{2\pi j (k/M) m} \tag{2} \end{align} $$

and so,

$$ \begin{align} \mathbf{v} = \frac{\mathbf{r}}{2} \cdot \texttt{iDFT}_\text{odd}(\mathbf{x}) &= \frac{\mathbf{r}}{2M}\sum_{m=0}^{M-1} \mathbf{x}[2m + 1] e^{2\pi j (k/M) m} \tag{3} \\ &= \frac{\mathbf{r}}{2} \cdot \texttt{iDFT}(\mathbf{x}_o) \\ &= \frac{\mathbf{r}}{2}\frac{1}{M}\sum_{m=0}^{M - 1} \mathbf{x}_o[m] e^{2\pi j (k/M) m} \tag{4} \\ &= 0.5 \mathbf{x}_o \mathbf{D}^\text{inv}_M \mathbf{r} \tag{5} \end{align} $$

where $\mathbf{D}^\text{inv}_{M}$ is the length-M $\texttt{iDFT}$ matrix, and $\mathbf{r}$ is the (length M) complex rotation vector:

$$ \mathbf{r} = r[k] = e^{\pi j (k/M)}. \tag{6} $$

In terms of using a $1/\sqrt{N}$-normed DFT or FFT, it's a bit tricky per different-length operations, see code. In short, we adjust the smaller DFT (which uses $1/\sqrt{N}$ in forward and $1/\sqrt{M}$ in inverse) by $\cdot \sqrt{N/M}$.

Full FFT & DFT example

% generate signal
N = 16;
M = N/2;
v = randn(1, M);
y = [v, -v];

% generate reusables; use the sqrt DFT norm
dft_mtx = dftmtx(N) / sqrt(N);
idft_mtx_adj = conj(dftmtx(M)) / sqrt(M) * sqrt(N/M);
rotate = exp(1j * pi * (0:M-1) / M) / 2;  % `/2` for speed; not part of definition

% run DFT & FFT
x_fft = fft(y);
x_dft = y * dft_mtx;
x_fft_nonzeros = x_fft(2:2:end);
x_dft_nonzeros = x_dft(2:2:end);
v_recovered_fft = ifft(x_fft_nonzeros) .* rotate;
v_recovered_dft = x_dft_nonzeros * idft_mtx_adj .* rotate;

% test; mimic `numpy.allclose` https://stackoverflow.com/a/28975920/10133797
rtol = 1e-5;
atol = 1e-8;
all( abs(v-v_recovered_fft) <= atol+rtol*abs(v_recovered_fft), 'all')
all( abs(v-v_recovered_dft) <= atol+rtol*abs(v_recovered_dft), 'all')
$\endgroup$
2
  • $\begingroup$ How about if we used the matrix F = dftmtx(16)/sqrt(16) instead of fft and ifft ? what would be the vector rotate? $\endgroup$
    – Sajjad
    Apr 27, 2023 at 9:11
  • $\begingroup$ @Sajjad Updated. To avoid duplication, I simply linked the posts that explain how this answer works - if it's helpful, consider voting on those also. $\endgroup$ Apr 27, 2023 at 13:14
2
$\begingroup$

I'm not sure if this answers your precise question, but one method of packing an N-sized real-valued FFT into a N/2-sized complex FFT is covered in "Numerical Recipes" in section 12.3.2, "FFT of a Single Real Function."

The text can be viewed online, click on chapter 12 in the left sidebar.

$\endgroup$

Your Answer

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

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