A General Optimization Framework for Dynamic Time Warping
The goal of dynamic time warping is to transform or warp time in order to approximately align two signals together. 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 +inf 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.
Code (2)
Tasks
Dynamic Time WarpingSimilar Papers 제목 키워드 기반
Generalized Time Warping Invariant Dictionary Learning for Time Series Classification and Clustering
Dictionary learning is an effective tool for pattern recognition and classification of time series data. Among various dictionary learning techniques, the dynamic time warping (DTW) is commonly used for dealing with temp…
ClassificationClusteringDictionary LearningDynamic Time Warping+2Comparing Temporal Graphs Using Dynamic Time Warping
Within many real-world networks the links between pairs of nodes change over time. Thus, there has been a recent boom in studying temporal graphs. Recognizing patterns in temporal graphs requires a proximity measure to c…
Dynamic Time WarpingTime Series AnalysisConditional Deep Canonical Time Warping
Temporal alignment of sequences is a fundamental challenge in many applications, such as computer vision and bioinformatics, where local time shifting needs to be accounted for. Misalignment can lead to poor model genera…
Dynamic Time Warpingfeature selectionTrainable Time Warping: Aligning Time-Series in the Continuous-Time Domain
DTW calculates the similarity or alignment between two signals, subject to temporal warping. However, its computational complexity grows exponentially with the number of time-series. Although there have been algorithms d…
General ClassificationTime SeriesTime Series AnalysisTime Series AveragingOptimal Warping Paths are unique for almost every Pair of Time Series
Update rules for learning in dynamic time warping spaces are based on optimal warping paths between parameter and input time series. In general, optimal warping paths are not unique resulting in adverse effects in theory…
Dynamic Time WarpingTime SeriesTime Series Analysis