Optimal Warping Paths are unique for almost every Pair of Time Series
This addresses a theoretical and practical bottleneck in time series analysis for researchers and practitioners, though it is incremental as it builds on existing assumptions.
The paper tackles the problem of non-unique optimal warping paths in dynamic time warping, which causes issues in learning algorithms, and shows that under squared error costs, these paths are unique almost everywhere, implying that distance-based cost functions like k-means are differentiable almost everywhere.
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 and practice. Under the assumption of squared error local costs, we show that no two warping paths have identical costs almost everywhere in a measure-theoretic sense. Two direct consequences of this result are: (i) optimal warping paths are unique almost everywhere, and (ii) the set of all pairs of time series with multiple equal-cost warping paths coincides with the union of exponentially many zero sets of quadratic forms. One implication of the proposed results is that typical distance-based cost functions such as the k-means objective are differentiable almost everywhere and can be minimized by subgradient methods.