## Summary:

Given $X$ (the discrete Fourier transform of some unknown vector $x$ of length $N$), is there any shortcut to computing $X'$ (the Fourier transform of $x$ after padding it with $N$ zeros)?

Of course, this can be accomplished by computing $x$ from $X$ (via the inverse discrete Fourier transform), then padding it with zeros, and finally computing $X'$; however, the even indices of $X'$ are already given by $X_{2 k}' = X_k$. Does this knowledge afford us any shortcut? *I.e.*, is there a way to compute (or accurately approximate) the odd indices of $X'$ without returning to the time domain (or faster than the $O(N log(N))$ steps required by returning to the time domain)?

I've written a more rigorous (read: longer) description of the puzzle below.

## Definitions:

(This is just to make sure the question is as clear as possible)

**Fourier transform of original signal:**

For a sequence $x=[x_0, x_1, \ldots x_{N-1}]$, the discrete Fourier transform:

$$X_k = \sum_{n=0}^{N-1} x_n ~e^{-2 \pi i k n / N}.$$

Directly computing $X$ via the summation above requires roughly $N^2$ steps (a summation over $N$ terms for each of the $N$ terms of $X$; however, $X$ can also be computed in $N log(N)$ steps using fast Fourier transforms (FFT), which is easy to perform when $N$ is a power of 2.

**Fourier transform of zero-padded signal:**

For a sequence that has been padded with $N$ zeros (so it has doubled in length) $x'=[x_0, x_1, \ldots x_{N-1}, 0, 0, \ldots 0]$, you can also compute its discrete Fourier transform:

$$X_k' = \sum_{n=0}^{2 N-1} x_n' ~ e^{-2 \pi i k n / (2 N)}$$

The terms when $x_n'=0$ can be excluded, yielding $$X_k' = \sum_{n=0}^{N-1} x_n' ~ e^{-2 \pi i k n / (2 N)}$$ $$ = \sum_{n=0}^{N-1} x_n ~ e^{-2 \pi i k n / (2 N)}.$$

If we are given $x$, we can compute the discrete Fourier transform of $x'$ via FFT in at most $2 N log(2 N)$ steps.

## My Question:

Assume you are given $X$ but not $x$, and that you want to compute $X'$.

**Simple solution:**

You could calculate $x$ via inverse FFT in $N log(N)$ steps, pad $x$ with zeros to compute $x'$, and then compute $X'$ in $2 N log(2 N)$ steps.

**Is there a way to compute $X'$ from $X$ without returning to the time domain?**

The even indices of $X'$ are already known because we are given $X$:

$$X_{2 k}' = \sum_{n=0}^{N-1} x_n ~ e^{-2 \pi i 2 k n / (2 N)}$$ $$ = \sum_{n=0}^{N-1} x_n ~ e^{-2 \pi i k n / N}$$ $$ = X_k$$

(for convenience of this and FFT, please assume that $N$ is a power of 2, and thus assume that $x'$ and $X'$ both have lengths $2 N$).

We do not know the values at the odd indices of $X'$. **Given the values at the even indices of $X'$, is there some way to compute only the values at the odd indices of $X'$? Has this problem already been posed? Has it been proven that the most efficient method for doing this is by returning to the time domain?**

**Notes:**

I know that zero-padding in the time domain is equivalent to ideal interpolation in the frequency domain, indicating the possibility of computing the values even indices of $X'$, and then somehow convolving with a sinc function (I believe, please forgive me if this is not precisely stated); however, performing this convolution would effectively require returning to the time domain (which would be the equivalent of a low pass filter in the time domain, which is the same as zero padding $x$, etc., *i.e.* the simple solution above).

**Thanks:**

Sorry for the lack of brevity, I wanted to make sure the question was as easy as possible to understand. Please feel free to ask any clarifying questions, and thank you immensely for any insights you can give to this fun puzzle.