An average-compress algorithm for the sample mean problem under dynamic time warping

DOI10.1007/S10898-023-01294-9MaRDI QIDQ6164020zbMATH OpenOpenAlexFDO

Authors

Publication date 26 July 2023

Published in Journal of Global Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1909.13541

zbMATH Keywords

Fréchet functionheuristicnonconvex optimizationtime series averaging

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Economic time series analysis (91B84)

Abstract: Computing a sample mean of time series under dynamic time warping (DTW) is NP-hard. Consequently, there is an ongoing research effort to devise efficient heuristics. The majority of heuristics have been developed for the constrained sample mean problem that assumes a solution of predefined length. In contrast, research on the unconstrained sample mean problem is underdeveloped. In this article, we propose a generic average-compress (AC) algorithm for solving the unconstrained problem. The algorithm alternates between averaging (A-step) and compression (C-step). The A-step takes an initial guess as input and returns an approximation of a sample mean. Then the C-step reduces the length of the approximate solution. The compressed approximation serves as initial guess of the A-step in the next iteration. The purpose of the C-step is to direct the algorithm to more promising solutions of shorter length. The proposed algorithm is generic in the sense that any averaging and any compression method can be used. Experimental results show that the AC algorithm substantially outperforms current state-of-the-art algorithms for time series averaging.

Recommendations

• Exact mean computation in dynamic time warping spaces
• Sufficient conditions for the existence of a sample mean of time series under dynamic time warping
• Summarizing a set of time series by averaging: from Steiner sequence to compact multiple alignment
• On computing exact means of time series using the move-split-merge metric
• A global averaging method for dynamic time warping, with applications to clustering

Cites work

• A global averaging method for dynamic time warping, with applications to clustering
• A review on distance based time series classification
• Adaptive Global Time Sequence Averaging Method Using Dynamic Time Warping
• Dimensionality reduction for fast similarity search in large time series databases
• Dynamic programming algorithm optimization for spoken word recognition
• Exact mean computation in dynamic time warping spaces
• Generalized median graph computation by means of graph embedding in vector spaces
• scientific article; zbMATH DE number 5668397 (Why is no real title available?)
• scientific article; zbMATH DE number 1194132 (Why is no real title available?)
• scientific article; zbMATH DE number 3053873 (Why is no real title available?)
• Nonparametric inference on manifolds. With applications to shape spaces
• Object oriented data analysis: sets of trees
• On the approximation of curves by line segments using dynamic programming
• Overview of object oriented data analysis
• Shape Manifolds, Procrustean Metrics, and Complex Projective Spaces
• Statistical graph space analysis
• Sufficient conditions for the existence of a sample mean of time series under dynamic time warping
• Tight hardness results for consensus problems on circular strings and time series

Cited in

(1)

• Exact mean computation in dynamic time warping spaces

This page was built for publication: An average-compress algorithm for the sample mean problem under dynamic time warping

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6164020)