A General Optimization Framework for Dynamic Time Warping

Dave Deriso, Stephen P. BoydarXiv 2019 · arXiv

Dynamic Time Warping (DTW) is a cornerstone of time-series analysis, essential for applications ranging from speech recognition to financial forecasting. However, the classic algorithm frequently produces "singularities"—pathological artifacts where multiple points in one signal are erroneously mapped to a single point in another. In their recent work, Dave Deriso and Stephen Boyd present a modern, optimization-based overhaul of DTW that addresses these issues while offering significant performance improvements.

The Challenge: Singularities in Classic DTW

The fundamental goal of DTW is to align two signals by "warping" the time axis of one to match the other. While powerful, the original 1970s-era algorithm is purely local and unconstrained. This often leads to "singularities," where the algorithm finds a mathematically optimal but physically nonsensical alignment—such as mapping a whole second of audio to a single millisecond.

Existing remedies are typically ad-hoc, involving manual preprocessing or rigid "step patterns" that limit temporal flexibility. These solutions often require extensive hand-tuning for each new dataset. This paper proposes a general framework that handles these issues mathematically through regularization, analogous to how Ridge or Lasso regression prevents overfitting in machine learning.

A Regularized Optimization Approach

The authors re-imagine DTW as a classical optimal control problem. Instead of simply minimizing the distance between signals, they minimize a multi-term objective function:

  1. Loss Functional: Measures the alignment quality between signals.
  2. Cumulative Warp Regularization: Penalizes the deviation of warped time from original time.
  3. Instantaneous Warp Regularization: Penalizes the rate of warping, preventing singularities and ensuring a smooth warping function.

To solve this infinite-dimensional problem efficiently, they employ Dynamic Programming (DP) with iterative refinement. By first solving on a coarse grid and then refining the solution on progressively finer grids, the approach achieves global optimality without the prohibitive cost of high-resolution brute-force searches.

Visualizing the GDTW alignment process: (Left) Signal alignment stages; (Right) Warping function $\phi(t)$ and its derivatives.

Key Insights and Implementation

The framework's use of regularization allows users to explicitly balance alignment accuracy ("fit") against the naturalness of the warping ("smoothness"). Furthermore, because the formulation is in continuous time, it inherently handles non-uniformly sampled data or signals with missing values.

The authors also introduce a "machine learning-native" approach to model selection. By using hyperparameters ($\lambda^{cum}$ and $\lambda^{inst}$), standard out-of-sample validation can be used to determine the optimal parameters, ensuring the warping does not overfit noise.

Performance and Results

The resulting open-source package, GDTW, demonstrates several key advantages:

  • Elimination of Singularities: The regularized approach produces significantly smoother warping functions compared to unregularized methods like FastDTW.
  • Computational Efficiency: GDTW, implemented in C++ with a Python wrapper, is up to 50x faster than FastDTW for signals of length $N=1000$.
  • Versatility: The framework extends easily to tasks like finding a "mean" signal (centering) or grouping similar signals (clustering).

Limitations and Future Work

While highly efficient, penalizing higher-order derivatives (e.g., warping "acceleration") increases computational complexity by expanding the DP state space. Additionally, the "asymmetric bidirectional" version of the problem remains computationally expensive for very high-resolution alignments. Future research may focus on optimizing these more complex variants.

Summary updated

BibTeX
@misc{deriso2019general,
  author = {Dave Deriso and Stephen P. Boyd},
  title = {{A General Optimization Framework for Dynamic Time Warping}},
  year = {2019},
  eprint = {1905.12893},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.12893},
}
Figure