PaperlayerView exact revision on arXiv

Source-linked AI summary

Persistent Cohomology and Circular Coordinates

Vin de Silva, Mikael Vejdemo-Johansson

arXiv:0905.4887v1math.ATcs.CG

TL;DR

Real-valued NLDR coordinates can inadequately represent data manifolds with nontrivial topology, such as circles. The paper constructs circle-valued coordinates by detecting persistent cohomology classes, harmonically smoothing them, and integrating them, with experiments recovering circular structure in noisy circles, paired circles, and a torus.

  • Problem

    NLDR methods assume real-valued coordinates suffice, but structures such as circles can require more real coordinates than their intrinsic dimension.

  • Method

    The method uses persistent cohomology to identify significant circle-structures, then applies harmonic smoothing and integration to obtain circle-valued coordinate functions.

  • Results

    The experiments recover natural circle-valued functions in noisy and paired circles and recover torus coordinates essentially perfectly.

  • Takeaways & Limitations

    Circle-valued coordinates enrich NLDR representations for data whose topology is not adequately captured by real-valued coordinates.

  • Takeaways & Limitations

    The initial integer-cocycle construction maps all vertices to one point, with circle-parameter variation occurring in cell interiors and producing an unsmooth representation.

Abstract

from arXiv · show

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.

1. INTRODUCTION

The paper challenges real-valued NLDR coordinates by introducing circle-valued coordinates for data with nontrivial topology. Its procedure uses persistent cohomology, harmonic smoothing, and integration to construct these coordinates.

  • Motivation: NLDR seeks low-dimensional embeddings that faithfully preserve the intrinsic structure of high-dimensional data.The embedding may provide coordinates on an underlying manifold when its structure is completely and non-redundantly parametrized.
  • Motivation: Real-valued coordinate methods implicitly assume that the data manifold is well-described by finitely many real-valued coordinate functions.Some correctness results further assume that the manifold has the topology of a convex domain in Euclidean space.
  • Motivation: The circle exposes this limitation because it is one-dimensional but requires two real coordinates for a faithful embedding.The paper also identifies the annulus, torus, figure eight, and 2-sphere as structures challenging Euclidean coordinates in their natural dimensions.
  • Contribution: The paper proposes enlarging the coordinate class to include circle-valued functions, which naturally represent angular and phase variables.Combinations of real and circular coordinates can describe spaces such as the annulus and torus.
  • Method: The construction represents data as a filtered simplicial complex, identifies significant cohomology classes with persistent cohomology, lifts them to integer coefficients, smooths them harmonically, and integrates them.The method is grounded in the correspondence between homotopy classes of maps to S1 and first cohomology with integer coefficients.

2. ALGORITHM DETAILS

The algorithm converts point-cloud data into filtered simplicial complexes, uses persistent cohomology to select stable cocycles, lifts them to integer classes, smooths them harmonically, and integrates them into circle-valued functions.

  • 2.5 Harmonic smoothing: An integer cocycle is replaced by a cohomologous real cocycle with small edge values, making the resulting circle-valued function more apparent on vertices.The smoothed cocycle is constructed in the form ¯α = α + d0f, with θ defined on vertices by f mod Z.
  • 2.2 Point-cloud data to simplicial complex: Point-cloud data are represented as finite simplicial or filtered simplicial complexes, commonly using Vietoris–Rips or smaller witness complexes.The complexes are truncated to their 2-skeleton because the method studies H1.
  • 2.3 Persistent cohomology: Persistent cohomology identifies cocycles associated with long filtration intervals, which are treated as stable topological information.A selected parameter δ within a persistent interval determines the complex and cocycle used downstream.
  • 2.3 Persistent cohomology: Persistence calculations use a finite field because interval decompositions can fail over the integers, after which the selected class is converted to integer coefficients.The procedure maintains live cocycles as simplices enter the filtration and associates surviving cocycles with semi-infinite intervals.
  • 2.3 Persistent cohomology: Persistent cohomology is used to obtain explicit cocycles rather than only the cycles returned by classical persistent homology algorithms.The persistence diagrams for homology and cohomology agree over fields, but the desired computational objects differ.

3. EXPERIMENTS

The experiments used jPlex for simplicial-complex and persistent-cocycle computations, MATLAB for scripting and numerical analysis, and LSQR for harmonic smoothing.

  • 3. EXPERIMENTS: Experiments used a development version of jPlex to compute explicit persistent cohomology cocycles and MATLAB for scripting and numerical analysis.Timings were measured with MATLAB’s built-in tic and toc commands.
  • 3. EXPERIMENTS: Paige and Saunders’ LSQR implementation was used to solve the least-squares problem in the harmonic smoothing step.

3.2 General procedure

The experiments evaluate circular coordinates on synthetic data with known topology across varied ambient spaces, using persistence diagrams, coordinate comparisons, color plots, and histograms.

  • 3.2 General procedure: The test suite spans synthetic data from a circle to a genus-2 surface, plus examples embedded in CP 2 and R120000.Most examples are embedded in R2 or R3.
  • 3.2 General procedure: Each experiment builds a Rips or witness complex from all vertices or well-distributed landmarks, generally targeting around 105 simplices.Landmarks are selected by iterative furthest-point sampling.
  • 3.2 General procedure: Persistence diagrams mark the chosen δ and identify the persistent cocycles available at that parameter, each of which yields a circular coordinate.
  • 3.2 General procedure: Correlation scatter plots compare pairs of inferred circular coordinates or compare inferred coordinates with known parameters in the unit-square representation of S1 × S1.
  • 3.2 General procedure: For data in R2 or R3, coordinate values are visualized by assigning each point a color on the standard hue-circle.The authors note that this visualization is less effective in grayscale reproductions.
  • 3.2 General procedure: Histograms plot coordinate values against frequency and can provide distributional information when other information is unavailable.
  • 3.2 General procedure: When topology is unknown, inferred-coordinate scatter plots, histograms, and persistence diagrams are used to distinguish structures without known parameters.

3.3 Noisy circle

On noisy samples of a circle, the method can recover a circle-valued coordinate, but the selected cocycle's persistence affects whether the result is global or locally distorted.

  • Noisy circle: 400 noisy points were sampled from the unit circle, and a Rips complex with maximal radius 0.5 contained 23475 simplices.The cohomology computation finished in 237 seconds.
  • Noisy circle: At parameter 0.4, the method produced a single coordinate function closely reproducing the tautological angle function.
  • Noisy circle: At parameter 0.14, selecting a low-persistence cocycle produced a parametrization that snagged around a small gap in the data.
  • Noisy circle: The high-persistence global coordinate had topological degree 1 correlation with the angle function and uniformly distributed variation.
  • Noisy circle: The low-persistence local coordinate instead had a spiky distribution.

3.4 Trefoil torus knot

On a noisy sample of a (2, 3) torus knot, the inferred circle-valued coordinate strongly correlates with the known parameter with topological degree 1.

  • Trefoil torus knot: 400 jittered points were sampled from a (2, 3) torus knot, and a Rips complex up to radius 1.0 contained 36936 simplices.Persistent cohomology was computed in 70 seconds.
  • Trefoil torus knot: The inferred coordinate correlates strongly with the known parameter with topological degree 1.The histogram shows three bulges.

3.5 Rotating cube

For rendered images of a cube rotating around one axis, the method constructs a circular coordinate whose values extend from landmark points to the full image family and track the known sequence with degree 1.

  • Rotating cube: A witness complex with 50 landmark points was built from 657 rendered images of a colorful cube rotating around one axis.Each image was represented as a vector in R200·200·3.
  • Rotating cube: Linear interpolation between the landmark values supplied coordinates for all points in the image family.
  • Rotating cube: The inferred coordinate correlated with the original image sequence with topological degree 1.Its frequency distribution was comparatively smooth, without large histogram spikes.

3.6 Pair of circles

For conjoined and disjoint noisy circles, the method detects the two most natural circle-valued functions; the conjoined case shows interference near the meeting point.

  • Pair of circles: The conjoined-circle example used 400 jittered points and a Rips complex containing 76763 simplices.The cohomology computation took 378 seconds.
  • Pair of circles: The disjoint-circle example used 400 disturbed points and a Rips complex containing 45809 simplices.The cohomology computation finished in about 117 seconds.
  • Pair of circles: In both examples, the method detected the two most natural circle-valued functions.
  • Pair of circles: Interference between the two circles appeared near their meeting point in the conjoined case.

3.7 Torus

The torus experiments recover two circle-valued coordinates corresponding to the torus’s two intrinsic directions. Their inferred-versus-inferred scatter plot is broadly uniform, indicating decorrelation, unlike the circle examples.

  • The experiment samples 400 jittered points from a torus parametrized by the unit square and computes a Rips complex with maximal radius 3.The complex contains 61522 simplices, and the corresponding cohomology computation takes 209 seconds.
  • The figure panels organize the torus analysis around persistence diagrams, coordinate comparisons, and inferred-coordinate visualizations.The supplied figure captions identify these panels across the noisy circle, torus knot, rotating cube, and paired-circle examples.
  • The two inferred coordinates recover the original coordinates essentially perfectly, with topological degrees −1 for the meridional coordinate and 1 for the longitudinal coordinate.
  • The inferred-versus-inferred scatter plot is fairly uniformly distributed across the coordinate square, showing that the two coordinates are decorrelated.The passage contrasts this distribution with the scatter plots for conjoined or disjoint circles.

3.8 Elliptic curve

The elliptic-curve experiment applies the circle-coordinate framework to a complex projective curve and identifies two dominant coclasses. Their correlation plot displays the decorrelation characteristic of a torus.

  • The data are sampled from a complex projective curve defined by the homogeneous cubic equation x2y + y2z + z2x = 0.The curve is represented using 400 points sampled on S5 ⊂ C3 subject to the cubic equation.
  • Two dominant coclasses survive beyond radius 0.15, and the parametrizations are computed at the 0.15 mark.
  • The resulting correlation plot clearly exhibits the decorrelation characteristic of the torus.

3.9 Double torus

The double-torus experiment identifies four significant cocycles and examines the relationships among the resulting circle-valued coordinates. Some coordinate pairs are coupled on the same subtorus, while uncoupled pairs resemble circle configurations.

  • The genus-2 surface dataset contains 3120 points, from which 400 landmarks define a witness complex with maximal radius 0.6.The landmark set has covering radius rmax = 0.9982, the complex contains 70605 simplices, and computation takes 748 seconds.
  • Four of the most significant cocycles are identified in the double-torus experiment.The figure materials describe the persistence diagram as detecting four cocycles and show four inferred coordinates.
  • Coordinates 1 and 4 are coupled because they are supported over the same subtorus, producing decorrelation except for a mass at one point.The mass corresponds to the other subtorus, where coordinates 1 and 4 are essentially constant; the same pattern applies to coordinates 2 and 3.
  • The uncoupled coordinate pairs (1,2), (1,3), (2,4), and (3,4) produce scatter plots resembling two conjoined or disjoint circles.
  • The figure compares inferred coordinates through persistence diagrams, coordinate displays, and correlation scatter plots.The supplied figure materials also label comparisons between original and inferred coordinates.
Loading 0905.4887v1…