Rybicki Press algorithm

The Rybicki–Press algorithm is a fast direct algorithm for inverting a matrix, whose entries are given by formula_1, where formula_2. It is a computational optimization of a general set of statistical methods developed to determine whether two noisy, irregularly sampled data sets are, in fact, dimensionally shifted representations of the same underlying function. The most common use of the algorithm is in the detection of periodicity in astronomical observations.
Recently, this method has been extended (Generalized Rybicki Press algorithm) for inverting matrices whose entries of the form formula_3. The key observation in the Generalized Rybicki Press (GPP) algorithm is that the matrix formula_4 is a semi-separable matrix with rank formula_5. More precisely, if the matrix formula_6 has a semi-separable rank is formula_5, the cost for solving the linear system formula_8 and obtaining the determinant of the matrix scales as formula_9, thereby making it extremely attractive for large matrices. This implementation of the GPP algorithm can be found here. The key idea is that the dense matrix formula_4 can be converted into a sparser matrix of a larger size (see figure on the right), whose sparsity structure can be leveraged to reduce the computational complexity.
The fact that matrix formula_4 is a semi-separable matrix also forms the basis for library, which is a library for fast and scalable Gaussian Process (GP) Regression in one dimension with implementations in C++, Python, and Julia. The method also provides an algorithm for generating samples from a high-dimensional distribution. The method has found attractive applications in a wide range of fields, especially in astronomical data analysis.