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. Would appreciate a reply Thanks -Goks

# Deconvolution

Started by ●July 12, 2006

Reply by ●July 12, 20062006-07-12

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. > > Would appreciate a reply > > Thanks > -GoksThink about the inverse of 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.

Reply by ●July 12, 20062006-07-12

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. > > Would appreciate a reply > > Thanks > -GoksHello 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

Reply by ●July 12, 20062006-07-12

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!

Reply by ●July 12, 20062006-07-12

gokul_s1 wrote:> 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 ...Your tabs don't act like my tabs. Please use spaces. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������

Reply by ●July 15, 20062006-07-15

gokul_s1 wrote:> 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! > > > >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)

Reply by ●July 15, 20062006-07-15

On 2006-07-15 17:04:38 -0300, Greg Steele <gregsteele@speakeasy.net> said:> gokul_s1 wrote: >> 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! >> >> >> >> > > 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'.