Nonsmooth Analysis and Subgradient Methods for Averaging in Dynamic Time Warping Spaces
This work addresses time series averaging for pattern recognition systems, offering incremental improvements in algorithm stability and efficiency for online and large-sample applications.
The paper tackles the problem of finding a sample mean in dynamic time warping (DTW) spaces, proposing subgradient methods that generalize existing algorithms like DTW Barycenter Averaging (DBA), with empirical results showing the stochastic subgradient (SSG) algorithm is more stable and finds better solutions in shorter time than DBA on average for increasing sample sizes.
Time series averaging in dynamic time warping (DTW) spaces has been successfully applied to improve pattern recognition systems. This article proposes and analyzes subgradient methods for the problem of finding a sample mean in DTW spaces. The class of subgradient methods generalizes existing sample mean algorithms such as DTW Barycenter Averaging (DBA). We show that DBA is a majorize-minimize algorithm that converges to necessary conditions of optimality after finitely many iterations. Empirical results show that for increasing sample sizes the proposed stochastic subgradient (SSG) algorithm is more stable and finds better solutions in shorter time than the DBA algorithm on average. Therefore, SSG is useful in online settings and for non-small sample sizes. The theoretical and empirical results open new paths for devising sample mean algorithms: nonsmooth optimization methods and modified variants of pairwise averaging methods.