Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
user_guide:tutorials:persistent_homology [2019/01/29 21:46] – external edit 127.0.0.1 | user_guide:tutorials:persistent_homology [2019/02/04 22:55] (current) – external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Persistent Homology Tutorial ===== | + | {{page>.:latest: |
- | Persistent homology is a construct from algebraic topology that formalizes the effect that changing a topological space in a certain way has on its homology. It attempts to overcome the lack of robustness homology shows: changing the space of interest just a little can result in a drastic change in homology. The approach to this is to consider the homology of the space at different " | + | |
- | [[http:// | ||
- | |||
- | To use the function, one has to switch to the '' | ||
- | |||
- | < | ||
- | polytope > application ' | ||
- | </ | ||
- | |||
- | ===== Filtrations ===== | ||
- | |||
- | The objects of study are filtrations of chain complexes with finitely many frames. The data structure is templated by the type of matrix used for the description of the boundary maps. | ||
- | |||
- | ====From Hasse diagrams==== | ||
- | A filtration can be initialized by passing the Hasse diagram of the last frame of the filtration and an array containing the degree of each cell, indexed in the same order as the node indexing in the Hasse diagram (without the empty set and the dummy node with index 0, thus shifted by one). Consider this small three-frame example filtration: | ||
- | |||
- | {{ user_guide: | ||
- | |||
- | You can construct it in '' | ||
- | < | ||
- | topaz > $S = new SimplicialComplex(FACETS=> | ||
- | |||
- | topaz > $HD = $S-> | ||
- | topaz > print rows_numbered($HD-> | ||
- | 0:-1 | ||
- | 1:0 1 | ||
- | 2:0 2 | ||
- | 3:1 2 | ||
- | 4:3 | ||
- | 5:0 | ||
- | 6:1 | ||
- | 7:2 | ||
- | 8: | ||
- | topaz > $a = new Array< | ||
- | |||
- | topaz > $F = new Filtration< | ||
- | </ | ||
- | |||
- | You can print the boundary matrix for each frame and dimension: | ||
- | < | ||
- | topaz > print $F-> | ||
- | 1 -1 0 | ||
- | 0 1 -1 | ||
- | </ | ||
- | To find out which rows correspond to which cells, you can print the cells of the filtration. They will be output as an array of 3-tuples, each representing one cell with degree, dimension and boundary matrix index. | ||
- | < | ||
- | topaz > print $F-> | ||
- | (0,0,1) (0,0,2) (1,0,3) (1,1,0) (1,1,2) (2,0,0) (2,1,1) | ||
- | </ | ||
- | |||
- | ====From boundary matrices==== | ||
- | It is also possible to construct a filtration by passing such an array of cells, together with an array of matrices to be used as boundary matrices. To construct the same filtration as above: | ||
- | < | ||
- | topaz > $C = new Array< | ||
- | topaz > $C->[0] = new Cell(0, | ||
- | $C->[1] = new Cell(0, | ||
- | $C->[2] = new Cell(1, | ||
- | $C->[3] = new Cell(1, | ||
- | $C->[4] = new Cell(1, | ||
- | $C->[5] = new Cell(2, | ||
- | $C->[6] = new Cell(2, | ||
- | | ||
- | topaz > $bd = new Array< | ||
- | topaz > $bd->[0] = new SparseMatrix< | ||
- | $bd->[1] = new SparseMatrix< | ||
- | $bd->[2] = new SparseMatrix< | ||
- | |||
- | topaz > $F = new Filtration< | ||
- | </ | ||
- | |||
- | |||
- | |||
- | ====Vietoris-Rips filtration==== | ||
- | It is also possible to compute the Vietoris-Rips-filtration of a point set given a metric. The input consists of the distance matrix of the point set (that is, the matrix whose i,j-entry is the distance between points i and j), an array containing the filtration degrees of the points, the increase in ball size per frame, and an upper bound to the dimension (so one can compute lower-dimensional skeletons and save space). The following computes the four-skeleton of the VR-filtration of six random points in 5-space using the euclidean metric: | ||
- | |||
- | < | ||
- | topaz > $S = polytope:: | ||
- | topaz > $P = $S-> | ||
- | |||
- | topaz > sub dist($){ | ||
- | topaz(2) > my $v = $_[0] - $_[1]; | ||
- | topaz(3) > return sqrt(new Float($v*$v)); | ||
- | |||
- | topaz > $D = distance_matrix($P, | ||
- | |||
- | topaz > $a = new Array< | ||
- | |||
- | topaz > $F = vietoris_rips_filtration< | ||
- | </ | ||
- | If you want to visualize specific frames of the filtration, use the '' | ||
- | < | ||
- | vietoris_rips_complex($D, | ||
- | </ | ||
- | |||
- | |||
- | {{ user_guide: | ||
- | ===== Computing Persistence ===== | ||
- | There are two different functions, one to compute persistent homology for coefficients from arbitrary euclidean domains, and another for computing persistence barcodes for field coefficients. Both are templated by the boundary matrix type. The following examples compute both for this filtration of the 5-simplex, whose 3rd frame is the real projective plane: | ||
- | |||
- | ==== Coefficients from arbitrary euclidean domains ==== | ||
- | |||
- | The function for coefficients from arbitrary euclidean domains takes as parameters a filtration object matching the matrix type and indices '' | ||
- | |||
- | The following code loads a filtration object with Integer coefficients containing the example that was previously saved to disk, which you can download {{ user_guide: | ||
- | |||
- | < | ||
- | topaz > $F = load_data(" | ||
- | topaz > print persistent_homology< | ||
- | <> | ||
- | <(2, <(15) (0 -1) (1 1) (5 -1)> | ||
- | </ | ||
- | |||
- | ==== Field coefficients and barcodes ==== | ||
- | |||
- | {{ user_guide: | ||
- | |||
- | < | ||
- | topaz > $F2 = load_data(" | ||
- | topaz > print persistent_homology< | ||
- | {(0 2) (0 -1)} | ||
- | {(2 3) (2 3) (2 3) (1 3) (2 3) (0 3)} | ||
- | {} | ||
- | {} | ||
- | {} | ||
- | {} | ||
- | {} | ||
- | </ | ||
- | |||
- | The output corresponds to the barcode on the right. |