3
$\begingroup$

Given a rectangular Toeplitz Matrix $ H $, how could one solve:

$$ y = H x $$

For instance, $ H $ can be Linear Convolution Matrix of the filter $ h $:

$$ H = \begin{bmatrix} {h}_{1} & 0 & 0 & \ldots & & 0 \\ {h}_{2} & {h}_{1} & 0 & \ldots & & 0 \\ {h}_{m} & \ldots & {h}_{1} & 0 & \ldots & 0 \\ 0 & {h}_{m} & \ldots & {h}_{1} & 0 & \ldots & 0 \\ \vdots & & \ddots & & & \vdots \\ 0 & \ldots & {h}_{m} & {h}_{m - 1} & \ldots & {h}_{1} \\ 0 & \ldots & 0 & {h}_{m} & \ldots & {h}_{2} \\ \vdots & & \ddots & & & \vdots \\ 0 & \ldots & & 0 & \ldots & {h}_{m} \\ \end{bmatrix} $$

Which is clearly not square.
In the general case it would be generated by:

numRows = 10; %<! Or any other number
numCols = 20; %<! Or any other number
vR = randn(numRows, 1);
vC = randn(numCols, 1);
mH = toeplitz(vC, vR);

Since the Matrix is not square, I'm after the least squares solution:

$$ \arg \min_{x} {\left\| H x - y \right\|}_{2}^{2} $$

I have implemented the Levinson Recursion for the square case yet I'd like to know if there is an extension to it.

At the moment the trick I use for this specific case it to partition the matrix and data for a subset of square Toeplitz Matrices and use the algorithm I implemented.
I wonder if there is a better way.

$\endgroup$
  • $\begingroup$ What are you trying to compute here? In the square case, a (nonsingular) linear system has a unique solution, so I assume that this solution is your 'target'. In the non-square case, there are either zero or infinite solutions, so it is not clear what this algorithm should compute in the first place. $\endgroup$ – Federico Poloni Jan 12 at 16:27
  • 2
    $\begingroup$ You may think of it as the Least Squares Solution in the case of a Non Square Toeplitz Matrix. $\endgroup$ – Royi Jan 12 at 17:41

Your Answer

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

Browse other questions tagged or ask your own question.