Perturbation for Eigenvalues and Singular values

06 Sep 2015 NUS mathematicians reported that strong relative perturbation bounds are developed for eigenvalues and singular values of totally nonpositive matrices.

Relative perturbation analysis is an active research topic of great interest in scientific computing. In recent years, much work has been done for the derivation of sharper perturbation bounds than the traditional ones by restricting perturbations to those that preserve certain structures. In particular, strong relative perturbation results have been obtained for a few special classes of structured matrices that have been represented by a proper set of parameters instead of matrix entries.

Sign regular matrices have found a lot of applications to variation diminishing transformations, spline interpolation problems, and statistics and have been studied extensively. Two important classes of sign regular matrices are totally nonnegative matrices and totally nonpositive matrices. It is known that all the eigenvalues and singular values of a nonsingular totally nonnegative matrix are accurately determined by its n² parametrization. Relative perturbation analysis has been provided to show that tiny perturbations of these n² parameters produce tiny variations of all the eigenvalues and singular values, independent of any conventional condition number. These bounds demonstrate that much more accurate algorithms than the traditional ones are possible to compute eigenvalues and singular values of totally nonnegative matrices. But, until now the only class of nonsymmetric matrices all of whose eigenvalues are computed with high relative accuracy is the class of totally nonnegative matrices and their variants.

A team led by Prof CHU Delin from the Department of Mathematics in NUS has shown that sign regular matrices including totally nonnegative and totally nonpositive matrices enjoy some same excellent numerical properties. Their recent work is to provide another class of nonsymmetric matrices all of whose eigenvalues and singular values may be computed accurately. Recently, they have successfully developed strong relative perturbation bounds for all the eigenvalues and singular values of a class of nonsymmetric matrices, i.e., the class of totally nonpositive matrices. Their main contributions include: 1) developed a structure-preserving relative perturbation theory for the eigenvalue and singular value problems of totally nonpositive matrices. They showed that there are exactly n² independent variables that parameterize the set of nonsingular totally nonpositive matrices of size ; 2) presented the relative perturbation results for eigenvalues and singular values of a nonsingular totally nonpositive matrix. It is shown that if each parameter of such a matrix has a relative error bounded by ϵ , then all its eigenvalues and singular values have relative errors of order O(n³ ϵ), independent of any conventional condition number. Therefore, by virtue of its new parametrization, all the eigenvalues and singular values of a nonsingular totally nonpositive matrix can be computed as accurately as they deserve, as illustrated in tables below for a totally nonpositive matrix:

Figure shows the new submission represents a giant step in the study of totally nonpositive matrices. [Image credit: Chu Delin]

Reference

Chu D. “Relative Perturbation analysis for eidenvalues and singular values of totally nonpositive matrices.” Siam J. Matrix Anal. Appl 36 (2) (2015) 476.