Rybicki Press algorithm: Difference between revisions

Content deleted Content added

Inline

Revision as of 04:56, 2 October 2021

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

The fact that matrix $A$ is a semi-separable matrix also forms the basis for celerite^[6]^{[inappropriate external link?]} library, which is a library for fast and scalable Gaussian process regression in one dimension^[7] with implementations in C++, Python, and Julia. The celerite method^[7] 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.^[8]^[9]

References

^ ^a ^b 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
^ ^a ^b ^c ^d 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.
^ 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.
^ ^a ^b 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.
^ "sivaramambikasaran/ESS". GitHub. Retrieved 2018-04-05.
^ "celerite — celerite 0.3.0 documentation". celerite.readthedocs.io. Retrieved 2018-04-05.
^ ^a ^b 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.{{cite journal}}: CS1 maint: unflagged free DOI (link)
^ Foreman-Mackey, Daniel (2018). "Scalable Backpropagation for Gaussian Processes using Celerite". Research Notes of the AAS. 2 (1): 31. arXiv:1801.10156. Bibcode:2018RNAAS...2a..31F. doi:10.3847/2515-5172/aaaf6c. ISSN 2515-5172.{{cite journal}}: CS1 maint: unflagged free DOI (link)
^ 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

[:2-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

[:3-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.

[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.

[:0-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.

[5] "sivaramambikasaran/ESS". GitHub. Retrieved 2018-04-05.

[6] "celerite — celerite 0.3.0 documentation". celerite.readthedocs.io. Retrieved 2018-04-05.

[:1-7] 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.{{cite journal}}: CS1 maint: unflagged free DOI (link)

[8] Foreman-Mackey, Daniel (2018). "Scalable Backpropagation for Gaussian Processes using Celerite". Research Notes of the AAS. 2 (1): 31. arXiv:1801.10156. Bibcode:2018RNAAS...2a..31F. doi:10.3847/2515-5172/aaaf6c. ISSN 2515-5172.{{cite journal}}: CS1 maint: unflagged free DOI (link)

[9] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 4: / Line 4: @@
 }}
 [[File:Extended_Sparse_Matrix.png|thumb|Extended Sparse Matrix arising from a <math>10 \times 10</math> semi-separable matrix whose semi-separable rank is <math>4</math>.]]
-The '''Rybicki–Press algorithm''' is a fast direct [[algorithm]] for inverting a [[Matrix (mathematics)|matrix]], whose entries are given by <math>A(i,j) = \exp(-a \vert t_i - t_j \vert)</math>, where <math>a \in \mathbb{R}</math>.<ref>{{citation
+The '''Rybicki–Press algorithm''' is a fast [[algorithm]] for inverting a [[Matrix (mathematics)|matrix]] whose entries are given by <math>A(i,j) = \exp(-a \vert t_i - t_j \vert)</math>, where <math>a \in \mathbb{R}</math><ref name=":2">{{citation
- |last1 = Rybicki|first1 = George B.|last2 = Press|first2 = William H.|arxiv = comp-gas/9405004|doi = 10.1103/PhysRevLett.74.1060|journal = Physical Review Letters|title = Class of fast methods for processing Irregularly sampled or otherwise inhomogeneous one-dimensional data|volume = 74|issue = 7|pages = 1060–1063|year = 1995|bibcode = 1995PhRvL..74.1060R|pmid=10058924}} {{Open access}}</ref>  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.<ref>{{Cite journal|title = Interpolation, realization, and reconstruction of noisy, irregularly sampled data|last = Rybicki|first = George B.|date = October 1992|journal = The Astrophysical Journal|doi = 10.1086/171845|last2 = Press|first2 = William H.|bibcode = 1992ApJ...398..169R|volume=398|page=169}}{{Open access}}</ref><ref name=":0">{{Cite journal|last=MacLeod|first=C. L.|last2=Brooks|first2=K.|last3=Ivezic|first3=Z.|last4=Kochanek|first4=C. S.|last5=Gibson|first5=R.|last6=Meisner|first6=A.|last7=Kozlowski|first7=S.|last8=Sesar|first8=B.|last9=Becker|first9=A. C.|date=2011-02-10|title=Quasar Selection Based on Photometric Variability|journal=The Astrophysical Journal|volume=728|issue=1|pages=26|doi=10.1088/0004-637X/728/1/26|issn=0004-637X|arxiv=1009.2081|bibcode=2011ApJ...728...26M}}</ref>  The most common use of the algorithm is in the detection of periodicity in astronomical observations.<ref name=":0" />
+ |last1 = Rybicki|first1 = George B.|last2 = Press|first2 = William H.|arxiv = comp-gas/9405004|doi = 10.1103/PhysRevLett.74.1060|journal = Physical Review Letters|title = Class of fast methods for processing Irregularly sampled or otherwise inhomogeneous one-dimensional data|volume = 74|issue = 7|pages = 1060–1063|year = 1995|bibcode = 1995PhRvL..74.1060R|pmid=10058924}} {{Open access}}</ref> and where the <math>t_i</math> are sorted in order.<ref name=":3" /> 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 matrix algorithm|tridiagonal systems of equations]] can be solved efficiently (to be more precise, in linear time).<ref name=":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.<ref>{{Cite journal|title = Interpolation, realization, and reconstruction of noisy, irregularly sampled data|last = Rybicki|first = George B.|date = October 1992|journal = The Astrophysical Journal|doi = 10.1086/171845|last2 = Press|first2 = William H.|bibcode = 1992ApJ...398..169R|volume=398|page=169}}{{Open access}}</ref><ref name=":0">{{Cite journal|last=MacLeod|first=C. L.|last2=Brooks|first2=K.|last3=Ivezic|first3=Z.|last4=Kochanek|first4=C. S.|last5=Gibson|first5=R.|last6=Meisner|first6=A.|last7=Kozlowski|first7=S.|last8=Sesar|first8=B.|last9=Becker|first9=A. C.|date=2011-02-10|title=Quasar Selection Based on Photometric Variability|journal=The Astrophysical Journal|volume=728|issue=1|pages=26|doi=10.1088/0004-637X/728/1/26|issn=0004-637X|arxiv=1009.2081|bibcode=2011ApJ...728...26M}}</ref> The most common use of the algorithm is in the detection of periodicity in astronomical observations{{Verify source|date=October 2021}}, such as for detecting [[Quasar|quasars]].<ref name=":0" />
-Recently, this method has been extended ('''Generalized Rybicki-Press algorithm''') for inverting matrices whose entries of the form <math>A(i,j) = \sum_{k=1}^p a_k \exp(-\beta_k \vert t_i - t_j \vert)</math>.<ref>{{Cite journal|last=Ambikasaran|first=Sivaram|date=2015-12-01|title=Generalized Rybicki Press algorithm|journal=Numerical Linear Algebra with Applications|language=en|volume=22|issue=6|pages=1102–1114|doi=10.1002/nla.2003|issn=1099-1506|arxiv=1409.7852}}</ref> The key observation in the Generalized Rybicki-Press (GRP) algorithm is that the matrix <math>A</math> is a semi-separable matrix with rank <math>p</math>. More precisely, if the matrix <math>A \in \mathbb{R}^{n\times n}</math> has a semi-separable rank is <math>p</math>, the cost for solving the linear system <math>Ax=b</math> and obtaining the determinant of the matrix scales as <math>\mathcal{O}\left(p^2n \right)</math>, thereby making it extremely attractive for large matrices. This implementation of the GRP algorithm can be found here.<ref>{{Cite web|url=https://github.com/sivaramambikasaran/ESS|title=sivaramambikasaran/ESS|website=GitHub|language=en|access-date=2018-04-05}}</ref> The key idea is that the dense matrix <math>A</math> 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 method has been extended to the '''Generalized Rybicki-Press algorithm''' for inverting matrices with entries of the form <math>A(i,j) = \sum_{k=1}^p a_k \exp(-\beta_k \vert t_i - t_j \vert)</math>.<ref name=":3">{{Cite journal|last=Ambikasaran|first=Sivaram|date=2015-12-01|title=Generalized Rybicki Press algorithm|journal=Numerical Linear Algebra with Applications|language=en|volume=22|issue=6|pages=1102–1114|doi=10.1002/nla.2003|issn=1099-1506|arxiv=1409.7852}}</ref> The key observation in the Generalized Rybicki-Press (GRP) algorithm is that the matrix <math>A</math> is a [[semi-separable matrix]] with rank <math>p</math> (that is, a matrix whose upper half, not including the main diagonal, is that of some matrix with [[matrix rank]] <math>p</math> and whose lower half is also that of some possibly different rank <math>p</math> matrix<ref name=":3" />) 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 <math>A \in \mathbb{R}^{n\times n}</math> has a semi-separable rank of <math>p</math>, the [[computational complexity]] of solving the linear system <math>Ax=b</math> or of calculating the determinant of the matrix <math>A</math> scales as <math>\mathcal{O}\left(p^2n \right)</math>, thereby making it attractive for large matrices.<ref name=":3" /> This implementation of the GRP algorithm can be found here.<ref>{{Cite web|url=https://github.com/sivaramambikasaran/ESS|title=sivaramambikasaran/ESS|website=GitHub|language=en|access-date=2018-04-05}}</ref>{{External links inline|date=October 2021}}
-The fact that matrix <math>A</math> is a semi-separable matrix also forms the basis for {{proper name|celerite}}<ref>{{Cite web|url=https://celerite.readthedocs.io/en/stable/|title=celerite — celerite 0.3.0 documentation|website=celerite.readthedocs.io|language=en|access-date=2018-04-05}}</ref> library, which is a library for fast and scalable [[Gaussian process regression|Gaussian Process Regression]] in one dimension<ref name=":1">{{Cite journal|last=Foreman-Mackey|first=Daniel|last2=Agol|first2=Eric|last3=Ambikasaran|first3=Sivaram|last4=Angus|first4=Ruth|date=2017|title=Fast and Scalable Gaussian Process Modeling with Applications to Astronomical Time Series|url=http://stacks.iop.org/1538-3881/154/i=6/a=220|journal=The Astronomical Journal|language=en|volume=154|issue=6|pages=220|doi=10.3847/1538-3881/aa9332|issn=1538-3881|arxiv=1703.09710|bibcode=2017AJ....154..220F}}</ref> with implementations in [[C++]], [[Python (programming language)|Python]], and [[Julia (programming language)|Julia]]. The {{proper name|celerite}} method<ref name=":1" /> 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.<ref>{{Cite journal|last=Foreman-Mackey|first=Daniel|date=2018|title=Scalable Backpropagation for Gaussian Processes using Celerite|url=http://stacks.iop.org/2515-5172/2/i=1/a=31|journal=Research Notes of the AAS|language=en|volume=2|issue=1|pages=31|doi=10.3847/2515-5172/aaaf6c|issn=2515-5172|arxiv=1801.10156|bibcode=2018RNAAS...2a..31F}}</ref><ref>{{Cite book|title=Handbook of Exoplanets|last=Parviainen|first=Hannu|date=2018|publisher=Springer, Cham|isbn=9783319306483|pages=1–24|language=en|doi=10.1007/978-3-319-30648-3_149-1|chapter = Bayesian Methods for Exoplanet Science|arxiv = 1711.03329}}</ref>
+The fact that matrix <math>A</math> is a semi-separable matrix also forms the basis for {{proper name|celerite}}<ref>{{Cite web|url=https://celerite.readthedocs.io/en/stable/|title=celerite — celerite 0.3.0 documentation|website=celerite.readthedocs.io|language=en|access-date=2018-04-05}}</ref>{{External links inline|date=October 2021}} library, which is a library for fast and scalable [[Gaussian process regression]] in one dimension<ref name=":1">{{Cite journal|last=Foreman-Mackey|first=Daniel|last2=Agol|first2=Eric|last3=Ambikasaran|first3=Sivaram|last4=Angus|first4=Ruth|date=2017|title=Fast and Scalable Gaussian Process Modeling with Applications to Astronomical Time Series|url=http://stacks.iop.org/1538-3881/154/i=6/a=220|journal=The Astronomical Journal|language=en|volume=154|issue=6|pages=220|doi=10.3847/1538-3881/aa9332|issn=1538-3881|arxiv=1703.09710|bibcode=2017AJ....154..220F}}</ref> with implementations in [[C++]], [[Python (programming language)|Python]], and [[Julia (programming language)|Julia]]. The {{proper name|celerite}} method<ref name=":1" /> 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|date=October 2021}}, especially in astronomical data analysis.<ref>{{Cite journal|last=Foreman-Mackey|first=Daniel|date=2018|title=Scalable Backpropagation for Gaussian Processes using Celerite|url=http://stacks.iop.org/2515-5172/2/i=1/a=31|journal=Research Notes of the AAS|language=en|volume=2|issue=1|pages=31|doi=10.3847/2515-5172/aaaf6c|issn=2515-5172|arxiv=1801.10156|bibcode=2018RNAAS...2a..31F}}</ref><ref>{{Cite book|title=Handbook of Exoplanets|last=Parviainen|first=Hannu|date=2018|publisher=Springer, Cham|isbn=9783319306483|pages=1–24|language=en|doi=10.1007/978-3-319-30648-3_149-1|chapter = Bayesian Methods for Exoplanet Science|arxiv = 1711.03329}}</ref>
 ==See also==
@@ Line 19: / Line 19: @@
 ==References==
 {{Reflist}}
+== External links ==
+* [https://github.com/sivaramambikasaran/ESS Implementation of the Generalized Rybicki Press algorithm]
+* [https://github.com/dfm/celerite celerite library on GitHub]
 [[Category:Numerical linear algebra]]