Abstract
Generalized Persistence Diagrams (GPDs) provide a robust framework for multi-parameter persistence in Topological Data Analysis (TDA), yet their computational complexity hinders large-scale application. This paper presents a novel sparsification method that optimizes the selection of intervals using gradient descent. By embedding intervals into $\mathbb{R}^6$ and minimizing a differentiable proxy for the erosion distance, the approach achieves significant speedups (5x to 15x) on time-series benchmarks while preserving, and often improving, classification performance.
Introduction
In TDA, persistence is used to track topological features (like holes or loops) across different scales. While single-parameter persistence is well-established, many real-world datasets require multi-parameter persistence (e.g., looking at distance and density simultaneously). The Generalized Persistence Diagram (GPD) is the gold standard for capturing this rich information. However, it faces a massive "scalability wall": computing a full GPD requires evaluating an astronomical number of intervals, making it computationally prohibitive for large-scale machine learning. Researchers often settle for a fixed, "sparse" grid of intervals, but this manual selection often leads to a loss of critical information.
Proposed Method
The authors propose a way to automatically optimize the selection of intervals using gradient descent, transforming a discrete selection problem into a continuous optimization task.
Key Innovations
- Sparse Erosion Distance: The authors adapted the standard "erosion distance" for GPDs into a version that works when comparing diagrams defined on different interval sets.
- Vectorization ($\mathbb{R}^6$ Embedding): Each interval $I$ is represented as a point in 6D space, capturing its coordinates $(x, y)$ and lengths $a, b, c, d$. This allows the use of standard gradient descent solvers like PyTorch.
- The Independence Breakthrough: Crucially, the authors proved that when comparing GPDs of the same data over different domains, the distance depends only on the domains themselves. This means they can optimize the interval set once without recomputing the expensive GPDs at every single step of the gradient descent, bypassing the slowest part of the TDA pipeline.
- Differentiable Loss: The derived loss function is Lipschitz stable and differentiable almost everywhere, ensuring smooth convergence during optimization.
Experimental Evaluation
The method was evaluated on 18 time-series datasets from the UCR repository, including medical (ECG200), motion (GunPoint), and sensor (ItalyPowerDemand) data. Time-series were converted into point clouds using time-delay embedding before TDA features were extracted.
Key Results
- Efficiency: The optimized sparse GPDs were computed 5.4x to 15.7x faster than the full GPDs.
- Accuracy: Despite using significantly fewer intervals, the optimized GPDs achieved classification accuracies comparable to—and in several cases better than—the full GPDs. A small, "smart" set of 400 optimized intervals often captured more relevant topological information than a massive, "dumb" grid of 1,600 intervals.
- Optimization Success: In almost all cases, the "Optimized Sparse" version outperformed the "Initial Sparse" version (random/grid start), proving that gradient descent successfully found more discriminative topological features.
Limitations and Future Work
The current work limits intervals to those with at most two minimal points and one maximal point to keep the $\mathbb{R}^6$ embedding simple. Future research may explore more complex interval shapes and dataset-dependent terms in the loss function to further refine the discriminative power of sparse GPDs. Additionally, developing formal stopping criteria for the optimization remains an open area for development.
Summary updated