Time Series Decomposition using the Fréchet Distance
This is a novel problem formulation for time series analysis, but the results are theoretical and incremental, with no empirical validation or comparison to existing methods.
This paper introduces the Fréchet decomposition problem, which decomposes a set of univariate time series into a small set of base curves minimizing the sum of Fréchet distances. For a single base curve, a (1+ε)-approximation algorithm is provided, and an exact algorithm is given for the projection distance problem.
In this paper, we introduce a new data analysis problem that aims to decompose a set of univariate time series into a small set of $k$ base curves of length at most $l$ such that the sum of Fréchet distances of the time series to a ``Fréchet combination'' of the base curves is minimized. Here, a Fréchet combination allows to combine individually scaled base curves using a $k$-dimensional traversal. We call the problem of finding a set of optimal base curves the Fréchet decomposition problem and we consider two variants: (a) the base curves can be arbitrary curves of bounded length and (b) the curves come from a given finite set of candidate curves. We think of the Fréchet decomposition problem as a Fréchet variant of principal component analysis. For the case of a single base curve we develop a $(1+\varepsilon)$-approximation algorithm for the Fréchet decomposition problem. Additionally we give an exact algorithm for the projection distance problem that asks to compute the distance of one given time series to a given set of $k$ base curves. This allows us to design an exact algorithm for the Fréchet decomposition problem for general $k$ when curves come from a fixed candidate set.