What is the Cholesky Decomposition used for?

Question

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?

Answer 1

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.

Answer 2

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.