Cholesky factorization

We know that a positive definite matrix A has a unique symmetric square root F such that :

F ² = FF' = A

Now if we do not insist on symmetry, there is a very large set of (non symmetric) matrices G such that :

GG' = A

and which may also be regarded as "square roots" of A. The positive definite matrix A is then said to be factored into the "square" of its square root.

-----

One of these factorizations is of particular interest, both from theoretical and practical standpoints : the Cholesky factorization (or "Cholesky decomposition"), which is expressed as follows.

If A is only positive semidefinite, the diagonal elements of L can only be said to be non negative.

The Cholesky factorization can be symbolically represented by :

-----

The Cholesky factorization is the prefered numerical method for calculating :

    * The inverse,

    * and the determinant

of a positive definite matrix (in particular of a covariance matrix), as well as for the simulation of a random multivariate normal variable.

_____________________________________________________

In this Tutorial, we first identify a large set of non symmetric square roots of a positive definite matrix.

-----

We then describe two different ways of establishing the existence of the (unique) Cholesky factorization :

    * The first one is very much in the spirit of Linear Algebra, and establishes the existence of the Cholesky factorization recursively :

        - The factorization is assumed to exist and be unique for positive definite matrices of order (n - 1).

        - It is then proved that this implies that the same is true for positive definite matrices of order n.

    * The second way is more "pedestrian" and actually builds iteratively the matrix L column after column, and in each column, element after element.

Both demonstrations are constructive, and lead to actual numerical algorithms.

CHOLESKY FACTORIZATION

 ______________________________________________________

Related readings :