# Deconvolution

Started by July 12, 2006
```Why is the inversion of a Toeplitz system Ax=b, where A is a Toeplitz
matrix, ill-posed even when A is not rank deficient?. If A is full rank,
shouldnt the system have a unique solution and not be affected by small
noise perturbations?. How can one relate the ill-posedness of
deconvolution problems to the behaviour of the Toeplitz Matrix.

Thanks
-Goks

```
```On 2006-07-12 11:16:05 -0300, "gokul_s1" <swamygok@msu.edu> said:

> Why is the inversion of a Toeplitz system Ax=b, where A is a Toeplitz
> matrix, ill-posed even when A is not rank deficient?. If A is full rank,
> shouldnt the system have a unique solution and not be affected by small
> noise perturbations?. How can one relate the ill-posedness of
> deconvolution problems to the behaviour of the Toeplitz Matrix.
>
>
> Thanks
> -Goks

1  0  0
0  1  0
0  0  10^-10

which is of full rank and provides unique solutions.

Is it prone to amplify small errors in the third component?

Full rank, and thus uniqueness, does not mean that the
inverse will be small. Large values in the inverse will
tend to amplify small perturbations.

Try looking at the values in the inverse with the eigenvalues
as a quick way to get there. One will see that Toeplitz matrices
can be ill conditioned.

```
```gokul_s1 wrote:
> Why is the inversion of a Toeplitz system Ax=b, where A is a Toeplitz
> matrix, ill-posed even when A is not rank deficient?. If A is full rank,
> shouldnt the system have a unique solution and not be affected by small
> noise perturbations?. How can one relate the ill-posedness of
> deconvolution problems to the behaviour of the Toeplitz Matrix.
>
>
> Thanks
> -Goks

Hello Goks,

To follow up on what Gordon said, you may wish to look up condition
numbers as applied to matrices. And you will find how it is very easy
to create a matrix that is numerically very difficult t work with.

A good book on numerical analysis that I would recommend is Forman S.
Acton's "Numerical Methods That Work." He offers an interlude in the
middle of the book about what to not compute. And gives a lot of
examples of things are ill conditioned. Try looking up Hilbert
Matrices. It is easy to set up a system where Hx=b and H is a Hilbert
matrix and ith element of b is chosen to be the sum the elements on row
i. The solution is simply x=(1,1,1,1,1,1,...,1). But try this on a
computer and see how close you get!

IHTH,

Clay S. Turner

```
```Thanks for your response.

I guess the answer does lie in the condition number of the matrix.
Consider this matrix [1 10 10
0 1 10;
0 0 1 ]
This matrix has all eigen values equal to 1...but it is still ill
conditioned. It is quite interesting to know that the eigenvalues play no
role in determining the stability of the inverse!

```
```gokul_s1 wrote:
>
> I guess the answer does lie in the condition number of the matrix.
> Consider this matrix [1 10 10
>              0 1 10;
>              0 0 1 ]
> This matrix ...

Jerry
--
Engineering is the art of making what you want from things you can get.
&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;&#2013266095;
```
```gokul_s1 wrote:
>
> I guess the answer does lie in the condition number of the matrix.
> Consider this matrix [1 10 10
>              0 1 10;
>              0 0 1 ]
> This matrix has all eigen values equal to 1...but it is still ill
> conditioned. It is quite interesting to know that the eigenvalues play no
> role in determining the stability of the inverse!
>
>
>
>

I would argue that eigenvalues do play a role. The eigenvalues of
interest are not those of the original matrix A, but of A'A. The
condition number of A can be defined as

max Eig(A'A)/ min Eig(A'A)
```
```On 2006-07-15 17:04:38 -0300, Greg Steele <gregsteele@speakeasy.net> said:

> gokul_s1 wrote:
>> I guess the answer does lie in the condition number of the matrix.
>> Consider this matrix [1 10 10
>>              0 1 10;
>>              0 0 1 ]
>> This matrix has all eigen values equal to 1...but it is still ill
>> conditioned. It is quite interesting to know that the eigenvalues play no
>> role in determining the stability of the inverse!
>>
>>
>>
>>
>
> I would argue that eigenvalues do play a role. The eigenvalues of
> interest are not those of the original matrix A, but of A'A. The
> condition number of A can be defined as
>
> max Eig(A'A)/ min Eig(A'A)

The matrix is not symmetric so the eigensystem is more complicated.
The eigenvectors are deficient.

When the matix is symmetric, or Herrmitian for complex values, then the
eigenvectors are guaranteed to be well behaved.

Looking at the singular values avoids this complication. It is the same
information that you get fron A'A and AA'.

```