PaperlayerView exact revision on arXiv

Source-linked AI summary

Sliding Windows and Persistence: An Application of Topological Methods to Signal Analysis

Jose Perea, John Harer

arXiv:1307.6188v2math.ATmath.ST

TL;DR

The paper addresses how to detect periodicity and quasi-periodicity in signals using a topological analysis of sliding-window embeddings. It combines Fourier approximation, Vietoris–Rips persistent homology, and stability results, showing that maximum persistence quantifies periodicity while the associated diagrams admit convergence guarantees.

  • Problem

    The paper seeks a new way to find periodicity and quasi-periodicity in signals by adding computational topology to sliding-window analysis.

  • Method

    The method analyzes sliding-window point clouds with Vietoris–Rips persistent homology, using Fourier approximations and stability to study general periodic functions.

  • Results

    Maximum persistence quantifies signal periodicity, while the resulting persistence diagrams have structural and convergence properties under the paper’s assumptions.

  • Takeaways & Limitations

    The framework provides a topological periodicity score based on point-cloud roundness and supports approximation of generic periodic signals through truncated Fourier series.

  • Takeaways & Limitations

    The method depends critically on denoising, because results degrade considerably on raw synthetic data without preprocessing.

Abstract

from arXiv · show

We develop in this paper a theoretical framework for the topological study of time series data. Broadly speaking, we describe geometrical and topological properties of sliding window (or time-delay) embeddings, as seen through the lens of persistent homology. In particular, we show that maximum persistence at the point-cloud level can be used to quantify periodicity at the signal level, prove structural and convergence theorems for the resulting persistence diagrams, and derive estimates for their dependency on window size and embedding dimension. We apply this methodology to quantifying periodicity in synthetic data sets, and compare the results with those obtained using state-of-the-art methods in gene expression analysis. We call this new method SW1PerS which stands for Sliding Windows and 1-dimensional Persistence Scoring.

1. Introduction

The paper introduces a topological approach to detecting periodicity and quasi-periodicity by analyzing the shape of sliding-window point clouds with persistent homology.

  • Motivation: The method combines sliding-window embeddings with computational topology to find periodicity and quasi-periodicity in signals.It extends established time-delay reconstruction with a topological component.
  • Background: Persistent homology measures shapes and function features, while 1-dimensional persistence captures circular structure in point clouds.Noise can reduce persistence, and insufficient sampling can prevent circular structure from appearing.
  • Novelty: The approach studies the geometry and topology of the sliding-window point cloud rather than relying on conventional signal-analysis methods.It interprets repeated patterns through the circularity or roundness of the generated point cloud.
  • Contribution: Maximum persistence occurs when the window size corresponds to the signal’s natural frequency, making 1D persistence a periodicity measure.The paper extends this interpretation to periodicity and quasi-periodicity.
  • Scope: The paper develops structural and convergence results for sliding-window persistence diagrams and derives estimates for their dependencies.The outlined analyses address approximations, geometry, embedding dimension, and window size.

2. Definitions and Motivation

The paper represents a signal through overlapping time-delay samples, then connects the resulting point-cloud geometry to periodicity through a computable persistence score.

  • Definitions: A sliding-window embedding maps each time t to the vector of signal values sampled at t, t+τ, through t+Mτ.The resulting points lie in R^(M+1), and the window-size Mτ is a critical parameter.
  • Motivating example: For f(t) = cos(Lt), the sliding-window embedding traces an ellipse in a two-dimensional subspace of R^(M+1).Its axes are determined by the square roots of the eigenvalues of A.
  • Motivating example: The ellipse is roundest exactly when L(M + 1)τ ≡ 0 mod π.This condition identifies the window placements that maximize the smaller eigenvalue.
  • Motivating example: Roundness is maximized when the window size is close to the period length, or resonates with the signal’s natural frequency.The same intuition motivates using point-cloud circularity to study generic periodic functions.
  • Persistence score: Maximum persistence in the Vietoris–Rips filtration provides a computable measure of sliding-window point-cloud roundness.The paper uses this quantity to study periodicity and period.
  • Approach: The analysis combines trigonometric-polynomial geometry, Fourier approximation, and persistence-diagram stability to study generic periodic functions.This supplies the approximation route from tractable special cases to general periodic signals.

3. Background: Persistent Homology

The background develops persistent homology through simplicial complexes and filtrations, using Vietoris–Rips complexes to compute persistence diagrams from point clouds.

  • Homology: A simplicial complex is a finite collection of simplices closed under taking faces, and simplicial homology is built from chains, cycles, and boundaries.The k-th homology group is Z_k/B_k, whose rank is the mod-p Betti number.
  • Persistence: A filtration is a nested sequence of subcomplexes, and a homology class’s persistence records the interval between its birth and death.Persistence is the difference j − i when a class is born at K_i and dies entering K_j.
  • Persistence diagrams: Persistence diagrams encode the birth and death coordinates of homology classes separately for each dimension.The paper uses dgm to denote the relevant persistence diagram when dimension is clear.
  • Vietoris–Rips complexes: A Vietoris–Rips complex contains a simplex exactly when all pairwise distances among its vertices are at most r.Its edges determine the higher-dimensional simplices.
  • Vietoris–Rips complexes: Increasing r produces a Vietoris–Rips filtration, whose homology induces the persistence diagram used for a point cloud.Only finitely many pairwise-distance values need to be considered for a finite point cloud.
  • Stability: Persistence is stable under perturbations of point clouds measured by Hausdorff or Gromov–Hausdorff distance.This stability supports comparing diagrams generated from nearby data.

4. The Approximation Theorem

The paper approximates generic signals by truncated Fourier series, transfers sliding-window geometry through stability bounds, and establishes convergence of the resulting persistence diagrams.

  • Approximation strategy: Generic periodic signals are analyzed through Fourier-series approximations because sliding-window embeddings of sine and cosine components are tractable.The approximation argument combines Fourier analysis with persistence-diagram stability.
  • Operator bounds: The sliding-window operator is a bounded linear map from continuous periodic functions to continuous functions valued in R^(M+1).The embedding norm is controlled by the sampled signal values across the window.
  • Stability under approximation: Hausdorff bounds between the original and Fourier-truncated sliding-window point clouds yield bottleneck-distance bounds for their persistence diagrams.This transfers approximation control from point clouds to persistence diagrams.
  • Approximation theorem: The Approximation Theorem states that persistent homology of a sliding-window point cloud can be understood in the limit through truncated Fourier series.The result applies to functions with the stated smoothness assumptions.
  • Scope: The arguments extend to functions in the Sobolev space W^1,2(T), while smoother functions yield explicitly faster approximation rates.The paper states the C^k formulation for interpretive reasons, although the key proposition only requires f′ ∈ L2(T).

5. The Geometric Structure of SWM,τSNf

The section characterizes sliding-window embeddings of truncated Fourier series geometrically, clarifying how embedding dimension and window size affect information retention and orthogonality. It shows that frequency-matched windows produce structured, mutually orthogonal components whose normalized point clouds trace curves on tori.

  • Embedding dimension: The embedding dimension M + 1 captures function detail but increasing it can make the Rips complex computationally infeasible.Higher dimensions may require denser point clouds, increasing the size of the Rips complex.
  • Embedding dimension: For trigonometric polynomials, no information is lost exactly when the embedding dimension exceeds twice the maximum frequency.The linear components can recover the original truncated signal when the relevant vectors are linearly independent.
  • Embedding dimension: Under Mτ < 2π, the vectors u0, u1, v1, …, uN, vN are linearly independent if and only if M ≥ 2N.This proposition supplies the precise dimension threshold for independence.
  • Window size: The maximum persistence of the sliding-window cloud for cos(Lt) is largest when the window size is proportional to the underlying frequency.For truncated Fourier series, the corresponding proportionality is described using the factor M/(M + 1).
  • Window size: Choosing τ = 2π/[L(M + 1)] for an L-periodic function makes the potentially nonzero harmonic components mutually orthogonal.The same condition enforces orthogonality within and across relevant Fourier harmonics.
  • Geometric structure: After centering and normalization, the sliding-window curve can be viewed in an N-torus, with projection onto the nth circle traversing it n times at constant speed.For N = 3, the curve is represented in flat coordinates and shown with projections onto the xy-, xz-, and yz-planes.

6. The Persistent Homology of ϕτ and SWM,τf

This section establishes convergence results for persistence diagrams from centered and normalized sliding-window embeddings, including limits as embedding resolution increases and sampling becomes denser. It also addresses how changing window and embedding parameters affects comparison and convergence.

  • Structural and approximation issues: Increasing the embedding dimension yields better approximations, but the embedded point cloud itself changes, complicating direct comparisons across dimensions.The authors note that the ambient sequence space is not complete, so convergence cannot be assumed without additional structure.
  • First convergence theorem: For finite sample sets, the persistence diagrams of pointwise-centered and normalized sliding-window embeddings form a Cauchy sequence in Bottleneck distance as the embedding dimension increases.This holds for any field of coefficients under the stated periodicity and sampling conditions.
  • First convergence theorem: The limiting diagram dgm∞(f, T, w) is obtained as the embedding dimension tends to infinity while the window size remains approximately w.The construction applies to centered and normalized versions of either the original signal or its Fourier approximations.
  • First convergence theorem: For C1 periodic functions, persistence diagrams from the original sliding-window embeddings also converge because Fourier approximation errors vanish and persistence is stable under Hausdorff perturbations.The proof compares the original and approximated point clouds and combines convergence of the approximations with Bottleneck stability.
  • Second convergence theorem: As the finite sampling set T becomes dense in the circle, the limiting diagrams converge to a diagram dgm∞(f, w) under the theorem’s continuity assumptions.The comparison is controlled using the modulus of continuity of f and Hausdorff distance between sampling sets.
  • Persistence estimates: Theorem 6.8 provides an estimate for maximum persistence under finite sampling, window-size, and embedding-dimension conditions, including rational coefficients.The bound is stated for finite T with dH(T, T) < δ and extends to all N when homology uses Q coefficients.

7. Examples: Quantifying Periodicity of Sampled Signals

The experiments test whether SW1PerS ranks periodic signals independently of waveform shape and classifies periodic versus non-periodic signals under noise. SW1PerS uses centered, normalized sliding-window point clouds and 1D persistence, with denoising improving classification results.

  • Experimental design: SW1PerS assigns periodicity scores to sampled signals and compares them with JTK CYCLE, Lomb-Scargle, and Total Persistent Homology.Signals are spline-interpolated, transformed into centered and normalized sliding-window point clouds, and scored using 1D persistence.
  • 7.1. Shape Independence: The synthetic ranking experiment includes cosine-like, saw-tooth, damped, spiky, square-wave, and other periodic shapes across multiple noise levels.Signals are sampled at 50 evenly spaced time points; sliding-window parameters use N = 10, coefficients in F11, and L = 2, 3, 4, with the best score reported.
  • 7.1. Shape Independence: Except for SW1PerS, the competing algorithms show clear preferences for particular signal shapes.The paper contrasts these shape biases with SW1PerS’s geometric scoring interpretation and more reasonable score distribution.
  • 7.2. Classification Rates: ROC analysis evaluates classification by comparing True Positive Rate with False Positive Rate and using area under the ROC curve.The synthetic data contains periodic positive cases and constant or linear negative cases, with Gaussian noise at 0%, 25%, and 50% of signal amplitude.
  • 7.2. Classification Rates: SW1PerS performs comparably to Lomb-Scargle in most cases and outperforms it for peaked and damped profiles at high noise levels.Lomb-Scargle remains favorable for trended cosines and cosines, while the comparison includes ROC curves and AUC values for each periodic shape.
  • 7.2. Classification Rates: Without moving-average and mean-shift preprocessing, SW1PerS classification results degrade considerably.The raw-data analysis in Figure 7 is explicitly compared with the denoised pipeline in Figure 6.

8. Final Remarks

The paper establishes a theoretical foundation for persistent-homology analysis of sliding-window embeddings, including parameter dependencies and coefficient choices. It identifies maximum persistence as a periodicity measure, while positioning broader feature development and applications as future work.

  • The paper presents the first full theoretical analysis of persistent homology for structure in time-series data, including persistence dependencies on embedding dimension and window size.
  • The analysis establishes which coefficient-field primes may cause problems, allowing them to be avoided in advance rather than selected through random testing.
  • The paper relates 2Wq(dgm, dgm∆) to a smoother periodicity signature, with larger q shifting emphasis from topological noise and fine attributes toward large topological events.
  • Section 6.3 provides the first explicit computation of a persistence diagram for a parametrized space and introduces Fourier approximation for explicit diagram computations.
  • Maximum persistence measures sliding-window point-cloud roundness and occurs when window size matches the signal’s natural frequency, quantifying periodicity and quasi-periodicity.
  • Future work includes proving the conjectured optimal window size, establishing filtering properties, applying SW1PerS to broader datasets, and extending the feature set beyond maximum persistence.
Loading 1307.6188v2…