Inverse DFT on the first half time domain ("DFT unpad property"?)

Question

Assume to have c[] representing N DFT coefficients. The complex-valued signal of N samples in the time domain is computed by idft(c, N).

Is there a straightforward way of reconstructing the signal just in the first half of the time domain by manipulating c[], and executing only idft(., N/2) multiple times?

Answer 1

Mirroring isn't required; this simply utilizes "subsampling in time <=> folding in Fourier", with duality and an extra step. Hence,

x = np.random.randn(128) + 1j * np.random.randn(128)

xf = fft(x)
A = ifft(xf[::2])
B = ifft(xf[1::2])
rotate = np.exp(1j * 2 * np.pi * np.arange(len(x)//2) / len(x))
x_half = (A + B*rotate) / 2

assert np.allclose(x[:len(x)//2], x_half)

Performance-wise, not much gain. In terms of pure FFT, it's more computationally efficient: $2 (N/2) \log(N / 2) < N \log(N)$. However, there's also complex multiplication that's $O(N/2)$. Assuming we pre-compute and reuse rotate (sampling exp(jw) is expensive), my benchmarks show the naive approach is superior for N that's a power of 2, and same or a little slower for other N. If we don't pre-compute, naive always wins.

Credit to OP for initial solution.

---

Details

A folds the second half of x onto the first: xA = x.reshape(2, -1).mean(axis=0), or (x[:8] + x[8:])/2, while B*rotate does the same except the folding is a subtraction, xB = (x[:8] - x[8:])/2, hence xA + xB = x_half.

Answer 2

For long sequences, there's very little computational gain from this arrangement.

Consider a sequence x[n] of length N, and its N-point DFT $X[k]$. Denote the first half of $x[n]$ as $x_1$, and its second half as $x_2$, then it can be shown that:

$$ \frac{N}{2}-DFT\{ x_1 + x_2 \} = X[2k] = X_e[k] \tag{1}$$ $$ \frac{N}{2}-DFT\{ W_1 x_1 + W_2 x_2 \} = X[2k+1] = X_o[k] \tag{2}$$

where $W_1$ and $W_2$ are the first & second halves of the sequence $W = e^{-j \frac{2\pi}{N} n } ~~,~~ n = 0,1,...,N-1$. Also, $X_e[k]$ and $X_o[k]$ are the even and odd indexed parts of $X[k]$ respectively.

Then, it's a matter of algebra to show the following:

$$ x_1 + x_2 = \frac{N}{2}-IDFT \{ X_e[k] \} \tag{3}$$ $$ W_1 x_1 + W_2 x_2 = \frac{N}{2}-IDFT \{ X_o[k] \} \tag{4}$$

then, multiply Eq.3 with $W_2$

$$ W_2 x_1 + W_2 x_2 = W_2 \cdot \left( \frac{N}{2}-IDFT \{ X_e[k] \} \right) \tag{5} $$ $$ W_1 x_1 + W_2 x_2 = \frac{N}{2}-IDFT \{ X_o[k] \} \tag{6}$$

and solve for $x_1$:

$$x_1 = \frac{ W_2 \cdot \left( \frac{N}{2}-IDFT \{ X_e[k] \} \right) - \left( \frac{N}{2}-IDFT \{ X_o[k] \} \right) }{ W_2 - W_1 } \tag{7}$$

Eq.7 indicates that the first half of the sequence $x[n]$ is obtained by two $\frac{N}{2}$-point inverse DFTs performed on even & odd indexed parts of $X[k]$ (which is your $c[n]$ sequence).

Answer 3

UPDATE: OverLordGoldDragon gave a solution that is superior to mine on every aspect. He got rid of mirroring, but more importantly he clearly exposed the insight to solve this problem. I hope he gets a shower of points!

It turns out to be not that difficult. At least when N is a power of 2.

The cornerstone of my approach is mirroring. Vanilla code (python):

import numpy as np

def mir(xin):
        n = xin.shape[0]
        return np.array([xin[-i & (n - 1)] for i in range(n)])

Now I can build an "unscaled" dft, using mir and idft (which is ifft here):

  import numpy.fft as fft

  def dft(xin) : 
     return fft.ifft(mir(xin))

I first mirror the frequencies to implement idft as radix-2 DIT, allowing in turn to reconstruct only half of the signal. But I need twiddle factors.

def split(xin) : 
    t = np.transpose(xin.reshape(-1, 2))
    return t[0], t[1]

def ifft_half(c):
        e, o = split(mir(c))
        
        G = dft(e)
        H = dft(o)
        
        N = c.shape[0]
        W = [np.exp(-1j * 2 * np.pi * k / N) for k in range(N//2)] #twiddle
        
        return (G + W * H) / 2