Optimal 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 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Dynamic Time WarpingTime SeriesTime Series AnalysisSimilar Papers 제목 키워드 기반
ScanGAN360: A Generative Model of Realistic Scanpaths for 360$^{\circ}$ Images
Understanding and modeling the dynamics of human gaze behavior in 360$^\circ$ environments is a key challenge in computer vision and virtual reality. Generative adversarial approaches could alleviate this challenge by ge…
Dynamic Time WarpingDeep Declarative Dynamic Time Warping for End-to-End Learning of Alignment Paths
This paper addresses learning end-to-end models for time series data that include a temporal alignment step via dynamic time warping (DTW). Existing approaches to differentiable DTW either differentiate through a fixed w…
Dynamic Time WarpingInformation RetrievalMusic Information RetrievalRetrieval+2A Probabilistic Time-Evolving Approach to Scanpath Prediction
Human visual attention is a complex phenomenon that has been studied for decades. Within it, the particular problem of scanpath prediction poses a challenge, particularly due to the inter- and intra-observer variability,…
Dynamic Time WarpingPredictionScanpath predictionWarpedGANSpace: Finding non-linear RBF paths in GAN latent space
This work addresses the problem of discovering, in an unsupervised manner, interpretable paths in the latent space of pretrained GANs, so as to provide an intuitive and easy way of controlling the underlying generative f…
Game Connectivity and Adaptive Dynamics
We analyse the typical structure of games in terms of the connectivity properties of their best-response graphs. Our central result shows that, among games that are `generic' (without indifferences) and that have a pure …