Half length inverse DFT to obtain half of the concatenation of a signal with negative of itself

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.

• 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". Commented Apr 26, 2023 at 13:59
• 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? Commented Apr 26, 2023 at 17:35
• @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 Commented Apr 27, 2023 at 7:06
• @Sajjad Sorry, I made a mistake. Commented Apr 27, 2023 at 7:44

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')

• How about if we used the matrix F = dftmtx(16)/sqrt(16) instead of fft and ifft ? what would be the vector rotate? Commented Apr 27, 2023 at 9:11
• @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. Commented Apr 27, 2023 at 13:14

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.