On the conditioning of a Symmetric Toeplitz Matrix

Question

I have the following problem, which I hope is enough interesting for you to help me.

I have a matrix $A$ which is Toeplitz, Symmetric and Positive definite. Such a matrix is an autocorrelation matrix (https://en.wikipedia.org/wiki/Autocorrelation_matrix). Maybe is also important to say that $dim(A)>250$. In my case of analysis, $A$ is extremely ill-conditioned with values $\kappa(A) >10^{13}$. I'm trying to find a suitable way of preconditioning or regularization of the problem because that matrix is involved in a linear system of equations $Ax=b$.

Things that I have already tried, without success:

• Optimal and Superoptimal preconditioners for Toeplitz matrices (https://doi.org/10.1137/0613030).
• Use a Cholesky decomposition.
• Thikhonov Regularization (https://en.wikipedia.org/wiki/Tikhonov_regularization).

Any other ideas or suggestions will be extremely appreciated! Thanks!!!

Answer 1

Your matrix $A$ is numerically singular, and the problem $Ax = b$ cannot be solved, by any algorithm. Any preprocessing, postprocessing, iterative refinement, etc. will be useless.

Possible solutions:

1. use high precision arithmetics,
2. reformulate the problem.

As the second method you may consider different regulations; performing SVD , removing small singular values, and then solve least square problems; or something else. But in this case you are solving completely different problem, which has nothing to do with solving $Ax=b$. Such obtained result may be usefull or not, it highly dependents on the problem.