Suppose is a matrix that is symmetric but not positive definite. What is the best way to perturb the diagonal to make
positive definite? We want to compute a vector
such that
is positive definite. Since the positive definite matrices form an open set there is no minimal , so we relax the requirement to be that
is positive semidefinite. The perturbation
needs to make any negative eigenvalues of
become nonnegative. We will require all the entries of
to be nonnegative. Denote the eigenvalues of
by
and assume that
.
A natural choice is to take to be a multiple of the identity matrix. For
,
has eigenvalues
, and so the smallest possible
is
. This choice of
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 are positive another possibility is to take
, so that each diagonal entry undergoes a relative perturbation of size
. Write
and note that
is symmetric with unit diagonal. Then
Since is positive semidefinite if and only if
is positive semidefinite, the smallest possible
is
.
More generally, we can treat the as
independent variables and ask for the solution of the optimization problem
Of particular interest are the norms (since
and
.
If is positive semidefinite then from standard eigenvalue inequalities,
so that
Since satisfies the constraints of
, this means that this
solves
for the
-norm, though the solution is obviously not unique in general.
For the – and
-norms,
does not have an explicit solution, but it can be solved by semidefinite programming techniques.
Another approach to finding a suitable is to compute a modified Cholesky factorization. Given a symmetric
, such a method computes a perturbation
such that
for an upper triangular
with positive diagonal elements, so that
is positive definite. The methods of Gill, Murray, and Wright (1981) and Schnabel and Eskow (1990) compute a diagonal
. The cost in flops is essentially the same as that of computing a Cholesky factorization (
) 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 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 , so
is positive semidefinite for
. The Gill–Murray–Wright method gives
with diagonal elements
2.0000e+01 4.6159e+00 1.3194e+00 2.5327e+00 1.0600e+01
and has while the Schnabel–Eskow method gives
with diagonal elements
6 6 6 6 6
and has . If we increase the diagonal elements of
by 0.5 to give comparable smallest eigenvalues for the perturbed matrices then we have
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.