5
$\begingroup$

It seems like a very niche case, where a matrix must be Hermitian positive semi-definite. In the case of reals, it simply must be symmetric.

How often does one have a positive semi-definite matrix in which taking it's Cholesky Decomposition has a significant usage?

$\endgroup$

closed as unclear what you're asking by Axoren, Claude Leibovici, haqnatural, Daniel W. Farlow, user98602 Sep 29 '16 at 17:05

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ That is not at all a niche case. Hermitian positive semidefinite matrices are everywhere and are so important. For example, if $A$ is any real matrix, then $A^T A$ is positive semidefinite. Try reading some of Gilbert Strang's books that emphasize the ubiquity of $A^T CA$. $\endgroup$ – littleO Sep 28 '16 at 1:27
  • $\begingroup$ @littleO Could you give a real world practical example in which the Cholesky decomposition of $A^TA$ has a practical application? I've had someone try to convince me with this line of thought but I feel like that alone is incomplete. Generally, if I'm working with $A$ as a linear transformation, $A^T A$ will have a different meaning. $\endgroup$ – Axoren Sep 28 '16 at 1:30
  • $\begingroup$ The focus seems to be on whether positive definite symmetric matrices are commonly needed (they are). The Cholesky factorization will likely fail for semi-definite but not definite forms. $\endgroup$ – hardmath Sep 28 '16 at 1:40
  • $\begingroup$ I will have to think on both given answers for a while. These are definitely cases in which we can be certain that we have a matrix matching the criteria. They don't immediately answer why the Cholesky decomposition benefits them, however. The answers seemed to focus on where $A^TA$ will appear, rather than what the Cholesky factorization brings to the table in those cases. "Why would you do Cholesky factorization in this case?" has not been expressly addressed by either question. $\endgroup$ – Axoren Sep 28 '16 at 2:01
  • $\begingroup$ I understood your wording of the Question to focus on whether applications permitting a Cholesky decomposition are really common in practice. I considered posting some remarks about the advantages of this factorization, but concluded it was not of concern to you. $\endgroup$ – hardmath Sep 28 '16 at 22:27
8
$\begingroup$

Symmetric and positive definite matrices that can be Cholesky factored appears in many applications:

  • Normal equations for least squares problems.
  • Discretizations of self adjoint partial differential equation boundary value problems.
  • Hessians of convex functions (in many cases the Hessian is made to be convex) in optimization.
  • Systems of equations arising from the primal-dual barrier method for linear programming.

As to why one would use the Cholesky factorization rather than another matrix factorization such as the LU factorization, the answer is that Cholesky factorization is substantially faster than LU factorization because it can exploit the symmetry of the matrix and because pivoting isn't required. Cholesky factorization of sparse positive definite matrices is fairly simple in comparison with LU factorization because of the need to do pivoting in LU factorization.

$\endgroup$
  • 1
    $\begingroup$ Nice to see you here, my SciComp.SE colleague! $\endgroup$ – hardmath Sep 28 '16 at 1:37
1
$\begingroup$

Positive semidefinite matrices are everywhere, largely due to the ubiquity of the pattern $A^T C A$ (which is emphasized by Gilbert Strang). For example, in least squares problems we find $x$ to minimize $(1/2)\|Ax - b\|_2^2$. To solve this problem, set the gradient equal to zero: $$ A^T(Ax- b) = 0. $$ This is just one of many examples.

$\endgroup$

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