OTW: Optimal Transport Warping for Time Series

• URL: http://arxiv.org/abs/2306.00620v1
• Date: Thu, 1 Jun 2023 12:45:00 GMT
• Title: OTW: Optimal Transport Warping for Time Series
• Authors: Fabian Latorre, Chenghao Liu, Doyen Sahoo, Steven C.H. Hoi
• Abstract summary: Dynamic Time Warping (DTW) has become the pragmatic choice for measuring distance between time series. It suffers from unavoidable quadratic time complexity when the optimal alignment matrix needs to be computed exactly. We introduce a new metric for time series data based on the Optimal Transport framework, called Optimal Transport Warping (OTW)
• Score: 75.69837166816501
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Dynamic Time Warping (DTW) has become the pragmatic choice for measuring distance between time series. However, it suffers from unavoidable quadratic time complexity when the optimal alignment matrix needs to be computed exactly. This hinders its use in deep learning architectures, where layers involving DTW computations cause severe bottlenecks. To alleviate these issues, we introduce a new metric for time series data based on the Optimal Transport (OT) framework, called Optimal Transport Warping (OTW). OTW enjoys linear time/space complexity, is differentiable and can be parallelized. OTW enjoys a moderate sensitivity to time and shape distortions, making it ideal for time series. We show the efficacy and efficiency of OTW on 1-Nearest Neighbor Classification and Hierarchical Clustering, as well as in the case of using OTW instead of DTW in Deep Learning architectures.

Related papers

• Deep Declarative Dynamic Time Warping for End-to-End Learning of Alignment Paths [54.53208538517505]
  This paper addresses learning end-to-end models for time series data that include a temporal alignment step via dynamic time warping (DTW) We propose a DTW layer based around bi-level optimisation and deep declarative networks, which we name DecDTW. We show that this property is particularly useful for applications where downstream loss functions are defined on the optimal alignment path itself.
  arXiv  Detail & Related papers  (2023-03-19T21:58:37Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Approximating DTW with a convolutional neural network on EEG data [9.409281517596396]
  We propose a fast and differentiable approximation of Dynamic Time Wrapping (DTW) We show that our methods achieve at least the same level of accuracy as other DTW main approximations with higher computational efficiency.
  arXiv  Detail & Related papers  (2023-01-30T13:27:47Z)
• Averaging Spatio-temporal Signals using Optimal Transport and Soft Alignments [110.79706180350507]
  We show that our proposed loss can be used to define temporal-temporal baryechecenters as Fr'teche means duality. Experiments on handwritten letters and brain imaging data confirm our theoretical findings.
  arXiv  Detail & Related papers  (2022-03-11T09:46:22Z)
• TC-DTW: Accelerating Multivariate Dynamic Time Warping Through Triangle Inequality and Point Clustering [6.502892821109196]
  The most popular algorithm used today is still the one developed seventeen years ago. The new solution, named TC-DTW, introduces Triangle Inequality and Point Clustering into the algorithm design. In experiments on DTW-based nearest neighbor finding, the new solution avoids as much as 98% (60% average) DTW distance calculations and yields as much as 25X (7.5X average) speedups.
  arXiv  Detail & Related papers  (2021-01-15T16:38:28Z)
• Matrix Profile XXII: Exact Discovery of Time Series Motifs under DTW [1.282368486390644]
  We present the first scalable exact method to discover time series motifs under Dynamic Time Warping. Our algorithm can admissibly prune up to 99.99% of the DTW computations.
  arXiv  Detail & Related papers  (2020-09-16T19:35:43Z)
• Approximated Bilinear Modules for Temporal Modeling [116.6506871576514]
  Two-layers in CNNs can be converted to temporal bilinear modules by adding an auxiliary-branch sampling. Our models can outperform most state-of-the-art methods on SomethingSomething v1 and v2 datasets without pretraining.
  arXiv  Detail & Related papers  (2020-07-25T09:07:35Z)
• Aligning Time Series on Incomparable Spaces [83.8261699057419]
  We propose Gromov dynamic time warping (GDTW), a distance between time series on potentially incomparable spaces. We demonstrate its effectiveness at aligning, combining and comparing time series living on incomparable spaces.
  arXiv  Detail & Related papers  (2020-06-22T22:19:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.