Superoptimal approximation for unbounded symbols (Q2465322)

The paper focusses on the superoptimal Frobenius approximation of Toeplitz matrices in connection with the case of unbounded symbols, the contribution being to discuss and explain the reasons behind the bad approximation of the small eigenvalues given by the superoptimal preconditioners and to show that the only situation where the superoptimal approach can become competitive is when we add some noise. The first part is an overview concerning the superoptimal preconditioner proposed by \textit{E. E. Tyrtyshnikov} [SIAM J. Matrix Anal. Appl. 13, No. 2, 459--473(1992; Zbl 0774.65024)]. In the second part one introduces the necessary definitions and one discusses the quality of the approximation for various well-known preconditioners: natural or strang, optimal and superoptimal, showing the relationship between the relative and absolute approximations of the generating functions, and the corresponding approximations of the generated Toeplitz matrices. The third part contains numerical experiments on how the distribution of the eigenvalues of the superoptimal approximation shown in the second part can be favorable for solving ill-conditioned Toeplitz systems with unbounded symbols. One focusses in the solution of linear systems when the right-hand side is corrupted by noise and in the classical case where the noise is not present. The results are critically discussed, one of the main conclusions being that the case of Toeplitz systems with Fisher-Hartwig singularities is equivalent (up to a positive scaling and in a spectral asymptotic sense) to the case of symmetric burring operators coming from classical signal/image processing. Moreover, although the paper is mainly devoted to 1D Toeplitz systems, the results can be extended to multidimensional Toeplitz problems. The last part is devoted to the concluding remarks.