Computing a nearest symmetric positive semidefinite matrix. (English) Zbl 0649.65026

Higham, Nicholas J.

Linear Algebra Appl. 103, 103-118 (1988).

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

Keywords:

nearest positive semidefinite matrix; 2-norm; Frobenius norm; bisection algorithm; positive definiteness; Numerical examples

Software:

LINPACK

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