Diagonally Perturbing a Symmetric Matrix to Make It Positive Definite

Suppose $A$ is a matrix that is symmetric but not positive definite. What is the best way to perturb the diagonal to make $A$ positive definite? We want to compute a vector $d$ such that

$\notag A(d) = A + D, \quad D = \mathrm{diag}(d),$

is positive definite. Since the positive definite matrices form an open set there is no minimal $d$ , so we relax the requirement to be that $A$ is positive semidefinite. The perturbation $D$ needs to make any negative eigenvalues of $A$ become nonnegative. We will require all the entries of $d$ to be nonnegative. Denote the eigenvalues of $A$ by $\lambda_n(A) \le \lambda_{n-1}(A) \le \cdots \le \lambda_1(A)$ and assume that $\lambda_n(A) < 0$ .

A natural choice is to take $D$ to be a multiple of the identity matrix. For $d_i \equiv \delta$ , $A(d)$ has eigenvalues $\lambda_i + \delta$ , and so the smallest possible $\delta$ is $\delta = - \lambda_n(A)$ . This choice of $D$ shifts all the diagonal elements by the same amount, which might be undesirable for a matrix with widely varying diagonal elements.

When the diagonal entries of $A$ are positive another possibility is to take $d_i = \alpha a_{ii}$ , so that each diagonal entry undergoes a relative perturbation of size $\alpha$ . Write $D_A = \mathrm{diag}(a_{ii})$ and note that $C = D_A^{-1/2}A D_A^{-1/2}$ is symmetric with unit diagonal. Then

$\notag A + \alpha D_A = D_A^{1/2}(C + \alpha I)D_A^{1/2}.$

Since $A + \alpha D_A$ is positive semidefinite if and only if $C + \alpha I$ is positive semidefinite, the smallest possible $\alpha$ is $\alpha = -\lambda_n(C)$ .

More generally, we can treat the $d_i$ as $n$ independent variables and ask for the solution of the optimization problem

$\notag \min \|d\| ~~\mathrm{subject~to}~~ A + \mathrm{diag}(d) ~\mathrm{positive~semidefinite}, ~d \ge 0. \qquad(\dagger)$

Of particular interest are the norms $\|d\|_1 = \sum_i d_i = \mathrm{trace}(D)$ (since $d\ge0)$ and $\|d\|_\infty = \max_i d_i$ .

If $A+D$ is positive semidefinite then from standard eigenvalue inequalities,

$\notag 0 \le \lambda_n(A+D) \le \lambda_n(A) + \lambda_1(D),$

so that

$\notag \max_i d_i \ge -\lambda_n(A).$

Since $d_i \equiv -\lambda_n(A)$ satisfies the constraints of $(\dagger)$ , this means that this $d$ solves $(\dagger)$ for the $\infty$ -norm, though the solution is obviously not unique in general.

For the $1$ – and $2$ -norms, $(\dagger)$ does not have an explicit solution, but it can be solved by semidefinite programming techniques.

Another approach to finding a suitable $D$ is to compute a modified Cholesky factorization. Given a symmetric $A$ , such a method computes a perturbation $E$ such that $A + E = R^TR$ for an upper triangular $R$ with positive diagonal elements, so that $A + E$ is positive definite. The methods of Gill, Murray, and Wright (1981) and Schnabel and Eskow (1990) compute a diagonal $E$ . The cost in flops is essentially the same as that of computing a Cholesky factorization ( $n^3/3$ ) flops), so this approach is likely to require fewer flops than computing the minimum eigenvalue or solving an optimization problem, but the perturbations produces will not be optimal.

Example

We take the $5\times 5$ Fiedler matrix

>> A = gallery('fiedler',5)
A =
     0     1     2     3     4
     1     0     1     2     3
     2     1     0     1     2
     3     2     1     0     1
     4     3     2     1     0

The smallest eigenvalue is $-5.2361$ , so $A+D$ is positive semidefinite for $D_1 = 5.2361I$ . The Gill–Murray–Wright method gives $D_{\mathrm{GMW}}$ with diagonal elements

2.0000e+01   4.6159e+00   1.3194e+00   2.5327e+00   1.0600e+01

and has $\lambda_5(A+D_{\mathrm{GMW}}) = 0.5196$ while the Schnabel–Eskow method gives $D_{\mathrm{SE}}$ with diagonal elements

6     6     6     6     6

and has $\lambda_5(A+D_{\mathrm{SE}}) = 0.7639$ . If we increase the diagonal elements of $D_1$ by 0.5 to give comparable smallest eigenvalues for the perturbed matrices then we have

	$\Vert d\Vert_{\infty}$	$\Vert d \Vert_1$
Shift	5.2361	26.180
Gill-Murray-Wright	20.000	39.068
Schnabel–Eskow	6.000	30.000

References

Roger Fletcher, Semi-Definite Matrix Constraints in Optimization, SIAM J. Control Optim. 23 (4), 493–513, 1985.
Philip Gill, Walter Murray, and Margaret Wright, Practical Optimization, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2020. Republication of book first published by Academic Press, 1981.
Robert Schnabel and Elizabeth Eskow, A Revised Modified Cholesky Factorization Algorithm, SIAM J. Optim. 9(4), 1135–1148, 1999.

Example

References

Share this:

Related

Leave a Reply Cancel reply