3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I didn't think to diagonalize $T$. Doesn't this only work, though, if $T$ is circulant, not symmetric Toeplitz? $\endgroup$ – Steven Roberts Apr 2 '18 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.