Cholesky decomposition

Cholesky decomposition#

Statement#

The Cholesky decomposition of a Hermitian positive-definite matrix \(A\), is a decomposition of the form

\[A=LL^\dagger\]

where \(L\) is a lower triangular matrix with real and positive diagonal entries, and \(L^\dagger\) denotes the conjugate transpose of \(L\).

Theorem 2 (Orthogonal-Projection-Theorem)

Given \(y \in \mathbb R^n\) and linear subspace \(S \subset \mathbb R^n\), there exists a unique solution to the minimization problem

\[\hat y := \argmin_{z \in S} \|y - z\|\]

The minimizer \(\hat y\) is the unique vector in \(\mathbb R^n\) that satisfies

\(\hat y \in S\)
\(y - \hat y \perp S\)

The vector \(\hat y\) is called the orthogonal projection of \(y\) onto \(S\).

Proof#

numerical solution of linear equations#

Proof for positive semi-definite matrices#

Proof by QR decomposition#

The algorithm#

Efficiency#

Applications#

Monte Carlo simulation#

Matrix inversion#

## solve A(4,3)*B(3,2)=C(4,2)
import numpy as np
from numpy.linalg import inv, matrix_rank, det
from numpy import dot, transpose

a = np.array([[1., 2., 3.], [3., 5., 3.]])
aT_a = dot(transpose(a),a)
print(aT_a)
print(det(aT_a))
print('rank:',matrix_rank(aT_a))
ainv = inv(aT_a)
print(ainv)
np.allclose(dot(ainv, aT_a), np.eye(3))

[[10. 17. 12.]
 [17. 29. 21.]
 [12. 21. 18.]]
1.6710489201527266e-14
rank: 2
[[ 4.84725486e+15 -3.23150324e+15  5.38583873e+14]
 [-3.23150324e+15  2.15433549e+15 -3.59055916e+14]
 [ 5.38583873e+14 -3.59055916e+14  5.98426526e+13]]

False