# Levinson Recursion for Non Square Toeplitz Matrices

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.

• 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. – Federico Poloni Jan 12 at 16:27
• You may think of it as the Least Squares Solution in the case of a Non Square Toeplitz Matrix. – Royi Jan 12 at 17:41