How to correlate two time series with gaps and different time bases?

I asked this question over on StackOverflow, and was recommended to ask it here.

I have two time series of 3D accelerometer data that have different time bases (clocks started at different times, with some very slight creep during the sampling time), as well as containing many gaps of different size (due to delays associated with writing to separate flash devices).

The accelerometers I'm using are the inexpensive GCDC X250-2. I'm running the accelerometers at their highest gain, so the data has a significant noise floor.

The time series each have about 2 million data points (over an hour at 512 samples/sec), and contain about 500 events of interest, where a typical event spans 100-150 samples (200-300 ms each). Many of these events are affected by data outages during flash writes.

So, the data isn't pristine, and isn't even very pretty. But my eyeball inspection shows it clearly contains the information I'm interested in. (I can post plots, if needed.)

The accelerometers are in similar environments but are only moderately coupled, meaning that I can tell by eye which events match from each accelerometer, but I have been unsuccessful so far doing so in software. Due to physical limitations, the devices are also mounted in different orientations, where the axes don't match, but they are as close to orthogonal as I could make them. So, for example, for 3-axis accelerometers A & B, +Ax maps to -By (up-down), +Az maps to -Bx (left-right), and +Ay maps to -Bz (front-back).

My initial goal is to correlate shock events on the vertical axis, though I would eventually like to a) automatically discover the axis mapping, b) correlate activity on the mapped aces, and c) extract behavior differences between the two accelerometers (such as twisting or flexing).

The nature of the time series data makes Python's numpy.correlate() unusable. I've also looked at R's Zoo package, but have made no headway with it. I've looked to different fields of signal analysis for help, but I've made no progress.

Anyone have any clues for what I can do, or approaches I should research?

Update 28 Feb 2011: Added some plots here showing examples of the data.

-
@BobC, maybe one of the moderators can have your post migrated to this site. That would be the most reasonable. As for your technical questions, first of all, are you using the FFT to do the correlation? That should be feasible for 2 million data points on a half-decent computer. Your signal-to-noise ratio looks reasonably high, so you should be in business. A quick-and-dirty cut would be to fill in the missing data with either the last available sample or with zeros. The creep from sampling-interval differences may be the most challenging "feature" of your data to deal with. –  cardinal Mar 1 '11 at 2:16
@cardinal: I did indeed try an FFT, only to get garbage as a result. The 'interesting' features readily visible in the data are indistinguishable from noise in the FFT. However, I have done FFTs only on the entire data set: Perhaps a moving window FFT would provide better results, but I haven't yet been able to find a computationally efficient way to implement it. I suspect a Wavelet transform could help, but I'm unfamiliar with it (but am slowly learning about it). –  BobC Mar 1 '11 at 2:24
@BobC, what I meant was, did you consider an FFT-based implementation for calculating the correlation? Direct convolution is $O(n^2)$, but an FFT-based implementation would reduce this $O(n \log n)$, making it feasible. As for looking at the FFT itself, with 2 million data points, your frequency resolution will be very high. Any sampling creep and other stuff is bound to wash the signal out on a per-frequency basis. But, you should be able to aggregate over many bins to bring the signal out of the noise. Something like a Welch approach or maybe a custom windowing technique. –  cardinal Mar 1 '11 at 2:29
@BobC, off the top of my head, it seems like some variant of an overlap-and-add or overlap-and-save algorithm could be used to do a sliding-window FFT. Sliding the samples within a window just amounts to a phase shift, so all you have to do is compensate for those samples that "fall off" the left end and those that "come in" on the right end. –  cardinal Mar 1 '11 at 2:31
Hi, I have a similar question. I have 2 time series, each represented by a matrix with its first column corresponding to the values and second column corresponding to the time difference (since the previous value) How do I find the correlation between these 2 matrices? I tried to do xcorr2() but it doesn't seem right and doing xcorr would probably calculate correlation with only the values into considering, but I also want to account for the time. I'm really confused here, will an FFT help? How would you suggest I go about it? –  user3233 Mar 1 '11 at 3:09
show 4 more comments

The question concerns calculating the correlation between two irregularly sampled time series (one-dimensional stochastic processes) and using that to find the time offset where they are maximally correlated (their "phase difference").

This problem is not usually addressed in time series analysis, because time series data are presumed to be collected systematically (at regular intervals of time). It is rather the province of geostatistics, which concerns the multidimensional generalizations of time series. The archetypal geostatistical dataset consists of measurements of geological samples at irregularly spaced locations.

With irregular spacing, the distances among pairs of locations vary: no two distances may be the same. Geostatistics overcomes this with the empirical variogram. This computes a "typical" (often the mean or median) value of $(z(p) - z(q))^2 / 2$--the "semivariance"--where $z(p)$ denotes a measured value at point $p$ and the distance between $p$ and $q$ is constrained to lie within an interval called a "lag". If we assume the process $Z$ is stationary and has a covariance, then the expectation of the semivariance equals the maximum covariance (equal to $Var(Z(p))$ for any $p$) minus the covariance between $Z(p)$ and $Z(q)$. This binning into lags copes with the irregular spacing problem.

When an ordered pair of measurements $(z(p), w(p))$ is made at each point, one can similarly compute the empirical cross-variogram between the $z$'s and the $w$'s and thereby estimate the covariance at any lag. You want the one-dimensional version of the cross-variogram. The R packages gstat and sgeostat, among others, will estimate cross-variograms. Don't worry that your data are one-dimensional; if the software won't work with them directly, just introduce a constant second coordinate: that will make them appear two-dimensional.

With two million points you should be able to detect small deviations from stationarity. It's possible the phase difference between the two time series could vary over time, too. Cope with this by computing the cross-variogram separately for different windows spaced throughout the time period.

@cardinal has already brought up most of these points in comments. The main contribution of this reply is to point towards the use of spatial statistics packages to do your work for you and to use techniques of geostatistics to analyze these data. As far as computational efficiency goes, note that the full convolution (cross-variogram) is not needed: you only need its values near the phase difference. This makes the effort $O(nk)$, not $O(n^2)$, where $k$ is the number of lags to compute, so it might be feasible even with out-of-the-box software. If not, the direct convolution algorithm is easy to implement.

-
@whuber, good comments and suggestions. If I'm reading the question correctly, I believe one primary concern is uncertainty of the time-point of sampling. This may be a little different from the typical geostatistics framework where, I believe, the spacing is irregular, but still assumed known (at least to high precision). I think a rough model is, if the $n$th point of series one is at time $t_n = n t$, for fixed $t$ then the $n$th point of series 2 is at $\tau_n = t_n + \alpha + \beta n$ where $\alpha$ is probably on the order of a few milliseconds and $\beta$ is likely tiny. –  cardinal Mar 8 '11 at 3:40
@Cardinal I didn't get that from the question. I can't think of a way of estimating $\beta$ that wouldn't be quite computationally intensive. Perhaps by breaking the time series into groups where the net effect of $\beta$ is negligible? –  whuber Mar 8 '11 at 5:08
@whuber, @BobC, I'm making a semi-educated guess based on past experience dealing with similar problems and issues. Most approaches I've seen are computationally intensive and fail to impress. One attempt might be via something like dynamic time warping or what Ramsay and Silverman call curve registration. Whether either of those would be feasible on this size dataset is unclear to me. –  cardinal Mar 8 '11 at 5:17
It'll take me a bit to get my brain wrapped around this. I'll start with the examples in the R packages you mentioned. –  BobC Mar 8 '11 at 9:21
@BobC, is the rough model I gave for the timing asynchronicity close to what you have? I'm thinking it's "random initial offset" + "linear error" where the latter is due to a small constant difference in the sampling interval between your two devices. Then there is some additional small random error, say due to interrupt processing of two different uC's on top of that. –  cardinal Mar 8 '11 at 17:53
show 7 more comments