A Stable Measure of Similarity for Time Series using Persistent Homology

Abstract

Persistent homology, the study of holes that appear in data as one thickens balls centered around its points over time, has theoretically guaranteed stability. That is, small data perturbations guarantee small changes in the lifetimes of these holes. This stability has been used to construct a measure of periodicity for a single univariate time series, denoted score(f1). One popular measure of similarity between two time series is percent determinism (%DET), which measures the correlation between two time-series embeddings. We introduce a novel persistent-homology based measure of time-series similarity which we denote the bi-conditional periodicity score, score(f1,f2). We prove the stability of our measure under small time series and frequency perturbations, as well as the existence of a minimum embedding dimension for the convergence of our score. Our latter result implies that larger embedding dimensions may be necessary to reach desired levels of convergence. Since pairwise distances between points in these larger dimensions may start to concentrate, we also prove the stability of our measure under dimension reduction which guarantees that as long as the first K principal components capture a majority of the variance under orthogonal projection, the score will undergo small changes. We next introduce an algorithm for computing the bi-conditional periodicity score and deduce its computational complexity as O(N log N + PK^2 + P^6) for N the number of time series points, P the number of embedding points, and K the number of principal components. We experimentally verify the greater stability of our measure in comparison with %DET on both synthetic time series as well as real climate data. As well, score(f1,f2) requires only one parameter for its computation while %DET requires four.