Rybicki Press algorithm - Revision history

Voidxor: Add short description. Rm sentence-fragment periods per MOS:CAPTION.

2025-01-20T00:15:42Z

Add short description. Rm sentence-fragment periods per MOS:CAPTION.

← Previous revision		Revision as of 00:15, 20 January 2025
Line 1:		Line 1:
			{{Short description\|An algorithm for inverting a matrix}}
	{{Technical\|date=August 2021}}		{{Technical\|date=August 2021}}
	[[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>.]]		[[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 [[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\|s2cid = 17436268}} {{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\|last1 = Rybicki\|first1 = 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\|last1=MacLeod\|first1=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\|s2cid=28219978}}</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" />		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">{{cite journal \|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 \|date=1995 \|bibcode = 1995PhRvL..74.1060R\|pmid=10058924\|s2cid = 17436268}} {{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\|last1 = Rybicki\|first1 = 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\|last1=MacLeod\|first1=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\|s2cid=28219978}}</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" />

	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\|s2cid=1627477}}</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" />		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\|s2cid=1627477}}</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" />
Line 9:		Line 10:

	==See also==		==See also==
	*[[Invertible matrix]]		* [[Invertible matrix]]
	*[[Matrix decomposition]]		* [[Matrix decomposition]]
	*[[Multidimensional signal processing]]		* [[Multidimensional signal processing]]
	*[[System of linear equations]]		* [[System of linear equations]]

	==References==		==References==

Citation bot: Add: doi-access. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 1972/2500

2023-09-11T03:18:01Z

Add: doi-access. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 1972/2500

← Previous revision		Revision as of 03:18, 11 September 2023
Line 6:		Line 6:
	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\|s2cid=1627477}}</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" />		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\|s2cid=1627477}}</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" />

	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]] in one dimension<ref name=":1">{{Cite journal\|last1=Foreman-Mackey\|first1=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\|s2cid=88521913}}</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...2...31F\|s2cid=102481482}}</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]] in one dimension<ref name=":1">{{Cite journal\|last1=Foreman-Mackey\|first1=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\|s2cid=88521913 \|doi-access=free }}</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...2...31F\|s2cid=102481482 \|doi-access=free }}</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==		==See also==

Citation bot: Alter: bibcode. Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. Upgrade ISBN10 to ISBN13. | Use this bot. Report bugs. | Suggested by Abductive | Category:Articles with specifically marked weasel-worded phrases from October 2021 | #UCB_Category 19/403

2021-12-31T17:14:18Z

Alter: bibcode. Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. Upgrade ISBN10 to ISBN13. | Use this bot. Report bugs. | Suggested by Abductive | Category:Articles with specifically marked weasel-worded phrases from October 2021 | #UCB_Category 19/403

← Previous revision		Revision as of 17:14, 31 December 2021
Line 2:		Line 2:
	[[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>.]]		[[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 [[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		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> 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" />		\|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\|s2cid = 17436268}} {{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\|last1 = Rybicki\|first1 = 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\|last1=MacLeod\|first1=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\|s2cid=28219978}}</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" />

	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" />		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\|s2cid=1627477}}</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" />

	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]] 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>		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]] in one dimension<ref name=":1">{{Cite journal\|last1=Foreman-Mackey\|first1=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\|s2cid=88521913}}</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...2...31F\|s2cid=102481482}}</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==		==See also==

Broccoli and Coffee: Removed {{Underlinked}} tag

2021-10-02T16:10:33Z

Removed {{Underlinked}} tag

← Previous revision		Revision as of 16:10, 2 October 2021
Line 1:		Line 1:
	{{Multiple issues\|
	{{Technical\|date=August 2021}}		{{Technical\|date=August 2021}}
	{{Underlinked\|date=August 2021}}
	}}
	[[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>.]]		[[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 [[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		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

Broccoli and Coffee: ce

2021-10-02T16:10:25Z

← Previous revision		Revision as of 16:10, 2 October 2021
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> 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" />		\|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" />

	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 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" />

	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>		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]] 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==		==See also==
Line 21:		Line 21:

	== External links ==		== External links ==

	* [https://github.com/sivaramambikasaran/ESS Implementation of the Generalized Rybicki Press algorithm]		* [https://github.com/sivaramambikasaran/ESS Implementation of the Generalized Rybicki Press algorithm]
	* [https://github.com/dfm/celerite celerite library on GitHub]		* [https://github.com/dfm/celerite celerite library on GitHub]

Duckmather: wrote text, copy-edited

2021-10-02T04:56:56Z

wrote text, copy-edited

← Previous revision		Revision as of 04:56, 2 October 2021
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>.]]		[[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==		==See also==
Line 19:		Line 19:
	==References==		==References==
	{{Reflist}}		{{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]]		[[Category:Numerical linear algebra]]

Eimant: Fixed several grammar mistakes and added links

2021-10-01T14:05:11Z

Fixed several grammar mistakes and added links

← Previous revision		Revision as of 14:05, 1 October 2021
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" />		\|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==		==See also==

Adammaxi: added link

2021-09-24T10:15:57Z

added link

← Previous revision		Revision as of 10:15, 24 September 2021
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>.]]		[[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 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
	\|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> 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" />

Johnj1995: This article has a lead section

2021-09-21T20:58:28Z

This article has a lead section

← Previous revision		Revision as of 20:58, 21 September 2021
Line 1:		Line 1:
	{{Multiple issues\|		{{Multiple issues\|
	{{Lead missing\|date=August 2021}}
	{{Technical\|date=August 2021}}		{{Technical\|date=August 2021}}
	{{Underlinked\|date=August 2021}}		{{Underlinked\|date=August 2021}}

StubblyDread16: Added a link in the word "matrix"

2021-09-21T16:33:57Z

Added a link in the word "matrix"

← Previous revision		Revision as of 16:33, 21 September 2021
Line 5:		Line 5:
	}}		}}
	[[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>.]]		[[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, 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 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
	\|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> 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" />

← Previous revision		Revision as of 17:14, 31 December 2021
Line 2:		Line 2:
	[[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>.]]		[[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 [[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		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> 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" />		\|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\|s2cid = 17436268}} {{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\|last1 = Rybicki\|first1 = 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\|last1=MacLeod\|first1=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\|s2cid=28219978}}</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" />

	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" />		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\|s2cid=1627477}}</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" />

	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]] 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>		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]] in one dimension<ref name=":1">{{Cite journal\|last1=Foreman-Mackey\|first1=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\|s2cid=88521913}}</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...2...31F\|s2cid=102481482}}</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==		==See also==

← Previous revision		Revision as of 16:10, 2 October 2021
Line 1:		Line 1:
	{{Multiple issues\|
	{{Technical\|date=August 2021}}		{{Technical\|date=August 2021}}
	{{Underlinked\|date=August 2021}}
	}}
	[[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>.]]		[[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 [[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		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

← Previous revision		Revision as of 20:58, 21 September 2021
Line 1:		Line 1:
	{{Multiple issues\|		{{Multiple issues\|
	{{Lead missing\|date=August 2021}}
	{{Technical\|date=August 2021}}		{{Technical\|date=August 2021}}
	{{Underlinked\|date=August 2021}}		{{Underlinked\|date=August 2021}}