9
$\begingroup$

I'm given a matrix. How do I find the nearest (or a near) positive definite from it?

The matrix can have complex eigenvalues, not be symmetric, etc. However, all its entries are real valued. The resulting matrix from the algorithm must be positive definite, with all its entries real valued only. Symmetry is a plus, but not necessary. I have no preference toward the metric used. I prefer a pragmatic(relatively easy to programme) approach. It doesn't have to be optimal.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ The most common definition of "positive definite" includes symmetric. Are you specifically looking for a symmetric matrix, or would a non-symmetric matrix with eigenvalues that are real and positive be acceptable? What about a matrix that has complex eigenvalues with positive real parts? $\endgroup$
    – Brian Borchers
    Dec 3, 2018 at 3:39
  • 1
    $\begingroup$ What definition of "nearest" are you interested in? With respect to the spectral norm? Frobenius norm? Some other measure? $\endgroup$
    – Brian Borchers
    Dec 3, 2018 at 3:59
  • $\begingroup$ @BrianBorchers I've edited the question. I have no preference for the norm, as long as the requirements explained above are satisfied. $\endgroup$
    – An old man in the sea.
    Dec 3, 2018 at 9:45
  • $\begingroup$ Is this the sort of thing you're looking for? stat.ethz.ch/R-manual/R-devel/library/Matrix/html/nearPD.html (Incidentally, nearPD replaces $X$ with $\frac12(X+X^\top)$ for non-symmetric $X$.) $\endgroup$
    – Kirill
    Dec 3, 2018 at 13:30
  • 1
    $\begingroup$ @Anoldmaninthesea. I think it's based on this algorithm: maths.manchester.ac.uk/~higham/narep/narep369.pdf, and it looks pretty simple. $\endgroup$
    – Kirill
    Dec 3, 2018 at 14:31

2 Answers 2

Reset to default
20
$\begingroup$

Quick sketch of an answer for the Frobenius norm:

  1. Replace $X$ with the closest symmetric matrix, $Y=\frac12 (X+X^\top)$.
  2. Take an eigendecomposition $Y=QDQ^\top$, and form the diagonal matrix $D_+=\max(D,0)$ (elementwise maximum).
  3. The closest symmetric positive semidefinite matrix to $X$ is $Z=QD_+Q^\top$.
  4. The closest positive definite matrix to $X$ does not exist; any matrix of the form $Z+\varepsilon I$ is positive definite for $\varepsilon>0$. There is no minimum, just an infimum. Positive definite matrices are not a closed set.

To prove (1) and (3), you can use the fact that the decomposition of a matrix into a symmetric and antisymmetric part is orthogonal. In particular, this implies that we can minimize in two succesive steps like we did.

To prove (2), use the Wielandt-Hoffmann theorem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ For (3), in what sense is $Z$ closest to $X$? Is it $\min \|X-Z\|_2$? @federico-poloni $\endgroup$
    – KRL
    May 9, 2020 at 22:14
  • 3
    $\begingroup$ @KRL This answer was for the Frobenius norm, $\|X-Z\|_F = \left(\sum_{i,j} |X-Z|_{ij}^2\right)^{1/2}$, as stated in the first row. The proofs were stated very briefly here, but one key idea is that this norm is induced by the scalar product $\left\langle A,B\right\rangle = \operatorname{Tr}(A^TB)$, so this is a scalar product space and one can speak of "orthogonal decomposition". $\endgroup$
    – Federico Poloni
    May 10, 2020 at 6:44
3
$\begingroup$

If you're ok with positive semi-definite matrices, then you can refer to this paper, which I think is what Frederico's answer also explains:

Higham NJ. Computing a nearest symmetric positive semidefinite matrix. Linear Algebra and its Applications. 1988 May;103(C):103-118.

A python implementation can be found in this answer, which also provides a link to a maltab implementation.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Welcome to Computational Science! Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. $\endgroup$
    – Anton Menshov ♦
    Feb 9, 2021 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.