Introduction to Persistent Homology (Cech and Vietoris-Rips complex)

Motivation
Data is commonly represented as an unordered sequence of points in the Euclidean space \mathbb{R}^n. The global `shape’ of the data may provide important information about the underlying phenomena of the data.

For data points in \mathbb{R}^2, determining the global structure is not difficult, but for data in higher dimensions, a planar projection can be hard to decipher.
From point cloud data to simplicial complexes
To convert a collection of points \{x_\alpha\} in a metric space into a global object, one can use the points as the vertices of a graph whose edges are determined by proximity (vertices within some chosen distance \epsilon). Then, one completes the graph to a simplicial complex. Two of the most natural methods for doing so are as follows:

Given a set of points \{x_\alpha\} in Euclidean space \mathbb{R}^n, the Cech complex (also known as the nerve), \mathcal{C}_\epsilon, is the abstract simplicial complex where a set of k+1 vertices spans a k-simplex whenever the k+1 corresponding closed \epsilon/2-ball neighborhoods have nonempty intersection.

Given a set of points \{x_\alpha\} in Euclidean space \mathbb{R}^n, the Vietoris-Rips complex, \mathcal{R}_\epsilon, is the abstract simplicial complex where a set S of k+1 vertices spans a k-simplex whenever the distance between any pair of points in S is at most \epsilon.

fig2

Top left: A fixed set of points. Top right: Closed balls of radius \epsilon/2 centered at the points. Bottom left: Cech complex has the homotopy type of the \epsilon/2 cover (S^1\vee S^1\vee S^1) Bottom right: Vietoris-Rips complex has a different homotopy type (S^1\vee S^2). Image from R. Ghrist, 2008, Barcodes: The Persistent Topology of Data.

Advertisements

About mathtuition88

http://mathtuition88.com
This entry was posted in math and tagged . Bookmark the permalink.

2 Responses to Introduction to Persistent Homology (Cech and Vietoris-Rips complex)

  1. tomcircle says:

    You can make the math symbols bigger than the text font for easy reading. eg. {\lambda }
    “&s=3” added after the last } tells latex to make the symbol lambda bigger at size 3 (which is slightly bigger than the text font, so it stands out).

    Like

  2. tomcircle says:

    Sorry, latex should be:
    {\lambda}“.
    For color, you can append behind “&fg=aa0000 ” (brown)

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s