{"ID":5937741,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-08T16:41:18.03494969Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.04397","arxiv_id":"2607.04397","title":"Time Series Decomposition using the Fréchet Distance","abstract":"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.","short_abstract":"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 all...","url_abs":"https://arxiv.org/abs/2607.04397","url_pdf":"https://arxiv.org/pdf/2607.04397v1","authors":"[\"Anne Driemel\",\"Jan Höckendorff\",\"Ioannis Psarros\",\"Christian Sohler\"]","published":"2026-07-05T16:41:29Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}