What's the best way to make a symmetric matrix positive definite?

Question

Assume that you have a matrix $X \in \mathbb R^{m \times m}$ and it's symmetric, but it's not positive definite.

What's the best way to turn the matrix $X$ into a positive definite matrix?

I have a suggestion. This suggestion takes a very long time, to increase every diagonal of $X$ with $+10$ for every iteration.

eigenvalues = eig(X);
how_many_negative_eigenvalues = length(find(eigenvalues < 0))
while(how_many_negative_eigenvalues > 0)
  disp('Negative eigenvalues - Use regalarization');
  X = X + 10*eye(size(X));
  eigenvalues = eig(X);
  how_many_negative_eigenvalues = length(find(eigenvalues < 0))
end
disp('No negative eigenvalues - Regalarization done');

Can this be done in a faster way?

Answer 1

There is no unique nearest positive definite matrix, but you can make an $\epsilon$-close one. Let $A$ be a real symmetric matrix with eigendecomposition $A = U\Lambda U^\top$ and eigenvalues $\lambda_k$, $k=1,\dots,n$. Then the nearest semidefinite matrix is given by $$A_{\geq0} = U\Lambda_{\geq0}U^\top,$$ where the diagonal elements of $\Lambda_{\geq 0}$ are given by $\max(0, \lambda_k)$, $k=1,\dots,n$. To make this construction positive, instead of replacing the eigenvalues with $0$, replace them with a positive number $\epsilon>0$, i.e., $\max(\epsilon, \lambda_k)$. There is no unique nearest positive matrix since you can make $\epsilon$ arbitrarily small.

For example, consider a matrix with eigenvalues $\Lambda = \mathrm{diag}(10,1,0,-10)$. This algorithm replaces these with $\Lambda_{>0} = \mathrm{diag}(10,1,\epsilon, \epsilon)$.