0
$\begingroup$

I am applying DTW to a set of data. I haven't figured out a solution yet, still searching for ideas, and I'm currently trying to apply DTW successively with a monotonic set of windows.

Let's say i have a reference and test signals, which have been both resampled at 10 millis (reference is usually a 10 samples or so of length), the test signal is varying,but 3k of data samples is not unusual. My intention is to run DTW with window size of let's say 10,20,...50 and see how far it gets me. Question is, can I optimize this? Example: starting with 50 and calculating properly the DTW for this, are there shortcuts when progressing down to 40, 30 and so on (or the reverse, starting with 10 and progressing to 50)?

Can the processing effort be reduced under 5 full DTWs by reusing calculations for a different window size, yet applied to the same two signals?

For instance, I reinitialize the cost matrix only once per a set of 10...50 window DTWs. Cost matrix will have a 3K by 3K size after resampling, and reinitialization for constrained DTW, in my understanding, means resetting the elements to an arbitrarily high value. Checking with matlab, yielded the same results as reinitializing every time before DTW, but the running time was reduced to a third. Still, this has been tested insufficiently.

Please note this is not a question about generally optimizing DTW (currently not investigating bounding or anything else), but one with specific application to this use case.

$\endgroup$
  • $\begingroup$ Successive dynamic time warping... $\endgroup$ – Kalibr May 17 '17 at 7:40
  • $\begingroup$ sorry, I was having a stupid morning :) Thanks! $\endgroup$ – Marcus Müller May 17 '17 at 8:34
0
$\begingroup$

Hmm

There are few properties to help you.

Let Wi be a warping window of width i

It is the case that DTW_wi(A,B) >= DTW_wi+1(A,B)

Other than that, there is little to say.

If you have not already, you should read http://www.cs.unm.edu/~mueen/DTW.pdf and http://www.cs.ucr.edu/~eamonn/CIKM_2016_DTW_clustering.pdf

If you are only interested in the smallest items in the matrix, then using lower bounds (the LB_Keogh) will give you an easy 100-fold speed up.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your reply, at the moment, lb is not an option because there can be multiple candidates with very similar scores. LB-ing will somehow truncate further info about them, when I actually need to see the exact score. Like I said, the software solution is not well defined yet (tried first with pearson correlation, now I'm looking at dtw), so I need all the 'verbosity' I can get. Thank you again. $\endgroup$ – Kalibr May 18 '17 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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