tfp.experimental.linalg.simple_robustified_cholesky
Stay organized with collections
Save and categorize content based on your preferences.
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 that A + F is
positive definite, then E is not much larger than F.
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.
Args |
|---|
matrix
|
A batch of symmetric square matrices, with shape [..., n, n].
|
tol
|
Minimum for the diagonal. Default: 1e-6.
|
name
|
Python str name prefixed to Ops created by this function.
Default value: 'simple_robustified_cholesky'.
|
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.
|
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2023-11-21 UTC.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2023-11-21 UTC."],[],[],null,["# tfp.experimental.linalg.simple_robustified_cholesky\n\n\u003cbr /\u003e\n\n|-------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| [View source on GitHub](https://github.com/tensorflow/probability/blob/v0.23.0/tensorflow_probability/python/experimental/linalg/no_pivot_ldl.py#L112-L174) |\n\nUse `no_pivot_ldl` to robustify a Cholesky factorization. \n\n tfp.experimental.linalg.simple_robustified_cholesky(\n matrix, tol=1e-06, name='simple_robustified_cholesky'\n )\n\nGiven a symmetric matrix `A`, this function attempts to give a factorization\n`A + E = LL^T` where `L` is lower triangular, `LL^T` is positive definite, and\n`E` is small in some suitable sense. This is useful for nearly positive\ndefinite symmetric matrices that are otherwise numerically difficult to\nCholesky factor.\n\nThe algorithm proceeds as follows. The input is factored `A = LDL^T`, and the\ntoo-small diagonal entries of `D` are increased to the tolerance. Then `L @\nsqrt(D)` is returned.\n\nThis algorithm is similar in spirit to a true modified Cholesky factorization\n(\\[1\\], \\[2\\]). However, it does not use pivoting or other strategies to ensure\nstability, so may not work well for e.g. ill-conditioned matrices. Generally\nspeaking, a modified Cholesky factorization of a symmetric matrix `A` is a\nfactorization `P(A+E)P^T = LDL^T`, where `P` is a permutation matrix, `L` is\nunit lower triangular, and `D` is (block) diagonal and positive\ndefinite. Ideally such an algorithm would ensure the following:\n\n1. If `A` is sufficiently positive definite, `E` is zero.\n\n2. If `F` is the smallest matrix (in Frobenius norm) such that `A + F` is\n positive definite, then `E` is not much larger than `F`.\n\n3. `A + E` is reasonably well-conditioned.\n\n4. It is not too much more expensive than the usual Cholesky factorization.\n\nThe references give more sophisticated algorithms to ensure all of the\nabove. In the simple case where `A = LDL^T` does not require pivoting,\n`simple_robustified_cholesky` will agree and satisfy the above\ncriteria. However, in general it may fail to be stable or satisfy 2 and 3.\n\n#### References\n\n\\[1\\]: Nicholas Higham. What is a modified Cholesky factorization?\n\u003chttps://nhigham.com/2020/12/22/what-is-a-modified-cholesky-factorization/\u003e\n\n\\[2\\]: Sheung Hun Cheng and Nicholas Higham, A Modified Cholesky Algorithm Based\non a Symmetric Indefinite Factorization, SIAM J. Matrix Anal. Appl. 19(4),\n1097--1110, 1998.\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n| Args ---- ||\n|----------|-----------------------------------------------------------------------------------------------------------|\n| `matrix` | A batch of symmetric square matrices, with shape `[..., n, n]`. |\n| `tol` | Minimum for the diagonal. Default: 1e-6. |\n| `name` | Python `str` name prefixed to Ops created by this function. Default value: 'simple_robustified_cholesky'. |\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n\u003cbr /\u003e\n\n| Returns ------- ||\n|---------------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------|\n| `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. |\n\n\u003cbr /\u003e"]]
View source on GitHub