equinor / equinor/graphite-maps

Implement Sparse Cholesky approximatin by KL Minimization from Schäfer 2021

Open
#66 0 comments 0 reactions 1 assignee Claimed by @Blunde1 View on GitHub
Dominant language
Python
Stars
8
Forks
3
PR merge metrics
No merged PRs in 30d

Description

Algorithm C.1 in Appendix C of Schäfer yields an algorithm that is **linear in space and squared-log-linear in time**.

It is an approximate Cholesky factor to the true precision. But, provides KL-optimality guarantees among all approximations.

This means:
- Memory should be okay
- Computation time should be okay
- Error should be minimal.

The paper and the algorithm does not consider statistical estimation error. The framework is in-place, as we optimise the linear KR map (reverse-transpose Cholesky of precision) using a Gaussian reference, which is exactly the objective function of the paper.

The paper assumes the data stems from a reasonably smooth Gaussian kernel.

The paper is avilable on arXiv, and is heavily cited: https://arxiv.org/abs/2004.14455

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.