Interpreting FFT Coefficients from System Matrix That Is Originally Toeplitz (Not Circulant)

Question

If I have a measured signal $y$, true signal $x$, and a convolution matrix $A$ that is a Toeplitz but not circulant matrix, I can write the convolution as

\begin{equation} y = A x \ . \end{equation}

However, I would like to analyze the system using diagonalized coefficients of the Fourier transform. A re-formulation such as the one given below is often used to provide a means for fast computation: \begin{equation} \left[\begin{array}{c} y\\ y' \end{array}\right] = C \left[\begin{array}{c} x\\ 0 \end{array}\right] = \left[\begin{array}{cc} A & B \\ B & A \end{array}\right] \left[\begin{array}{c} x\\ 0 \end{array}\right] = \left[\begin{array}{c} A x \\ B x \end{array}\right] \ , \end{equation} where $C$ is a circulant matrix into which the Toeplitz matrix $A$ is embedded, using an additional matrix $B$ derived from the values of $A$.

Diagnoalized values of $C$ can be obtained by multiplication with Discrete Fourier Transform matrices. But are these values relevant for interpreting the behavior of the original system, $y = Ax$ - for instance, for use in construction of a Wiener filter for the original system?

Answer 1

If I understand your question, then the answer lies in the equivalence of linear and circular convolution - the linear convolution being implemented by multiplication with a toeplitz matrix, while circular convolution is implemented by multiplication with a circulant matrix.

If you have a length N signal and length M filter impulse response, the circular and linear convolutions are equivalent if you pad the signal and filter with zeros to length N+M-1 - that is, you can implement the linear convolution using the DFT. You are padding x with zeros above, and presumably the number of zeros is such that the length N+M-1 requirement is met. Then in matrix form, the DFT matrix would diagonalize the corresponding convolution operator.

Hope this helps - I'm short on time right now and can't provide a more detailed explanation.