A Class of Fast Methods for Processing Irregularly Sampled or Otherwise Inhomogeneous One-Dimensional Data

With the ansatz that a data set’s correlation matrix has a certain parametrized form (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 increases in computational speed can allow many common sub-optimal 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.