I am working on a rather large project and am stuck on a small part of it. The problem is as follows:
Problem
Let $x=\{x_1, x_2, x_3, ..., x_{N-1}\}$ where $N$ is a power of two.
Let $X=\mathcal{F}(x)$ where $\mathcal{F}$ is the DFT of X.
Given only $X$, I need to find a $Y$ such that $\mathcal{F}(Y)=\{x_1, x_2, x_3, ..., x_{\frac{N}{2}-1}, 0, 0, 0, ...\}$ in linear time ($\mathcal{O}(N)$ ).
Example
For example, let $x=\{1, 2, 3, 4\}$. Then, $X=\{5 + 0 i, -1 - i, -1 + 0 i, -1 + I\}$.
I need a way to compute $Y=\mathcal{F}(\{1,2,0,0\})=\{1.5, 0.5 + i, -0.5, 0.5 - i\}$ in linear time.
Maybe Useful Info
I will just be performing convolutions between two vectors meaning that I don't care about the order of the elements.
I have not made much progress in this problem of mine. I believe that the answer may come from looking at the Cooley-Turkey FFT algorithm. A direct solution is preferable, but if you can think of a solution involving reordering the DFTs, storing them differently, etc., that would suffice. Finally, if you can think of a reason that this is not possible, please tell me so I don't waist my time.
Finally, I am in high school and while I am familiar with much of the mathematical notation, I am rather limited in much of the terminology. While I will work to understand your answers, please keep this in mind.
Thanks for your help, and have a great start of fall!
Edit I was thinking that I could compute a "partial" DFT based on the fact that $$X_k = \sum_{n=1}^{N-1}x_ne^{-2\pi ikn/N} = \sum_{n=1}^{N/2-1}x_ne^{-2\pi ikn/N} + (-1)^k\sum_{n=1}^{N/2-1}x_{n+N/2}e^{-2\pi ikn/N}= X_{k,A} + (-1)^kX_{k,B}$$.
Assuming I want to add two vectors of this form, I can do so as follows:
$$\text{If }Z_k = X_k + Y_k$$ then $$Z_{k,A} = X_{k,A}+Y_{k,A} \text{ and } Z_{k,B} = X_{k,B}+Y_{k,B}$$
This works in theory, but in practice, while $Z_{k,A} + (-1)^kZ_{k,B}$ has the correct values, $Z_{k,A}$ and $Z_{k,B}$ independently do not. Therefore, if I want to set $Z_{k,B}$ to $0$, $Z_{k,A} + (-1)^kZ_{k,B}$ does not correspond to vector I want it to. A solution using the evaluation of the two halves would mean there is an easy way to "redistribute" $Z_{k,A}$ and $Z_{k,B}$. However, I doubt there is a way to do this without computing any DFTs.