Rybicki Press algorithm: Difference between revisions

Revision as of 22:30, 2 December 2019

Revision as of 03:01, 18 December 2020

Line 3:

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

|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|url = |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|pmid = |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.