Class of Fast Methods for Processing Irregularly Sampled or Otherwise Inhomogeneous One-Dimensional Data
G. B. Rybicki, William H. Press · Physical Review Letters · 1995
With the ansatz that a data set's correlation matrix has a certain parametrized from (one general enough, however, to allow the arbitrary specification of a slowly varying decorrelation distance and population variance), the general machinery of Wiener or optimal filtering can be reduced from $O({n}^{3})$ to $O(n)$ operations, where $n$ is the size of the data set. The implied vast increase in computational speed can allow many common suboptimal or heuristic data analysis methods to be replaced by fast, relatively sophisticated, statistical algorithms. Three examples are given: data rectification, high- or low-pass filtering, and linear least-squares fitting to a model with unaligned data points.