Topology
Witness Complexes and Multi-Parameter Persistence
Цели урока
- Understand witness complex construction and the role of landmarks/witnesses
- Master maxmin selection for quality data coverage
- Grasp what a 2-parameter persistence module is
- Learn the Carlsson-Zomorodian theorem on absence of a complete invariant
- Study RIVET and multi-parameter persistence applications
Предварительные знания
- Vietoris-Rips complex and its combinatorial complexity
- Persistent homology and barcodes
- Linear algebra basics over a field
- Notion of filtration of a topological space
Vietoris-Rips on 10000 points - 166 billion triangles. Witness complex - 100000. Million-fold compression with no topology loss.
- **Astronomy**: TDA on Sloan Digital Sky Survey catalogs with millions of galaxies via witness complexes
- **Single-cell genomics**: topological analysis of scRNA-seq data with millions of cells using landmarks as representative cells
- **Medical imaging**: organ segmentation via witness TDA on voxel clouds
- **Social networks**: bifiltration by frequency and recency for dynamic graphs
Witness complexes and multi-parameter
Witness complexes were introduced by de Silva and Carlsson in 2004 specifically to enable TDA on large point clouds. Multi-parameter persistence was formalized by Carlsson and Zomorodian in 2009 - in the same paper they proved absence of a complete discrete invariant (unlike the 1D barcode). The RIVET software for visualizing 2-parameter persistence was released by Lesnick and Wright in 2015. The field of multi-parameter TDA remains one of the most active research frontiers - NeurIPS workshops on TDA happen yearly.
Witness Complex Definition
A point cloud of 10000 points theoretically generates C(10000, 3) = 166 billion triangles in the Vietoris-Rips complex. No computer on the planet can store that in full. Witness complexes solve this problem through radical simplification: pick 100 landmark points, and the remaining 9900 points act as witnesses confirming the existence of simplices between landmarks. The topology gets reconstructed from a tiny subset.
The de Silva-Carlsson idea (2004): landmarks form the vertices, witnesses are nearby data points that support the existence of a simplex. The resulting complex is orders of magnitude smaller than Rips but captures the same topology.
Size comparison
How many simplices remain after witness construction
Cloud X of 10000 points, selected L = 100 landmarks. Vietoris-Rips: up to 166 billion 2-simplices. Witness complex: at most C(100, 3) = 161700 simplices. Compression by a factor of a million. Yet first few Betti numbers and large persistent features survive with bounded error.
Strong witness complex requires the witness to be strictly closer to sigma than to any other landmark - gives smaller, more accurate complex. Weak version with epsilon tolerance is more noise-robust.
Why is a witness complex needed?
Witness complex radically reduces simplex count while preserving topological features through evidence from outside points.
Landmark Selection and Complexity
Witness complex quality directly depends on landmark choice. Random sampling works fast but yields uneven coverage. Maxmin selection - the industry standard: first landmark is random, then each step picks the point maximally distant from already chosen landmarks. This is a greedy approximation of an epsilon-net.
Maxmin gives more uniform coverage than random sampling and provides theoretical guarantees: for any data point, there exists a landmark within the epsilon-net radius.
Maxmin algorithm
Step-by-step landmark set selection
Given cloud X = 10000 points, target |L| = 100. Step 1: random l_1. Step 2: for each point x compute d(x, l_1), pick argmax - that is l_2. Step k: for each x compute min distance to already chosen landmarks, pick the point with maximum such distance. Complexity O(|L| * |X|) = O(100 * 10000) = one million operations. Compare with Rips: 166 billion.
For good landmark sets (maxmin or epsilon-net), witness complex persistence diagrams approximate full Rips diagrams within bounded bottleneck error.
Random sampling can miss entire data regions. If the cloud contains a rare but topologically significant cluster, random landmarks may miss it. Maxmin protects against this.
ML applications: scalable TDA on million-scale datasets - astronomical catalogs from Sloan Digital Sky Survey, single-cell genomics with millions of cells, medical image segmentation where each voxel is a cloud point. Witness complexes make TDA practically applicable where Rips is impossible.
What is the idea of maxmin landmark selection?
Maxmin minimizes the maximum distance to the nearest landmark - a greedy approximation of an epsilon-net.
Multi-Parameter Persistence
A single filtration parameter is often insufficient to separate signal from noise. What if distance AND density must be considered simultaneously? A point can be close to others but in a low-density region - possibly noise. Or the reverse: far away but in a dense cluster - meaningful structure. Multi-parameter persistence answers this question.
Carlsson and Zomorodian (2009) formalized multi-parameter persistence: a persistence module over R^n instead of R^1. For two parameters the result is a functor from R^2 to Vect - a 2D persistence module.
Carlsson and Zomorodian proved: unlike 1D persistence (where barcode is a complete invariant), multi-parameter persistence has NO simple complete discrete invariant. This is a fundamental obstruction, not an algorithmic shortcoming.
Density-Rips bifiltration
Two-parameter filtration by distance and density
Parameter r - Rips radius, parameter k - density threshold (e.g., k-nearest neighbor distance). A simplex sigma enters the complex at level (r, k) if all vertices of sigma have density at least k AND pairwise distances at most r. The result is a 2D lattice of complexes and a 2D persistence module.
If data contains noise of different nature (outliers AND density noise), a single parameter cannot separate the signal. Multi-parameter allows filtering along both dimensions simultaneously.
Why is multi-parameter persistence harder than 1D?
Carlsson and Zomorodian proved impossibility of a complete discrete invariant - a mathematical obstruction, not a computational one.
Applications and State of the Field
Multi-parameter persistence in practice - sublevel set bifiltrations for signals with varying noise level. Vineyard - tracking persistent features as parameters change over time. Persistence vineyard visualizes how barcode evolves along a curve in parameter space. RIVET software (Lesnick and Wright, 2015) is the standard tool for visualizing 2-parameter persistence.
RIVET computes slice-and-project: fix a line in parameter space and compute 1D persistence along it. Interactive visualization allows moving the line and watching barcode change in real time.
Social network with time
Bifiltration by interaction frequency and recency
Social network graph: vertices are users, edges are interactions. Parameter f - frequency (message count), parameter t - recency (time since last message). The result is a 2-parameter filtration. Loops in H_1 correspond to cyclic communication patterns. Multi-parameter separates active cycles (high f, low t) from decaying ones (low f, high t).
Active research: computable invariants for multi-parameter persistence (Hilbert function, signed barcodes, decomposition theorems for interval modules). Connection with quiver representation theory. This is one of the most active areas of TDA today.
ML applications: learning the optimal filtration parameter pair from data - instead of manual radius and density threshold choice, gradient-optimize over downstream loss; multi-parameter TDA for heterogeneous datasets where different features have different noise scales; topological features for heterogeneous time series with different update frequencies.
Multi-parameter persistence is substantially more expensive than 1D - not only due to lack of barcode invariant, but also due to growth of complex lattice size. In practice 2-parameter cases are used; 3+ parameters is a research frontier.
What does RIVET do with 2-parameter persistence?
RIVET uses slice-and-project: a line is interactively selected, and ordinary 1D persistence is computed along it.
Where this leads
Witness complexes make TDA a practical tool for million-scale datasets. Multi-parameter persistence opens a new mathematical dimension - topological quiver representation theory.
- Sliding window TDA — Related topic
- TDA in neural networks — Related topic
- Persistent homology — Related topic
- Vietoris-Rips — Related topic
Key ideas
- Witness complex replaces Rips for large |X|: landmarks as vertices, witnesses confirm simplices
- Maxmin selection yields even data coverage and theoretical guarantees
- Persistence witness approximates Rips persistence with bounded error
- Multi-parameter persistence is a functor R^n to Vect, no complete discrete invariant (Carlsson-Zomorodian)
- Rank invariant and Hilbert function are partial invariants for 2D modules
- RIVET computes 1D slices of a 2-parameter module interactively
- Density-Rips bifiltration separates density noise from distance noise
- Active research front: signed barcodes, interval decomposition, learning filtrations
Вопросы для размышления
- Which data properties make maxmin selection preferable to random sampling?
- Why is the absence of a complete invariant for multi-parameter persistence a mathematical, not computational, problem?
- What stability guarantees do witness complexes provide compared to full Rips?
- In which ML tasks does 2-parameter filtration give an advantage over 1D?
- How can landmark selection be used as a form of active learning?