Time Series Averaging under Time Warping

Time Series such as sensor signals, speech or stock prices generally vary in length and speed. To cope with such temporal variations, warping distances such as Dynamic Time Warping (DTW) are often used. In recent years, the problem of finding an average of time series under DTW has been faced and many properties such as the existence, uniqueness, complexity, exact solutions and heuristic solutions have been studied. In practice, a DTW average may not ‘look like’ an averagely shaped curve of the sample time series. This is reasoned in the nature of the DTW distance itself. Therefore, several alternative warping distances have been proposed. However, as of today, they have rarely been used for computing average curves. The goal of this thesis it to explore the behavior of different warping distances for time series averaging. One challenge is to evaluate such averages quantitatively and qualitatively.

Prerequisites

  • Good programming skills (Python, Matlab or Java)
  • Solid basics in Analysis and Linear Algebra, ideally experience with gradient descent optimizers
  • Interest in theoretically oriented research

Literature

  • Schultz, D., & Jain, B. (2018). Nonsmooth analysis and subgradient methods for averaging in dynamic time warping spaces. Pattern Recognition74, 340-358.
  • Petitjean, F., Ketterlin, A., & Gançarski, P. (2011). A global averaging method for dynamic time warping, with applications to clustering. Pattern recognition44(3), 678-693.
  • Zhao, J., & Itti, L. (2018). shapedtw: Shape dynamic time warping. Pattern Recognition74, 171-184.
  • Keogh, E. J., & Pazzani, M. J. (2001, April). Derivative dynamic time warping. In Proceedings of the 2001 SIAM international conference on data mining (pp. 1-11). Society for Industrial and Applied Mathematics.
  • Cuturi, M., & Blondel, M. (2017, July). Soft-dtw: a differentiable loss function for time-series. In International Conference on Machine Learning (pp. 894-903). PMLR.
  • Marteau, P. F. (2008). Time warp edit distance with stiffness adjustment for time series matching. IEEE transactions on pattern analysis and machine intelligence31(2), 306-318.
  • And own literature research