Rybicki & Press Fast Statistical Methods Page

Keywords (for robots):
time series statistical methods Wiener filter optimal filters filtering linear prediction interpolation covariance matrix correlation function structure function exponential decay inverse of tridiagonal matrix Gaussian random process fast method order N methods least squares fitting Gauss-Markov unbiased low-frequency red pink noise random walk fractal

This page was made by George Rybicki and Bill Press, as a location for our links to the subject, and as a distribution point for our source code that implements so-called "fast" statistical methods.

We define "fast" methods as being methods that

seem to require the inversion of a matrix the size of the data set (typically the covariance matrix S+N), an n³ workload
but actually can be done, thanks to special assumptions or approximations, in order n workload

We are interested in fast methods because they are applicable to very large data sets, and because they provide an efficient and well-controlled alternative to various inferior and ad-hoc procedures for the interpolation or fitting of noisy, incomplete data sets.

Our Publications

Our principal published work on this subject is in PRL,

G.B. Rybicki and W.H. Press, ``A Class of Fast Methods for Processing Irregularly Sampled or Otherwise Inhomogeneous One-Dimensional Data,'' Physical Review Letters, 74, 1060 (1995).

Here is a downloadable PDF file.

The above paper is rather terse, due to the requirements of the journal. We have written related papers on statistical reconstruction (though not via fast methods) which may help you to understand the above fast-methods paper:

G.B. Rybicki and W.H. Press, ``Interpolation, Realization, and Reconstruction of Noisy, Irregularly Sampled Data,'' Astrophysical Journal, 398, 169 (1992). (Reprint in ADS.)

W.H. Press and G.B. Rybicki, ``Large-Scale Linear Methods for Interpolation, Realization, and Reconstruction of Noisy, Irregularly Sampled Data,'' in Predicting the Future and Understanding the Past: a Comparison of Approaches, A.S. Weigend and N.A. Gershenfeld, eds. (Reading, MA: Addison-Wesley, 1993).

Sample Code for Fast Methods

We are putting the following files of sample code into the public domain (except for the embedded Numerical Recipes derivative routines whose rights are reserved by the copyright holders). There is no warranty of any kind. Use at your own risk.

README file explaining the next seven listings
sfast1.f Fortran 77 source
sfast2.f Fortran 77 source
snfast11.f Fortran 77 source
snfast12.f Fortran 77 source
snfast21.f Fortran 77 source
snfast22.f Fortran 77 source
subs.f Fortran 77 source
Fast Method Toolkit. Fortran 90 source code referenced in the PRL paper. This was developed earlier than the above code files, but is packaged to perform somewhat higher-level tasks. (The toolkit could be rewritten to call the above fast inversion subroutines, but we have not done this.)
lininv.f Fortran 77 source (see 3rd white paper below)

Additional "White Paper" Documents

George Rybicki has written several white-paper documents that describe further details of, and some interesting variants of, the fast methods described in the PRL paper. These should be considered as draft pieces of more formal papers yet to be written! These should be cited as "G.B. Rybicki, unpublished notes" (with or without the Web reference to this page).

Some Notes on Wiener Reconstruction (10 October 1997). PDF file. (Shows how to rewrite the unbiased estimator formulas in terms of the structure function alone, instead of the correlation function.)

Notes on the Ornstein-Uhlenbeck Process (2 December 1994).PDF file. (This is the process with the exponential correlation function that, when used as an approximation, enables the fast methods. Here it is looked at in its own right.)

Fast Operations Involving the Matrix |t_i-t_j| (4 March 1998). PDF file. (Shows how to take the limit to pure random walk processes, where the structure function is linear in time difference. Sample code is in the file lininv.f, previously listed.)

Reduction Method for Duplicated Times (3 May 1995). PDF file. (Shows how to prevent duplicate times from causing the fast-method to become ill-posed. This technique is used in some of the sample codes above.)

Estimation of Correlation Properties (10 Jan 1995). PDF file. (Shows how to estimate the parametrized correlation matrix of a process from data by a method that can be made fast using the same sorts of techniques.)

Other "Fast" Topics

The following papers deal with different kinds of fast method, possibly also of interest:

W.H. Press and G.B. Rybicki, ``Fast Algorithm for Spectral Analysis of Unevenly Sampled Data," Astrophysical Journal, 338, 277 (1989). (Reprint in ADS.)

G.B. Rybicki and D.G. Hummer, ``Fast Solution for the Diagonal Elements of the Inverse of a Tridiagonal Matrix," Appendix B of ``An Accelerated Lambda Iteration Method for Multilevel Radiative Transfer," Astronomy and Astrophysics 245, 171 (1991). Downloadable as PDF file.