How to find a vector in time domain that validate the equality in the frequency domain

Consider the ring of polynomials over the complex field modulo $z^N - 1$. Define the polynomials

$$ X(z) = \sum_{k=0}^{N-1} x_k , z^k \quad \text{and} \quad H(z) = \sum_{j=0}^{3} h_j , z^j. $$

Because the circular convolution $r = h * x$ of length $N$ corresponds exactly to the product

$$ R(z) \equiv H(z),X(z) ; (\mathrm{mod} ; z^N - 1), $$

we have

$$ R\left(e^{\tfrac{2\pi i , n}{N}}\right) = H\left(e^{\tfrac{2\pi i , n}{N}}\right),X\left(e^{\tfrac{2\pi i , n}{N}}\right). $$

Now, split $X(z)$ into two parts: the “known tail” of length $M \gg 4$ and the “unknown head.” Write

$$ X(z) = X_{\mathrm{head}}(z) + X_{\mathrm{tail}}(z), \quad X_{\mathrm{tail}}(z) = \sum_{k=N-M}^{N-1} x_k , z^k, $$

where $x_{N-4}, \dots, x_{N}$ are given. Define similarly

$$ R_{\mathrm{tail}}(z) = H(z),X_{\mathrm{tail}}(z) \quad (\mathrm{mod} ; z^N - 1). $$

In the time domain, $X_{\mathrm{tail}}(z)$ accounts for the last $M$ values of $x$, so the corresponding part of the circular convolution

$$ r_{\mathrm{tail}} = h * x_{\mathrm{tail}} $$

is completely determined by $h$ and those known entries. However, these known samples also “wrap around” index $k = 0$ because of the circular nature, causing interference with the unknown head. To decouple this rigorously, consider

$$ \Delta(z) = R(z) - R_{\mathrm{tail}}(z). $$

By construction,

$$ \Delta(z) \equiv H(z),X_{\mathrm{head}}(z) ; (\mathrm{mod} ; z^N - 1). $$

We do not know $X_{\mathrm{head}}(z)$ in full, but we do have partial frequency information of $R$. Specifically, if a small subset ${p_1, p_2, \dots} \subset {0, 1, \dots, N-1}$ is such that we know

$$ R\left(e^{\tfrac{2\pi i, p_\ell}{N}}\right), $$

then at each $z = e^{\tfrac{2\pi i, p_\ell}{N}}$,

$$ \Delta\left(e^{\tfrac{2\pi i, p_\ell}{N}}\right) = R\left(e^{\tfrac{2\pi i, p_\ell}{N}}\right) - H\left(e^{\tfrac{2\pi i, p_\ell}{N}}\right) , X_{\mathrm{tail}}\left(e^{\tfrac{2\pi i, p_\ell}{N}}\right). $$

Hence,

$$ \Delta\left(e^{\tfrac{2\pi i, p_\ell}{N}}\right) = H\left(e^{\tfrac{2\pi i, p_\ell}{N}}\right), X_{\mathrm{head}}\left(e^{\tfrac{2\pi i, p_\ell}{N}}\right). $$

Let us introduce an auxiliary polynomial

$$ Q(z) = \sum_{m=0}^{3} q_m , z^m $$

so that its discrete Fourier transform helps decouple the unknown head from the known tail. In particular, choose $q_m$ so that

$$ Q\left(e^{\tfrac{2\pi i , n}{N}}\right) = \begin{cases} \frac{1}{X_{\mathrm{tail}}\left(e^{\tfrac{2\pi i , n}{N}}\right)}, & \text{if } n \text{ is in the known set}, \ 0, & \text{otherwise}, \end{cases} $$

assuming $X_{\mathrm{tail}}\left(e^{\tfrac{2\pi i, n}{N}}\right) \neq 0$ in those frequencies. (Such a polynomial can be constructed via an interpolation argument in the ring $\mathbb{C}[z]/(z^N - 1)$, though higher-degree forms or partial approximations might be required in practice.) Then at each known frequency $\omega_{p_\ell}$,

$$ Q\left(\omega_{p_\ell}\right) , \Delta\left(\omega_{p_\ell}\right) = H\left(\omega_{p_\ell}\right) , \frac{X_{\mathrm{head}}\left(\omega_{p_\ell}\right)}{X_{\mathrm{tail}}\left(\omega_{p_\ell}\right)} , X_{\mathrm{tail}}\left(\omega_{p_\ell}\right) = H\left(\omega_{p_\ell}\right), X_{\mathrm{head}}\left(\omega_{p_\ell}\right). $$

But if $Q(\omega_{p_\ell})$ is chosen to zero out the unknown portion of $X_{\mathrm{head}}$ at other frequencies, we effectively isolate a small system of equations for $H(\omega_{p_\ell})$. Rewriting

$$ H(z) = h_0 + h_1, z + h_2, z^2 + h_3, z^3 $$

gives

$$ H\left(\omega_{p_\ell}\right) = h_0 + h_1, \omega_{p_\ell} + h_2, \omega_{p_\ell}^2 + h_3, \omega_{p_\ell}^3, \quad \omega_{p_\ell} = e^{\tfrac{2\pi i, p_\ell}{N}}. $$

So each known frequency $p_\ell$ supplies one polynomial relation in the four unknowns ${h_0, h_1, h_2, h_3}$. Even when the number of known frequency values is smaller than $4$, one can invoke additional constraints from the known tail in the time domain: for large enough $M$, the last $M$ samples of $r$ (each of which is a linear functional of $h_0, h_1, h_2, h_3$ via the known $x_k$) yield extra equations. For each $n = N - M, \dots, N - 1$, we have

$$ r_n = \sum_{j=0}^3 h_j , x_{(n - j) \bmod N}. $$

Since $x_{(n - j) \bmod N}$ is known in that index range, each of these is a linear constraint on ${h_0, h_1, h_2, h_3}$. Collecting all these linear equations, along with the transformed-domain relations involving $H(\omega_{p_\ell})$, forms a potentially overdetermined system. Solving that system in $\mathbb{C}$ determines a unique ${h_0, h_1, h_2, h_3}$ unless the system is degenerate.

Note that each known time-domain sample $r_n$ becomes an affine equation in ${h_0, \dots, h_3}$ once the corresponding $x_{(n - j) \bmod N}$ is given. Meanwhile, each known frequency-domain value $R(\omega_{p_\ell})$ factors as $H(\omega_{p_\ell}), X(\omega_{p_\ell})$ and hence gives a polynomial condition on $h_0, h_1, h_2, h_3$. By suitably combining those constraints—via an interpolating polynomial $Q(z)$ that zeroes out unwanted spectral components of the unknown portion of $X(z)$—we can form a closed-form system on the small set ${h_0, h_1, h_2, h_3}$.