Rybicki Press algorithm: Difference between revisions

Content deleted Content added

Inline

Revision as of 14:05, 1 October 2021

The Rybicki–Press algorithm is a fast direct 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] 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.^[2]^[3] The most common use of the algorithm is in the detection of periodicity in astronomical observations.^[3]

Recently, this method has been extended (Generalized Rybicki-Press algorithm) for inverting matrices whose entries of the form $A(i,j)=\sum _{k=1}^{p}a_{k}\exp(-\beta _{k}\vert t_{i}-t_{j}\vert )$ .^[4] The key observation in the Generalized Rybicki-Press (GRP) algorithm is that the matrix $A$ is a semi-separable matrix with rank $p$ . More precisely, if the matrix $A\in \mathbb {R} ^{n\times n}$ has a semi-separable rank is $p$ , the cost for solving the linear system $Ax=b$ and obtaining the determinant of the matrix scales as ${\mathcal {O}}\left(p^{2}n\right)$ , thereby making it extremely attractive for large matrices. This implementation of the GRP algorithm can be found here.^[5] The key idea is that the dense matrix $A$ 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 $A$ is a semi-separable matrix also forms the basis for celerite^[6] 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, especially in astronomical data analysis.^[8]^[9]

References

^ 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
^ 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.
^ 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.
^ "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.

[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

[2] 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-3] 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.

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

[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 7: / Line 7: @@
  |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" />
-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 (GPP) 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 GPP 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.
+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 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 (GP) 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> 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>
 ==See also==