Rybicki Press algorithm

Extended Sparse Matrix arising from a ${\displaystyle 10\times 10}$ semi-separable matrix whose semi-separable rank is ${\displaystyle 4}$

The Rybicki–Press algorithm is a fast algorithm for inverting a matrix whose entries are given by ${\displaystyle A(i,j)=\exp(-a\vert t_{i}-t_{j}\vert )}$, where ${\displaystyle a\in \mathbb {R} }$ ^[1] and where the ${\displaystyle t_{i}}$ 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 ${\displaystyle A(i,j)=\sum _{k=1}^{p}a_{k}\exp(-\beta _{k}\vert t_{i}-t_{j}\vert )}$. ^[2] The key observation in the Generalized Rybicki-Press (GRP) algorithm is that the matrix ${\displaystyle A}$ is a semi-separable matrix with rank ${\displaystyle p}$ (that is, a matrix whose upper half, not including the main diagonal, is that of some matrix with matrix rank ${\displaystyle p}$ and whose lower half is also that of some possibly different rank ${\displaystyle p}$ 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 ${\displaystyle A\in \mathbb {R} ^{n\times n}}$ has a semi-separable rank of ${\displaystyle p}$, the computational complexity of solving the linear system ${\displaystyle Ax=b}$ or of calculating the determinant of the matrix ${\displaystyle A}$ scales as ${\displaystyle {\mathcal {O}}\left(p^{2}n\right)}$, thereby making it attractive for large matrices. ^[2]

The fact that matrix ${\displaystyle A}$ 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]}

See also

• Invertible matrix
• Matrix decomposition
• Multidimensional signal processing
• System of linear equations

References

1. Rybicki, George B.; Press, William H. (1995). "Class of fast methods for processing Irregularly sampled or otherwise inhomogeneous one-dimensional data". Physical Review Letters. 74 (7): 1060–1063. arXiv: comp-gas/9405004 . Bibcode:1995PhRvL..74.1060R. doi:10.1103/PhysRevLett.74.1060. PMID   10058924. S2CID   17436268.
2. Ambikasaran, Sivaram (2015-12-01). "Generalized Rybicki Press algorithm". Numerical Linear Algebra with Applications. 22 (6): 1102–1114. arXiv: 1409.7852 . doi:10.1002/nla.2003. ISSN   1099-1506. S2CID   1627477.
3. 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.
4. MacLeod, C. L.; Brooks, K.; Ivezic, Z.; Kochanek, C. S.; Gibson, R.; Meisner, A.; Kozlowski, S.; Sesar, B.; Becker, A. C. (2011-02-10). "Quasar Selection Based on Photometric Variability". The Astrophysical Journal. 728 (1): 26. arXiv: 1009.2081 . Bibcode:2011ApJ...728...26M. doi:10.1088/0004-637X/728/1/26. ISSN   0004-637X. S2CID   28219978.
5. "celerite — celerite 0.3.0 documentation". celerite.readthedocs.io. Retrieved 2018-04-05.
6. Foreman-Mackey, Daniel; Agol, Eric; Ambikasaran, Sivaram; Angus, Ruth (2017). "Fast and Scalable Gaussian Process Modeling with Applications to Astronomical Time Series". The Astronomical Journal. 154 (6): 220. arXiv: 1703.09710 . Bibcode:2017AJ....154..220F. doi: 10.3847/1538-3881/aa9332 . ISSN   1538-3881. S2CID   88521913.
7. Foreman-Mackey, Daniel (2018). "Scalable Backpropagation for Gaussian Processes using Celerite". Research Notes of the AAS. 2 (1): 31. arXiv: 1801.10156 . Bibcode:2018RNAAS...2...31F. doi: 10.3847/2515-5172/aaaf6c . ISSN   2515-5172. S2CID   102481482.
8. Parviainen, Hannu (2018). "Bayesian Methods for Exoplanet Science". Handbook of Exoplanets. Springer, Cham. pp. 1–24. arXiv: 1711.03329 . doi:10.1007/978-3-319-30648-3_149-1. ISBN   9783319306483.

External links

• Implementation of the Generalized Rybicki Press algorithm
• celerite library on GitHub