zbMATH — the first resource for mathematics

Computing a nearest symmetric positive semidefinite matrix. (English) Zbl 0649.65026
The problem of computing a nearest positive semidefinite matrix (notation used $$X\geq 0)$$ to an arbitrary real matrix A is considered. The criterion of approximation is the distance $$\delta (A)=\min_{X=X^ T\geq 0}\| A-X\|$$ where the norm is chosen to be either Frobenius or 2-norm. The paper consists of two parts. In the first part the author proves that the nearest unique positive approximant $$X_ F$$ of A in the Frobenius norm is $$X_ F=(B+H)/2,$$ where $$B=(A+A^ T)/2$$ and H is the symmetric polar factor of B, and the corresponding distance from A is $$\delta^ 2_ F(A)=\sum_{\lambda_ i(B)<0}\lambda^ 2_ i(B)+\| C\|_ F^ 2,$$ where $$C=(A-A^ T)/2.$$
In the second part the problem is studied in 2-norm. Examining from a computational view point the famous Halmos formula for the distance $$\delta_ 2(A)$$ the author proposes two algorithms to estimate $$\delta_ 2(A)$$ as well as the positive approximant (which is not unique in general): (i) an efficient bisection algorithm of low accuracy that is $$\alpha \geq \delta_ 2(A)\leq \alpha +2\max \{f\alpha,tol\},$$ where f is a relative error tolerance and tol is an absolute error tolerance; (ii) a hybrid Newton-bisection type algorithm for high accuracy computations. The problem of computational testing for positive definiteness as well as some details concerning the implementation of algorithm (ii) are discussed. Numerical examples are presented.
Reviewer: V.G.Rumchev

MSC:
 65F30 Other matrix algorithms (MSC2010) 15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory 15B48 Positive matrices and their generalizations; cones of matrices 65K05 Numerical mathematical programming methods 90C25 Convex programming
LINPACK
Full Text:
References:
 [1] Bouldin, R., Positive approximants, Trans. amer. math. soc., 177, 391-403, (1973) · Zbl 0264.47020 [2] Bouldin, R., Operators with a unique positive near-approximant, Indiana univ. math. J., 23, 421-427, (1973) · Zbl 0269.47010 [3] Byers, R., A bisection method for measuring the distance of a stable matrix to the unstable matrices, (1986), Dept. of Mathematics, North Carolina State Univ Raleigh, Manuscript [4] Cybenko, G.; Van Loan, C.F., Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix, SIAM J. sci. statist. comput., 7, 123-131, (1986) · Zbl 0626.65030 [5] Demmel, J.W., On condition numbers and the distance to the nearest III-posed problem, Numer. math., 51, 251-289, (1987) · Zbl 0597.65036 [6] Dongarra, J.J.; Bunch, J.R.; Moler, C.B.; Stewart, G.W., \sclinpack users’ guide, (1979), SIAM Publ Philadelphia · Zbl 0476.68025 [7] Fan, K.; Hoffman, A.J., Some metric inequalities in the space of matrice, Proc. amer. math. soc., 6, 111-116, (1955) · Zbl 0064.01402 [8] Fletcher, R., Semi-definite matrix constraints in optimization, SIAM J. control optim., 23, 493-513, (1985) · Zbl 0567.90088 [9] Friedland, S.; Nocedal, J.; Overton, M.L., The formulation and analysis of numerical methods for inverse eigenvalue problems, SIAM J. numer. anal., 24, 634-667, (1987) · Zbl 0622.65030 [10] Gil, P.E.; Murray, W.; Wright, M.H., Practical optimization, (1981), Academic London [11] Golub, G.H.; Van Loan, C.F., Matrix computations, (1983), Johns Hopkins U.P Baltimore · Zbl 0559.65011 [12] Halmos, P.R., Positive approximants of operators, Indiana univ. math. J., 21, 951-960, (1972) · Zbl 0263.47018 [13] Higham, N.J., Computing the polar decomposition—with applications, SIAM J. sci. statist. comput., 7, 1160-1174, (1986) · Zbl 0607.65014 [14] N.J. Higham, The symmetric procrusters problem, BIT, to appear. [15] Meinguet, J., Refined error analyses of Cholesky factorization, SIAM J. numer. anal., 20, 1243-1250, (1983) · Zbl 0528.65014 [16] Parlett, B.N., Progress in numerical analysis, SIAM rev., 20, 443-456, (1978) · Zbl 0408.65002 [17] Parlett, B.N., The symmetric eigenvalue problem, (1980), Prentice-Hall Englewood Cliffs, N.J · Zbl 0431.65016 [18] Press, W.H.; Flannery, B.P.; Teukolsky, S.A.; Vetterling, W.T., Numerical recipes: the art of scientific computing, (1986), Cambridge U.P Cambridge · Zbl 0587.65003 [19] Strang, G., Introduction to applied mathematics, (1986), Wellesley-Cambridge Press Wellesley, Mass · Zbl 0618.00015 [20] Van Loan, C.F.; Datta, B.N., How near is a stable matrix to an unstable matrix?, Linear algebra and its role in systems theory, Vol. 47, 465-478, (1985), Amer. Math. Soc. [21] Wilkinson, J.H., A priori error analysis of algebraic processes, (), 629-640, Moscow · Zbl 0197.13301
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.