Time-Warping Invariants of Multidimensional Time Series
- PDF / 1,015,029 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 11 Downloads / 214 Views
Time-Warping Invariants of Multidimensional Time Series Joscha Diehl1 · Kurusch Ebrahimi-Fard2 · Nikolas Tapia3,4
Received: 6 August 2019 / Accepted: 6 May 2020 © The Author(s) 2020
Abstract In data science, one is often confronted with a time series representing measurements of some quantity of interest. Usually, in a first step, features of the time series need to be extracted. These are numerical quantities that aim to succinctly describe the data and to dampen the influence of noise. In some applications, these features are also required to satisfy some invariance properties. In this paper, we concentrate on time-warping invariants. We show that these correspond to a certain family of iterated sums of the increments of the time series, known as quasisymmetric functions in the mathematics literature. We present these invariant features in an algebraic framework, and we develop some of their basic properties. Keywords Time series analysis · Time warping · Standing-still invariance · Signature · Quasisymmetric functions · Quasi-shuffle product · Hoffman’s exponential · Area-operation · Hopf algebra
1 Motivation Given a discrete time series x = (x0 , x1 , . . . , xN ) ∈ (Rd )N ,
B N. Tapia
[email protected] J. Diehl [email protected] K. Ebrahimi-Fard [email protected]
1
Institut für Mathematik und Informatik, Universität Greifswald, Walther-Rathenau-Str. 47, 17489 Greifswald, Germany
2
Department of Mathematical Sciences, NTNU, 7491 Trondheim, Norway
3
Weierstraß-Institut Berlin, Mohrenstr. 39, 10117 Berlin, Germany
4
Technische Universität Berlin, Str. des 17. Juni 136, 10623 Berlin, Germany
J. Diehl et al.
Fig. 1 Example of time warping in the case of a discrete time series in d = 1 dimensions.
where N ≥ 1 is some arbitrary time horizon, our foremost, and original, motivation stems from the desire to extract features from x that are invariant to time warping. The precise definition of the latter will be given in Section 4, but Figure 1 illustrates what we mean by time warping: the time series is allowed to “stand still” or to “stutter” (this term is used in [47]), which means that x has repetitions of values at consecutive time steps (here at time t = 3). Remark 1.1 In this section we consider the notationally simpler case d = 1, that is, when x ∈ RN . Our interest is prompted, on the one hand by the extensive literature on the dynamic time warping (DTW) distance [5], a distance on discrete time series that is invariant to time warping. In [47] it is stated that “the time warping distance . . . does not lead to any natural features”. Our work aims to provide those missing “natural” features. On the other hand the following example illustrates where such invariant features will become useful. Example 1.2 Assume that there is a deterministic time series x ∈ RN which models some “prototype” evolution of a quantity, say the prototype heartbeat in a patient’s ECG. This prototype is unknown, but one records a lot of samples of it run at different speeds and contaminated by n
Data Loading...
