RESTORING DEFINITENESS VIA SHRINKING, WITH AN APPLICATION TO CORRELATION MATRICES WITH A FIXED BLOCK∗

Abstract. Indefinite estimates of positive semidefinite matrices arise in many data analysis ap-plications involving covariance matrices and correlation matrices. We develop a method for restoring positive semidefiniteness of an indefinite estimate based on the process of shrinking, which finds a convex linear combination S(α) = αM1 + (1 − α)M0 of the original matrix M0 and a target pos-itive semidefinite matrix M1. We describe three algorithms for computing the optimal shrinking parameter α ∗ = min{α ∈ [0, 1] : S(α) is positive semidefinite}. One algorithm is based on the bisec-tion method, with the use of Cholesky factorization to test definiteness, a second employs Newton’s method, and a third finds the smallest eigenvalue of a symmetric definite generalized eigenvalue problem. We show that weights that reflect confidence in the individual entries of M0 can be used to construct a natural choice of the target matrix M1. We treat in detail a problem variant in which a positive semidefinite leading principal submatrix of M0 remains fixed, showing how the fixed block can be exploited to reduce the cost of the bisection and generalized eigenvalue methods. Numerical experiments show that when applied to estimates of correlation matrices shrinking can be at least an order of magnitude faster than computing the nearest correlation matrix