Abstract
The goal of dynamic time warping is to transform or warp time in order to approximately align two signals. We pose the choice of warping function as an optimization problem with several terms in the objective. The first term measures the misalignment of the time-warped signals. Two additional regularization terms penalize the cumulative warping and the instantaneous rate of time warping; constraints on the warping can be imposed by assigning the value \(+\infty\) to the regularization terms. Different choices of the three objective terms yield different time warping functions that trade off signal fit or alignment and properties of the warping function. The optimization problem we formulate is a classical optimal control problem, with initial and terminal constraints, and a state dimension of one. We describe an effective general method that minimizes the objective by discretizing the values of the original and warped time, and using standard dynamic programming to compute the (globally) optimal warping function with the discretized values. Iterated refinement of this scheme yields a high accuracy warping function in just a few iterations. Our method is implemented as an open source Python package GDTW.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abou-Nasr M, Feldkamp L (2008) Ford Classification Challenge. Zip Archive http://www.timeseriesclassificationcom/descriptionphp?Dataset=FordA
Bellman RE & Dreyfus SE (2015) Applied dynamic programming (Vol. 2050). Princeton university press
Bertsekas DP (2005) Vol. 1 of Dynamic programming and optimal control. Athena scientific Belmont, MA
Boyd S, Boyd SP, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge
Boyd S, Vandenberghe L (2018) Introduction to applied linear algebra: vectors, matrices, and least squares. Cambridge University Press, Cambridge
Dau H, Silva D, Petitjean F et al (2018) Optimizing dynamic time warping’s window width for time series data mining applications. Data min knowl Discov 32(4):1074–1120
Dupont M, Marteau P (2015) Coarse-DTW for sparse time series alignment. In: International Workshop on Advanced Analytics and Learning on Temporal Data, Springer, pp 157–172
Hastie T, Tibshirani R, Friedman J (2001) The elements of statistical learning. Springer series in statistics, New York, NY, USA
Golub GH & Loan CF Van (2012) Matrix computations, vol. 3 JHU press
Green PJ & Silverman BW (1993) Nonparametric regression and generalized linear models: a roughness penalty approach. Crc Press
Hansen PC (1998). Rank-deficient and discrete ill-posed problems: numerical aspects of linear inversion. Society for Industrial and Applied Mathematics
Huber P (2011) Robust statistics. In: International encyclopedia of statistical science. Springer, p 1248–1251
Itakura F (1975) Minimum prediction residual principle applied to speech recognition. IEEE Trans Acoust Speech Signal Process 23(1):67–72
Keogh E, Pazzani M (2001) Derivative dynamic time warping. In: Proceedings of the 2001 SIAM international conference on data mining, SIAM, pp 1–1
Marron J, Ramsay J, Sangalli L et al (2015) Functional data analysis of amplitude and phase variation. Stat Sci 30(4):468–484
Myers C, Rabiner L, Rosenberg A (1980) Performance tradeoffs in dynamic time warping algorithms for isolated word recognition. IEEE Trans Acoust Speech Signal Process 28(6):623–635
Needleman S, Wunsch C (1970) A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol 48(3):443–453
Rabiner L & Juang BH (1993) Fundamentals of speech recognition. Prentice-Hall, Inc.
Rakthanmanon T, Campana B, Mueen A, et al (2012) Searching and mining trillions of time series subsequences under dynamic time warping. In: Proceedings of the international conference on knowledge discovery and data mining, ACM, pp 262–270
Ramsay JO, Silverman BW (2005) Fitting differential equations to functional data: Principal differential analysis. Springer, New York, pp 327–348
Ramsay J, Silverman B (2007) Applied functional data analysis: Methods and case studies. Springer
Sakoe H, Chiba S (1978) Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans Acoust Speech Signal Process 26(1):43–49
Salvador S, Chan P (2007) Toward accurate dynamic time warping in linear time and space. Intell Data Anal 11(5):561–580
Singh M, Cheng I, Mandal M, et al (2008) Optimization of symmetric transfer error for sub-frame video synchronization. In: European conference on computer vision, Springer, pp 554–567
Ramsay JO & Silverman BW(2005). Fitting differential equations to functional data: Principal differential analysis (pp. 327-348). Springer New York
Srivastava A, Wu W, Kurtek S, et al (2011) Registration of functional data using Fisher-Rao metric. arXiv preprint arXiv:1103.3817
Tibshirani R (1996) Regression shrinkage and selection via the lasso. J R Stat Soc 58(1):267–288
Tikhonov A, Arsenin V (1977) Solutions of Ill-Posed Problems, vol 14. Winston
Xi X, Keogh E, Shelton C, et al (2006) Fast time series classification using numerosity reduction. In: Proceedings of the 23rd international conference on machine learning, ACM, pp 1033–1040
Zhao J, Itti L (2016) ShapeDTW: Shape dynamic time warping. arXiv preprint arXiv:1606.01601
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Disclosure statement
The authors declare that they have no conflicts of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Deriso, D., Boyd, S. A general optimization framework for dynamic time warping. Optim Eng 24, 1411–1432 (2023). https://doi.org/10.1007/s11081-022-09738-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11081-022-09738-z