Efficiently computing symmetric Toeplitz matrix such that $Tx=y$

Question

Let $x,y \in \mathbb{R}^N$ be known vectors. I am looking for an efficient means to compute the $N$ coefficients of the following symmetric Toeplitz matrix

$$T = \begin{bmatrix} c_0 & c_1 & \ldots & c_{N-1} \\ c_1 & c_0 & \ldots & c_{N-2} \\ \vdots & \vdots & \ddots & \vdots \\ c_{N-1} & c_{N-2} & \ldots & c_0 \end{bmatrix}$$

which satisfies

$$Tx=y$$

Tests in Mathematica seem to indicate that all $c_i$ can be uniquely determined from $x$ and $y$, but I cannot find a generic algorithm to do this.

Answer 1

Are you sure this is always possible with a symmetric Toeplitz matrix? Take for example $x = [1, 1, 0, \ldots, 0]^T$. Then the first two elements of $T \cdot x$ are given by $c_0 + c_1$ and $c_1 + c_0$. Therefore, if $y_0 \neq y_1$, there is no solution.

If you drop the symmetric constraint it's easier. For

$$T = {\rm toep}\{c\} = \begin{bmatrix} c_0 & 0 & 0 & \ldots & 0 \\ c_1 & c_0 & 0 & \ldots & 0 \\ c_2 & c_1 & c_0 & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_{N-1} & c_{N-2} & c_{N-3}& \ldots & c_0 \end{bmatrix},$$ we have ${\rm toep}\{c\} \cdot x = {\rm toep}\{x\} \cdot c$ due to the commutativity of the (truncated) convolution. To see this, just write out the product: $y_0 = c_0 x_0$, $y_1 = c_0 x_1 + c_1 x_0$, $y_2 = c_0 x_2 + c_1 x_1 + c_2 x_0$ and so on, you can clearly see how $c$ and $x$ are interchangeable. Then, it is easy to find $c$ via $c = {\rm toep}\{x\}^{-1} \cdot y$. Note that since the Toeplitz matrix is diagonal, this can be done efficiently. We have $c_0 = \frac{y_0}{x_0}$, $c_1 = \frac{y_1 - c_0 x_1}{x_0}$, etc.

If you must do it with symmetrix Toeplitz matrices (which will not always work), write out your products and isolate the c's. You'll notice that $T = c_0 I + \sum_{n=1}^{N-1} c_n (D_n + D_n^T)$, where $D_n$ is a matrix with ones on its $n$-th diagonal (note that $D_n = D_1^n$ for $n\geq 1$). Therefore, $T x = c_0 x + \sum_{n=1}^{N-1} c_n (D_n + D_n^T)x$, which we can write as $T x = X \cdot c$, where $$X=\begin{bmatrix} x & (D_1 + D_1^T)x & \ldots & (D_{N-1} + D_{N-1}^T)x\end{bmatrix}.$$ This allows to solve for $c$ via $c = X^{-1} y$, provided that $X$ is invertible (it is not for my example given in the beginning of this post).

Answer 2

You are looking for a $c$ such that $y = c \ast x,$ where $\ast$ denotes (cyclic) convolution. Take Fourier transforms (DFT, in this case) of both sides, to get $\widehat{y} = \widehat{c} \widehat{x},$ where the multiplication is pointwise.It follows that you can compute $c$ given $x, y$ as long as the compatibility condition that $\widehat{y}_i$ is zero if $\widehat{x}_i$ is.