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

Question

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.

Answer 1

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

Answer 2

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.