Square root of non-positive definite matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T10:59:15Z http://mathoverflow.net/feeds/question/43943 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43943/square-root-of-non-positive-definite-matrix Square root of non-positive definite matrix Anbu 2010-10-28T05:49:34Z 2010-10-28T09:10:08Z <p>Finding square root of matrices using Cholesky decomposition is limited to positive definite matrices. Any other method to find square root of matrix which has some diagonal values approximately zero (0.00000001) ?</p> http://mathoverflow.net/questions/43943/square-root-of-non-positive-definite-matrix/43944#43944 Answer by Will Jagy for Square root of non-positive definite matrix Will Jagy 2010-10-28T05:57:47Z 2010-10-28T06:19:09Z <p>Actually Cholesky can be shown to extend to semidefinite matrices:</p> <p><a href="http://en.wikipedia.org/wiki/Cholesky_decomposition#Proof_for_positive_semi-definite_matrices" rel="nofollow">http://en.wikipedia.org/wiki/Cholesky_decomposition#Proof_for_positive_semi-definite_matrices</a> </p> <p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.8064" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.8064</a></p> <p>Evidently implemented in R.</p> <p><a href="http://tolstoy.newcastle.edu.au/R/e6/help/09/04/9980.html" rel="nofollow">http://tolstoy.newcastle.edu.au/R/e6/help/09/04/9980.html</a> </p> <p>Meanwhile, covariance matrices are semidefinite, read some background at</p> <p><a href="http://en.wikipedia.org/wiki/Covariance_matrix" rel="nofollow">http://en.wikipedia.org/wiki/Covariance_matrix</a></p> http://mathoverflow.net/questions/43943/square-root-of-non-positive-definite-matrix/43955#43955 Answer by J. M. for Square root of non-positive definite matrix J. M. 2010-10-28T09:08:21Z 2010-10-28T09:08:21Z <p>Personally, I'm still a bit torn while giving this prescription. I am of the opinion that for truly reliable computation, one should use the singular value decomposition whenever one can tolerate the performance penalty; it truly is a very stable algorithm that can also be used to compute a bunch of important diagnostic quantities. (As an aside, if it is truly the square root you want, you could exploit the fact that having a singular value decomposition of $\mathbf{A}$ is effectively equivalent to having an eigendecomposition of either of $\mathbf{A}^T \mathbf{A}$ or $\mathbf{A}\mathbf{A}^T$)</p> <p>Having said this, if you're still dead-set on using Cholesky on a positive semidefinite matrix, while in exact arithmetic you are supposed to encounter a zero, what might actually happen with a (large enough) matrix with inexact entries is that your Cholesky routine encounters a tiny quantity not detected as zero, and the routine happily carries over this tiny quantity to divide other entries with. Disaster!</p> <p>The cure is that one does a symmetric pivoting $\mathbf{A}\to\mathbf{P}\mathbf{A}\mathbf{P}^T$ (where $\mathbf{P}$ is a permutation matrix), which reorders the diagonal entries of $\mathbf{A}$ (no off-diagonal entries are moved into the diagonal). This has the effect that the (near-)zero quantities are not encountered until one already has proceeded through the $r$-th iteration of the main loop in the Cholesky decomposition, where $r$ is the (perceived) rank of the matrix (this depends on what tolerance you have set, or the value such that anything whose absolute value is lower than it is effectively treated as zero).</p> <p>I have only given a brief sketch, since what I really should be doing is to point out this <a href="http://eprints.ma.man.ac.uk/1193/01/covered/MIMS_ep2008_56.pdf" rel="nofollow">paper</a> by Nick Higham, which discusses the nuances of Cholesky decomposition with symmetric pivoting for symmetric positive semidefinite matrices.</p>