Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 3 down vote favorite
2

I asked this question over on StackOverflow, and was recommended to ask it here. Rather than duplicate the entire question here, I hope I can start new comment/solution chains here. If I should repost the question, please let me know.

share|improve this question
1  
@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
1  
@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

1 Answer

up vote 4 down vote

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.

share|improve this answer
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.