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^{3}workload- but
*actually*can be done, thanks to special assumptions or approximations, in order n workload

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

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,'' inPredicting the Future and Understanding the Past: a Comparison of Approaches, A.S. Weigend and N.A. Gershenfeld, eds. (Reading, MA: Addison-Wesley, 1993).

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

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(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.)_{i}-t_{j}|

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

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 Astrophysics245, 171 (1991). Downloadable as PDF file.