Skip to content

smrfeld/ggm-inversion

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

32 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Numerical inversion of precision matrix in Gaussian graphical model

Summary

See also the LaTeX version of the docs.

The goal of this library is to solve the problem of calculating the inverse of a symmetric positive definite matrix (e.g. a covariance matrix) when the constraints are mixed between the covariance matrix \Sigma and the precision matrix B = \Sigma^{-1}. In particular, constraints of the following form are considered:

\Sigma_{ij} = \theta_{ij}
B_{kl} = 0

where \theta_{ij} are some given numerical values. It is also considered that the number of constraints matches the number of degrees of freedom. An N x N symmetric matrix has N + (N choose 2) = N * (N+1) / 2 degrees of freedom.

  • If all the constraints were on \Sigma, this problem would be trivially solved by computing the inverse B = \Sigma^{-1}.
  • For small matrices, this problem can be solved analytically - for large matrices this is infeasible.
  • In this library, the problem is solved by optimization.

Two approaches

There are two main approaches:

  1. Apply root finding to the matrix equation system
B * \Sigma - I = 0
  1. Minimize the L2 loss:
\sum_{kl} ((B^{-1})_{kl} - \Sigma_{kl})^2

If an initial guess sufficiently close to the inverse is available, then the first root finding method is preferred. See the Newton's root finding method example.

Minimizing the L2 loss is slower but more robust if such a guess is not available. Currently, only first order methods (in the gradients) are included. Two classes of optimizers are supported:

Example figures

Minimization of the residuals from Newton's root finding method: drawing

Convergence of the covariance matrix during minimizing the L2 loss: drawing

Convergence of the precision matrix during minimizing the L2 loss: drawing

Dependencies

Building

Build out of a dedicated build directory;

mkdir build
cd build
cmake ..
make
make install

Tests

See the test directory, which can be built in the same way:

cd test
mkdir build
cd build
cmake ..

About

Numerical inversion of precision matrix in Gaussian graphical model

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published