View source on GitHub |
Use no_pivot_ldl
to robustify a Cholesky factorization.
tfp.experimental.linalg.simple_robustified_cholesky(
matrix, tol=1e-06, name='simple_robustified_cholesky'
)
Given a symmetric matrix A
, this function attempts to give a factorization
A + E = LL^T
where L
is lower triangular, LL^T
is positive definite, and
E
is small in some suitable sense. This is useful for nearly positive
definite symmetric matrices that are otherwise numerically difficult to
Cholesky factor.
The algorithm proceeds as follows. The input is factored A = LDL^T
, and the
too-small diagonal entries of D
are increased to the tolerance. Then L @
sqrt(D)
is returned.
This algorithm is similar in spirit to a true modified Cholesky factorization
([1], [2]). However, it does not use pivoting or other strategies to ensure
stability, so may not work well for e.g. ill-conditioned matrices. Generally
speaking, a modified Cholesky factorization of a symmetric matrix A
is a
factorization P(A+E)P^T = LDL^T
, where P
is a permutation matrix, L
is
unit lower triangular, and D
is (block) diagonal and positive
definite. Ideally such an algorithm would ensure the following:
If
A
is sufficiently positive definite,E
is zero.If
F
is the smallest matrix (in Frobenius norm) such thatA + F
is positive definite, thenE
is not much larger thanF
.A + E
is reasonably well-conditioned.It is not too much more expensive than the usual Cholesky factorization.
The references give more sophisticated algorithms to ensure all of the
above. In the simple case where A = LDL^T
does not require pivoting,
simple_robustified_cholesky
will agree and satisfy the above
criteria. However, in general it may fail to be stable or satisfy 2 and 3.
References
[1]: Nicholas Higham. What is a modified Cholesky factorization? https://nhigham.com/2020/12/22/what-is-a-modified-cholesky-factorization/
[2]: Sheung Hun Cheng and Nicholas Higham, A Modified Cholesky Algorithm Based on a Symmetric Indefinite Factorization, SIAM J. Matrix Anal. Appl. 19(4), 1097–1110, 1998.
Returns | |
---|---|
triangular_factor
|
The lower triangular Cholesky factor, modified as above.
This will have shape [..., n, n] . Callers should check for nans or
other evidence of instability.
|