Persistent Cohomology and Circular Coordinates

Vin de Silva, Dmitriy Morozov, Mikael Vejdemo-Johansson

TL;DR

This paper introduces a novel approach to nonlinear dimensionality reduction (NLDR) by incorporating "circular coordinates" (functions mapping data to a circle) alongside traditional real-valued coordinates. By leveraging persistent cohomology, the authors can automatically detect and extract these circular structures, enabling a more complete understanding of data with inherent cyclical or angular properties.

What Problem Does This Paper Address?

Standard NLDR algorithms like Isomap and LLE assume that data can be faithfully represented by real-valued coordinates. However, this assumption breaks down for data with intrinsic topological features, such as circles or tori, which require multiple real coordinates for a complete description. For instance, a simple circle, though one-dimensional, needs two real numbers to specify a point's position. This limitation hinders the accurate analysis of datasets exhibiting such structures. The paper aims to extend NLDR to handle these cases by introducing circle-valued coordinates.

Methods

The core of the paper's methodology lies in a five-step process:

  1. Simplicial Complex Representation: The input point cloud data is converted into a filtered simplicial complex. This allows the application of topological tools.
  2. Persistent Cohomology: Persistent cohomology is used to identify "significant" topological features (specifically, circular structures) that persist across a range of scales. This is done using coefficients in a finite field (Fp) for computational reasons, and then lifted to integer coefficients.
  3. Lifting to Integer Coefficients: The Fp-valued cocycles are lifted to integer-valued cocycles, which are necessary for constructing circle-valued functions.
  4. Harmonic Smoothing: The integer cocycle is smoothed into a "harmonic" real-valued cocycle. This process minimizes the total variation across the edges of the complex, leading to a "smoother" representation. This is achieved by solving a least-squares minimization problem.
  5. Integration: The harmonic cocycle is integrated to produce the final circle-valued coordinate function. This function maps data points to the circle (S¹), effectively capturing angular or cyclical information.

The paper also leverages the relationship between cohomology and continuous maps to a circle (H¹(X; Z) = [X, S¹]), which is a fundamental concept from algebraic topology.

Datasets

The paper evaluates its method on several synthetic datasets designed to represent specific topological structures:

  • Noisy Circle: A set of points sampled from a circle with added uniform random noise.
  • Trefoil Torus Knot: Points sampled from a trefoil knot on a torus.
  • Rotating Cube: A sequence of images of a rotating cube, treated as a dataset.
  • Pair of Circles: Datasets representing both conjoined and disjoint circles.
  • Torus: Points sampled from a torus.
  • Elliptic Curve: Points sampled from a complex projective curve defined by a cubic equation.
  • Double Torus (Genus-2 Surface): A more complex topological surface.

These datasets are not new benchmarks but are specifically chosen to demonstrate the method's ability to recover known topological structures and parameters.

Key Insights and Ideas

  • Beyond Real Coordinates: The most significant insight is the realization that real-valued coordinates are insufficient for data with inherent cyclical or angular properties. Expanding the NLDR toolkit to include circle-valued functions is crucial for a complete representation.
  • Persistent Cohomology as a Detector: Persistent cohomology is a powerful tool for automatically identifying these "circular structures" in data, without prior knowledge of their existence or location. The persistence diagram provides a visual representation of the stability of these features.
  • Harmonic Smoothing for Well-Behaved Functions: The harmonic smoothing step is key to obtaining meaningful and interpretable circular coordinates. It ensures that the resulting functions are as "smooth" as possible, minimizing spurious variations.
  • Topological Degree as a Measure of Correlation: The paper uses the concept of topological degree to quantify how well the inferred circular coordinates match known parameters. A degree of 1 indicates a faithful recovery of the underlying cyclical structure.

Key Results

The paper demonstrates that its method can successfully:

  • Recover Tautological Coordinates: For simple structures like a circle, the inferred coordinate closely reproduces the known angular parameter (e.g., Figure 1).
  • Detect Multiple Circular Structures: For datasets with multiple natural circular coordinates (like a torus), the method can infer multiple distinct functions, which are then analyzed for decorrelation (e.g., Figure 5).
  • Handle Noise and Complexity: The method shows robustness to noise and can extract meaningful coordinates from complex topological spaces like the trefoil knot, conjoined circles, and even a double torus.
  • Visualize Topological Features: Correlation scatter plots between inferred coordinates provide a visual diagnostic for understanding the relationships between different circular structures within the data.

While specific quantitative metrics like accuracy percentages are not the primary focus, the qualitative results, as shown in the figures, are compelling. For instance, the correlation plots for the torus (Figure 5) clearly show the decorrelation between the two inferred coordinates, which is characteristic of this manifold.

Limitations and Future Work

  • Computational Cost: While the paper mentions computation times, the construction of simplicial complexes and persistent cohomology can be computationally intensive for very large datasets.
  • Choice of Prime (p): The use of finite field coefficients (Fp) requires selecting a prime p. While the paper suggests that picking a prime that doesn't divide the torsion subgroup of H²(X; Z) is usually sufficient, this can add a layer of complexity.
  • "Snagging" Local Coordinates: The paper notes that low-persistence coordinates can "snag" around small gaps in the data, indicating they are more local and potentially less stable than global coordinates.
  • Higher-Dimensional Cohomology: The current work focuses on H¹ (which corresponds to circles). Extending the approach to higher-dimensional cohomology (which corresponds to spheres and other manifolds) is a natural next step.
  • Real-World Applications: While the paper uses synthetic data, the authors suggest that this enriched class of coordinate functions can lead to more precise NLDR analysis of a broader range of realistic data sets, implying future work in applying this to real-world problems.
  • Uncertainty Quantification: The paper doesn't deeply explore quantifying the uncertainty associated with the inferred coordinates.

Summary updated

Abstract

Nonlinear dimensionality reduction (NLDR) algorithms such as Isomap, LLE, and Laplacian Eigenmaps address the problem of representing high-dimensional nonlinear data in terms of low-dimensional coordinates which represent the intrinsic structure of the data. This paradigm incorporates the assumption that real-valued coordinates provide a rich enough class of functions to represent the data faithfully and efficiently. On the other hand, there are simple structures which challenge this assumption: the circle, for example, is one-dimensional, but its faithful representation requires two real coordinates. In this work, we present a strategy for constructing circle-valued functions on a statistical data set. We develop a machinery of persistent cohomology to identify candidates for significant circle-structures in the data, and we use harmonic smoothing and integration to obtain the circle-valued coordinate functions themselves. We suggest that this enriched class of coordinate functions permits a precise NLDR analysis of a broader range of realistic data sets.
BibTeX
@inproceedings{silva2011persistent,
  author = {Vin de Silva and Dmitriy Morozov and Mikael Vejdemo-Johansson},
  title = {{Persistent Cohomology and Circular Coordinates}},
  booktitle = {Discret. Comput. Geom},
  year = {2011},
  url = {https://openreview.net/forum?id=BCq77aryj},
}
Figure