The Rybicki–Press algorithm is a fast
algorithm for inverting a
matrix whose entries are given by , where [1] and where the are sorted in order.[2] The key observation behind the Rybicki-Press observation is that the
matrix inverse of such a matrix is always a
tridiagonal matrix (a matrix with nonzero entries only on the main diagonal and the two adjoining ones), and
tridiagonal systems of equations can be solved efficiently (to be more precise, in linear time).[1] 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.[3][4] The most common use of the algorithm is in the detection of periodicity in astronomical observations[verification needed], such as for detecting
quasars.[4]
The method has been extended to the Generalized Rybicki-Press algorithm for inverting matrices with entries of the form .[2] The key observation in the Generalized Rybicki-Press (GRP) algorithm is that the matrix is a
semi-separable matrix with rank (that is, a matrix whose upper half, not including the main diagonal, is that of some matrix with
matrix rank and whose lower half is also that of some possibly different rank matrix[2]) and so can be embedded into a larger
band matrix (see figure on the right), whose sparsity structure can be leveraged to reduce the computational complexity. As the matrix has a semi-separable rank of , the
computational complexity of solving the linear system or of calculating the determinant of the matrix scales as , thereby making it attractive for large matrices.[2]
The fact that matrix is a semi-separable matrix also forms the basis for celerite[5] library, which is a library for fast and scalable
Gaussian process regression in one dimension[6] with implementations in
C++,
Python, and
Julia. The celerite method[6] also provides an algorithm for generating samples from a high-dimensional distribution. The method has found attractive applications in a wide range of fields,[which?] especially in astronomical data analysis.[7][8]
^Rybicki, George B.; Press, William H. (October 1992). "Interpolation, realization, and reconstruction of noisy, irregularly sampled data". The Astrophysical Journal. 398: 169.
Bibcode:
1992ApJ...398..169R.
doi:
10.1086/171845.