Computing a nearest symmetric positive semidefinite matrix (Q1105980)

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.