A persistence landscapes toolbox for topological statistics

Peter Bubenik; Pawel Dlotko

Source-linked AI summary

A persistence landscapes toolbox for topological statistics

Peter Bubenik, Pawel Dlotko

arXiv:1501.00179v3Dec 31, 2014cs.CGcs.MSmath.ATstat.CO

TL;DR

The paper addresses the difficulty of combining persistent-homology summaries with statistics and machine learning. It develops efficient algorithms and publicly available software for persistence landscapes, their averages, and distances, and reports that low-dimensional landscapes distinguish samples from spheres and boxes of varying dimensions. The authors conclude that these methods can support intrinsic-dimension estimation, while computation choices depend on the input distribution and grid accuracy.

Problem
Persistence diagrams and barcodes provide multiscale topological summaries but are difficult to average and use directly with statistics and machine learning.
Method
The paper develops exact and grid-based algorithms for computing persistence landscapes, their averages, and distances, and implements them in publicly available software.
Results
Low-dimensional persistent landscapes of points sampled from spheres and boxes of varying dimensions differ, supporting experiments that estimate intrinsic dimension.
Takeaways & Limitations
The presented techniques may eventually allow explicit estimation of a dataset's intrinsic dimension and can be used for hypothesis testing and classification.
Takeaways & Limitations
Exact and grid-based computations have different practical advantages depending on point concentration, parameter range, grid spacing, and desired accuracy.

Abstract

from arXiv · show

Topological data analysis provides a multiscale description of the geometry and topology of quantitative data. The persistence landscape is a topological summary that can be easily combined with tools from statistics and machine learning. We give efficient algorithms for calculating persistence landscapes, their averages, and distances between such averages. We discuss an implementation of these algorithms and some related procedures. These are intended to facilitate the combination of statistics and machine learning with topological data analysis. We present an experiment showing that the low-dimensional persistence landscapes of points sampled from spheres (and boxes) of varying dimensions differ.

1. Introduction

The paper frames persistence landscapes as linear, statistical summaries of persistent homology and develops algorithms and software to compute, average, and compare them. It positions these tools as a bridge between topological data analysis, statistics, and machine learning.

Contributions: The paper develops algorithms for persistence landscapes, their averages, and distances between averages, including exact and grid-based approaches.Grid rounding perturbs persistence diagrams by at most δ/2 in bottleneck distance under the stated assumption.
Implementation: The authors provide a publicly available implementation with plotting and related procedures for applying persistence landscapes in topological data analysis.The implementation supports both exact computations and grid-based computations.
Motivation: Persistent homology gives a multiscale description of data topology, but persistence diagrams and barcodes are difficult to use for statistical averaging.The persistence landscape provides a linear summary that can be treated as a feature map in a Hilbert space.
Motivation: The persistence landscape is a functional summary of persistence modules that preserves information while supporting averages and machine-learning kernels.Related functional summaries include persistent Betti number functions, smoothed persistence diagrams, and silhouettes.
Algorithms: The main landscape algorithm runs in O(n^2), while grid-based computation runs in O(mn log n).For N landscapes, the paper gives average and distance computations with exact complexity O(n^2N log N) and grid-based complexity O(mnN).

2. Data structures

The data structures encode persistence landscapes exactly through critical points or approximately on a finite grid. They support finite or infinite birth-death intervals and represent landscapes and their linear combinations for computation.

Input: The algorithms take n birth-death pairs, representing persistent homology classes as points in a persistence diagram or intervals in a barcode.The finite-input algorithm assumes b and d are finite, while an appendix variant accommodates infinite intervals.
Output: Exact landscapes are encoded by sorted vectors of critical points, from which consecutive points recover each piecewise-linear λk by interpolation.This representation is exact, unlike discrete-grid representation in general.
Grid representation: Grid-based landscapes use a two-dimensional array V with entries V[k][i] = λk(i), followed by linear interpolation.Grid inputs are rescaled to values in {0, 2, 4, . . . , 2m}.
Linear combinations: Linear combinations of persistence landscapes are encoded using the same piecewise-linear representation as individual landscapes.This supports subsequent averaging and distance calculations.
Output: Only finitely many landscape functions are nonzero: λk = 0 for k greater than some K ≤ n.K is also the largest rank of the linear maps in the persistence module.

3. Algorithms

The paper presents algorithms for constructing persistence landscapes, linear combinations, and distances, with exact and grid-based variants. Their complexity is governed by the number of input pairs, nonzero landscapes, grid size, and landscape critical points.

The toolbox computes persistence landscapes, linear combinations, and distances between such linear combinations.
Algorithm 1 constructs landscapes in O(n log(n) + nK), or O(n^2) because K ≤ n.
Algorithm 2 computes grid-based landscapes in O(mn + mK log K), which is O(mn log n).
Computing only the first ⌈log n⌉ or a fixed number of landscapes takes O(n log n), and takes O(n) when the input is already sorted.
The persistence landscape has P = 3n + 2p critical points, with P ≤ n^2 + 2n, so the algorithms are optimal in the worst case.
Constructing all linear combinations has complexity O(n^2N^2), whereas computing an average persistence landscape has complexity O(n^2Nlog(N)).
Distances between landscapes with at most n birth-death pairs can be computed in O(n^2), while grid-based distances require O(Km), or O(mn).

4. Experiments

Experiments evaluate persistence landscapes on point clouds sampled from spheres and boxes of varying dimensions, and compare landscape-distance computation times. Low-dimensional landscapes differ across dimensions, supporting intrinsic-dimension estimation.

4.1. Points sampled from S^d: The experiments test whether persistent homology can determine the dimension of points sampled from lower-dimensional spheres embedded in R^D.
4.1. Points sampled from S^d: For dimensions 2–10, the study repeatedly sampled 100 points from spheres, normalized their average pairwise distance, and computed Vietoris–Rips persistent homology.Each dimension used 1000 point clouds; filtration values were rescaled to 0–100.
4.1. Points sampled from S^d: Average landscapes in degrees 0, 1, and 2 differed across sphere dimensions, with their L1, L2, and L∞ distances reported in Figure 6.
4.1. Points sampled from S^d: A 10,000-permutation test found no shuffled distance exceeding the original distance for any pair of sphere dimensions, indicating strong statistical differences.The test used significance level α = 0.05.
4.2. Points sampled from [0,1]^d: The analogous box experiment also found no shuffled distance exceeding the original in 10,000 permutations, and the combined experiments support intrinsic-dimension estimation.
4.4. Computing distance matrices: Additional experiments compare bottleneck and Wasserstein distances with corresponding landscape distances and measure computation times for landscape and distance-matrix calculations.Figure 7 uses a logarithmic vertical axis.

5. Specification of the implementation

The implementation provides programs and file formats for constructing, averaging, plotting, and analyzing persistence landscapes. It supports persistence diagrams, landscapes, and linear combinations across common operating systems.

Implementation and programs: The implementation includes a library and user programs intended to make persistence-landscape procedures accessible to both C++ users and nonprogrammers.
Implementation and programs: The package was compiled for Linux, Windows, and OS X, and the paper’s implementation results were obtained with these programs.
File formats: Input files can contain persistence diagrams, persistence landscapes, linear combinations of landscapes, or lists of files containing these objects.
Toy example: The toy example samples 50n noisy points from unions of n unit circles for n ∈ {1, 2, . . . , 5}, producing persistence data for demonstrations.
Core procedures: The programs compute average landscapes, generate plotting files, calculate norms and distance matrices, and perform permutation tests.

5.5. Norms of landscapes.

The section specifies norm, distance-matrix, permutation-test, and classification procedures built from persistence landscapes. A toy classifier performs well overall, with one explained outlier.

Norms and distance matrices: The norms program computes p-norms of input landscapes or linear combinations, including the supremum norm when p = −1.
Norms and distance matrices: The distance-matrix program computes Lp distances from input diagrams or landscapes and writes the resulting matrix to a text file.
Permutation tests: The permutation-test program compares classes of persistence intervals or landscapes using a chosen norm and outputs a matrix of p-values.The procedure may take substantial time.
Permutation tests: For the N-circle sample test, all p-values were 0, consistent with the strongly different persistence landscapes of the classes.
Classification: The single-dimension classifier builds one average landscape per class and assigns each input to the class with the smallest chosen Lp distance.
Classification: The classifier worked very well overall, but one 4-circle case was misclassified because one circle’s persistence interval had relatively short lifetime.

5.9. A classifier based on all dimensions.

The paper also provides a classifier that uses persistence data from more than one homological degree.

5.9. A classifier based on all dimensions.: ClassifierBasedOnAllDimensions extends the single-dimension classifier by using persistence data from more than one degree.

6. Exact versus grid based computations.

The toolbox supports both exact and grid-based persistence-landscape computations, with the better choice depending on diagram structure and desired accuracy. Grid estimates have explicit error bounds, though those bounds may be conservative for average landscapes.

Grid-based implementations can be faster when many persistence-diagram points are concentrated in a small region.
Exact implementations can be superior when birth and death parameters span a wide range, because accurate grids may require many points.
Grid spacing δ yields an L∞ error bound of δ/2.
With grid size m and K nonzero landscape functions, the L1 error is bounded by K(m −1)δ2/2.
The stated error bounds may substantially overestimate average-landscape errors because observed slopes are often far from ±1.

7. Configuration of the library.

The Persistence Landscape Toolbox is distributed as C++ programs configured through a shared file. The configuration file stores basic library parameters, including the constant used to represent infinity.

The library consists of C++ programs, with each .cpp file containing a ready-to-use program.
Programs require a configure file in the folder from which they are run.
The configure file contains basic configuration parameters, including the library’s representation of infinity.

8. Conclusion

The paper concludes with asymptotically optimal algorithms and an implementation for persistence-landscape computation, averaging, and distances. It demonstrates applications to hypothesis testing and classification and identifies software improvement as future work.

The authors provide asymptotically optimal algorithms for computing persistence landscapes, their averages, and distances between average landscapes.
The implemented algorithms are demonstrated in hypothesis testing and classification.
Future work aims to improve the algorithms and related software and increase their usefulness.

Appendix A. Persistence landscapes for barcodes with infinite intervals

The appendix extends persistence landscapes to barcodes containing infinite birth or death intervals. It also generalizes the landscape-construction algorithm to such barcodes.

The persistence-landscape definition is extended to birth-death pairs with −∞≤b < d ≤∞.
For an interval with infinite birth or death, the appendix supplies corresponding piecewise definitions for the landscape function.
Algorithm 4 generalizes Algorithm 1 to construct landscapes from barcodes that may contain infinite intervals.

Algorithm 4: Compute the persistence landscape.

The algorithm computes the persistence landscape from birth–death pairs by ordering the input and iteratively constructing lists of critical points. It returns the resulting collection of landscape functions.

The algorithm accepts birth–death pairs, sorts them by increasing birth time and then decreasing death time, and processes them sequentially.The input permits infinite birth or death values within the stated ordering constraints.
For each landscape level Lk, it initializes a list, removes the next pair, and handles the special pair (−∞, ∞) separately.The procedure advances through the ordered set while maintaining the current pair and a pointer to the next term.
When a remaining pair has maximal death time, the algorithm selects the first later pair with a larger death time and removes it from the working list.The selected pair is compared with the current pair to determine whether a critical point is added or an intermediate pair is pushed back into the ordered set.
If the new birth time exceeds the current death time, the procedure adds a zero-valued critical point; otherwise, it reinserts the truncated pair (b′, d).The branch updates the current landscape list and continues processing the relevant death-time cases, including d′ = ∞.
After each landscape list is completed, the algorithm increments k and repeats until the working set is empty, then returns {Lk}.Each Lk is represented as a list of critical points (x, y).