Differentiation of the Cholesky decomposition

By Iain Murray. 2016

47 citations recorded by the source corpus.

We review strategies for differentiating matrix-based computations, and derive symbolic and algorithmic update rules for differentiating expressions containing the Cholesky decomposition. We recommend new `blocked' algorithms, based on differentiating the Cholesky algorithm DPOTRF in the LAPACK library, which uses `Level 3' matrix-matrix operations from BLAS, and so is cache-friendly and easy to parallelize. For large matrices, the resulting algorithms are the fastest way to compute Cholesky derivatives, and are an order of magnitude faster than the algorithms in common usage. In some computing environments, symbolically-derived updates are faster for small matrices than those based on differentiating Cholesky algorithms. The symbolic and algorithmic approaches can be combined to get the best of both worlds.

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Hardware and Architecture

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Hardware and Architecture

Citations in the corpus

PIPPS: Flexible Model-Based Policy Search Robust to the Curse of Chaos (2019, methodology): “Obtaining the gradient dL/dΣ̂ is non-trivial, but (Murray, 2016) presents an overview.”
GPflow: A Gaussian Process Library using TensorFlow (2016, methodology): “The main part of the code was a C++ implementation of the blocked Cholesky algorithm proposed by Murray (2016).”
Asymptotically exact inference in differentiable generative models (2016, methodology): “This requires propagating partial derivatives through the Cholesky decomposition [25]; efficient implementations for this are present in many automatic differentiation frameworks including Theano.”
Spectral Inference Networks: Unifying Spectral Methods With Deep Learning (2018, background): “…for the matrix inverse and Cholesky decomposition are given by ¯ A = − C T ¯ CC T where C = A − 1 and ¯ Σ = L − T Φ ( L T ¯ L ) L − 1 where L is the Cholesky decomposition of Σ and Φ ( · ) is the operator that replaces the upper triangular of a matrix with its lower triangular transposed [15, 24].”
End-to-End Representation Learning for Correlation Filter Based Tracking (2017, background): “[14] and Murray [24] have presented back-propagation forms for the SVD and Cholesky decomposition respectively, enabling gradient descent to be applied to a network that computes the solution to either a system of linear equations or an eigenvalue problem.”
Auto-Differentiating Linear Algebra (2017, methodology): “It implements the expression from [16].”
Spectral Inference Networks: Unifying Deep and Spectral Learning (2018, background): “…and Cholesky decomposition are given by ¯ A = − C T ¯ CC T where C = A − 1 and ¯ Σ = L − T Φ ( L T ¯ L ) L − 1 where L is the Cholesky decomposition of Σ and Φ ( · ) is the operator that replaces the upper triangular of a matrix with its lower triangular transposed (Giles, 2008; Murray, 2016).”