際際滷

際際滷Share a Scribd company logo

Persistent homology

?
?
Kelly Davis
Kelly Davis

Persistent homology is a technique from topological data analysis that can be used to analyze the topology of a point cloud dataset. It constructs a sequence of simplicial complexes from the data and computes the homology groups of each complex to track how topological features in the data, such as connected components and loops, change with scale. This information can be represented visually using a barcode, which plots the lifetime of each topological feature as a line segment on a graph. Algorithms for computing persistent homology calculate the Betti numbers and persistence of topological features to construct these barcodes. Several software libraries such as PHAT, Dionysus, and Plex provide implementations of these algorithms.

1 of 14
Downloaded 20 times
Persistent Homology the basics Image:Jean-Marie Hullot (CC BY 3.0) kelly davis (founder forty.to)
problem:what¨s the topology of a point cloud? Image:Jean-Marie Hullot (CC BY 3.0)
solution: persistent homology Image:Jean-Marie Hullot (CC BY 2.0)
simplicial complex Image:Antoine Hubert (CC BY 2.0)
simplicial homology Image:Jean-Marie Hullot (CC BY 2.0)
simplicial homology i K L Image:Jean-Marie Hullot (CC BY 2.0)
simplicial ?ltrations iK Ki Image:Jean-Marie Hullot (CC BY 3.0)
birth, death, and taxes it is born at Ki if γ （ Hp . Furthermore, if γ is born at Ki then it dies entering Kj if it merges with an older class as we go from Kj?1 to Kj, that is, fi,j?1 p (γ) （ Hi?1,j?1 p but fi,j p (γ) （ Hi?1,j p ; see Figure VII.2. This is again the 0 0 0 0 H p i?1 H i H p j ?1 H pp j γ Figure VII.2: The class γ is born at Ki since it does not lie in the (shaded) image of Hi?1 p . Furthermore, γ dies entering Kj since this is the ?rst time its image merges into the image of Hi?1 p . Elder Rule. If γ is born at Ki and dies entering Kj then we call the di?erence in function value the persistence, pers(γ) = aj ? ai. Sometimes we prefer to ignore the actual function values and consider the di?erence in index, j ? i, which we call the index persistence of the class. If γ is born at Ki but neverImage:Jean-Marie Hullot (CC BY 3.0)
persistence it is born at Ki if γ （ Hp . Furthermore, if γ is born at Ki then it dies entering Kj if it merges with an older class as we go from Kj?1 to Kj, that is, fi,j?1 p (γ) （ Hi?1,j?1 p but fi,j p (γ) （ Hi?1,j p ; see Figure VII.2. This is again the 0 0 0 0 H p i?1 H i H p j ?1 H pp j γ Figure VII.2: The class γ is born at Ki since it does not lie in the (shaded) image of Hi?1 p . Furthermore, γ dies entering Kj since this is the ?rst time its image merges into the image of Hi?1 p . Elder Rule. If γ is born at Ki and dies entering Kj then we call the di?erence in function value the persistence, pers(γ) = aj ? ai. Sometimes we prefer to ignore the actual function values and consider the di?erence in index, j ? i, which we call the index persistence of the class. If γ is born at Ki but neverImage:Jean-Marie Hullot (CC BY 3.0)
so what! 2.3. Barcodes. The parameter intervals arising from the basis for H?(C; F) in Equation (2.3) inspire a visual snapshot of Hk(C; F) in the form of a barcode. A barcode is a graphical representation of Hk(C; F) as a collection of horizontal line segments in a plane whose horizontal axis corresponds to the parameter and whose vertical axis represents an (arbitrary) ordering of homology generators. Figure 4 gives an example of barcode representations of the homology of the sampling of points in an annulus from Figure 3 (illustrated in the case of a large number of parameter values i). H0 H1 H2 Figure 4. [bottom] An example of the barcodes for H?(R) in the example of Figure 3. [top] The rank of Hk(R i ) equals the number of intervals in the barcode for Hk(R) intersecting the (dashed) line = i. Theorem 2.3 yields the fundamental characterization of barcodes. Theorem 2.4 ([22]). The rank of the persistent homology group Hi★j k (C; F) is equal to the number of intervals in the barcode of Hk(C; F) spanning the parameter i Image:Padmanaba01 (CC BY 2.0)
calm before the algorithm Image:Pierre-Emmanuel BOITON (CC BY 2.0)
the algorithm: betti numbers Image:Pierre-Emmanuel BOITON (CC BY 2.0)
the algorithm: persistence Image:Pierre-Emmanuel BOITON (CC BY 2.0)
implementations: phat - c++ with c++ api dionysus - c++ with python api plex - java with java api Image:Jean-Marie Hullot (CC BY 3.0) Persistent Homology the basics kelly davis (founder forty.to)

More Related Content

Persistent homology

  • 1. Persistent Homology the basics Image:Jean-Marie Hullot (CC BY 3.0) kelly davis (founder forty.to)
  • 2. problem:what¨s the topology of a point cloud? Image:Jean-Marie Hullot (CC BY 3.0)
  • 8. birth, death, and taxes it is born at Ki if γ （ Hp . Furthermore, if γ is born at Ki then it dies entering Kj if it merges with an older class as we go from Kj?1 to Kj, that is, fi,j?1 p (γ) （ Hi?1,j?1 p but fi,j p (γ) （ Hi?1,j p ; see Figure VII.2. This is again the 0 0 0 0 H p i?1 H i H p j ?1 H pp j γ Figure VII.2: The class γ is born at Ki since it does not lie in the (shaded) image of Hi?1 p . Furthermore, γ dies entering Kj since this is the ?rst time its image merges into the image of Hi?1 p . Elder Rule. If γ is born at Ki and dies entering Kj then we call the di?erence in function value the persistence, pers(γ) = aj ? ai. Sometimes we prefer to ignore the actual function values and consider the di?erence in index, j ? i, which we call the index persistence of the class. If γ is born at Ki but neverImage:Jean-Marie Hullot (CC BY 3.0)
  • 9. persistence it is born at Ki if γ （ Hp . Furthermore, if γ is born at Ki then it dies entering Kj if it merges with an older class as we go from Kj?1 to Kj, that is, fi,j?1 p (γ) （ Hi?1,j?1 p but fi,j p (γ) （ Hi?1,j p ; see Figure VII.2. This is again the 0 0 0 0 H p i?1 H i H p j ?1 H pp j γ Figure VII.2: The class γ is born at Ki since it does not lie in the (shaded) image of Hi?1 p . Furthermore, γ dies entering Kj since this is the ?rst time its image merges into the image of Hi?1 p . Elder Rule. If γ is born at Ki and dies entering Kj then we call the di?erence in function value the persistence, pers(γ) = aj ? ai. Sometimes we prefer to ignore the actual function values and consider the di?erence in index, j ? i, which we call the index persistence of the class. If γ is born at Ki but neverImage:Jean-Marie Hullot (CC BY 3.0)
  • 10. so what! 2.3. Barcodes. The parameter intervals arising from the basis for H?(C; F) in Equation (2.3) inspire a visual snapshot of Hk(C; F) in the form of a barcode. A barcode is a graphical representation of Hk(C; F) as a collection of horizontal line segments in a plane whose horizontal axis corresponds to the parameter and whose vertical axis represents an (arbitrary) ordering of homology generators. Figure 4 gives an example of barcode representations of the homology of the sampling of points in an annulus from Figure 3 (illustrated in the case of a large number of parameter values i). H0 H1 H2 Figure 4. [bottom] An example of the barcodes for H?(R) in the example of Figure 3. [top] The rank of Hk(R i ) equals the number of intervals in the barcode for Hk(R) intersecting the (dashed) line = i. Theorem 2.3 yields the fundamental characterization of barcodes. Theorem 2.4 ([22]). The rank of the persistent homology group Hi★j k (C; F) is equal to the number of intervals in the barcode of Hk(C; F) spanning the parameter i Image:Padmanaba01 (CC BY 2.0)
  • 11. calm before the algorithm Image:Pierre-Emmanuel BOITON (CC BY 2.0)
  • 12. the algorithm: betti numbers Image:Pierre-Emmanuel BOITON (CC BY 2.0)
  • 14. implementations: phat - c++ with c++ api dionysus - c++ with python api plex - java with java api Image:Jean-Marie Hullot (CC BY 3.0) Persistent Homology the basics kelly davis (founder forty.to)