VI.2 Stability 135VI.2 StabilityPersistent homology is stable, that is, small perturbations of the input onlycause small perturbations of the output. This property has a number of non-trivial consequences, some of which will be discussed in Section VI.3. In thissection, we study how changing the filtration affects the corresponding reducedmatrix and use the gained insights to prove the stability of persistence diagrams.Matrix reduction revisited. We recall the notion of a reduced 0-1 matrixin which each non-zero column has its lowest one in a unique row. Starting withthe boundary matrix, D, whose rows and columns correspond to the simplicesin the order they enter the filtration, we use the algorithm of the previoussection to reduce the matrix by adding columns from the left. The resultingreduced matrix can therefore be written as R = DV , where V is an invertible,upper triangular 0-1 matrix. Let U be the right inverse of V and note that it isagain invertible and upper triangular. By multiplication from the right we getRU = DV U = D which we call an RU-decomposition of the boundary matrix.It is characterized by R being reduced and U being upper triangular. Notsurprisingly, the RU-decomposition is not unique. For example, we could useadditional column operations to remove as many ones from the matrix as wecan. On the other hand, the pairing implied by the lowest ones in the columnsis unique. To prepare the proof of this claim we write Ri,jfor the lower leftsubmatrix obtained by deleting the first i − 1 rows and the last n − j columnsfrom R, as illustrated in Figure VI.6. Any linear combination of non-zeroi +1j j−1++−−iFigure VI.6: The shaded submatrix Ri,jof R. We have i = low(j) iff the indicatedinclusion-exclusion formula of ranks of lower left submatrices gives 1.columns in Ri,jhas its lowest one in the same row as the lowest of the lowestones of the involved columns. The combination is non-zero implying that thecombined columns are linearly independent. In other words, the rank of Ri,j136 VI Persistenceis equal to its number of non-zero columns. We consider the same collection ofsubmatrices of the boundary matrix, and for each index pair (i, j) we definerD(i, j) = rank Di,j− rank Di+1,j+ rank Di+1,j−1− rank Di,j−1.We prove shortly that the pairing function can be expressed in terms of rDandis therefore independent of the particular reduced matrix we derive from D.Pairing Lemma. Letting D = RU be an RU-decomposition, we have i =low(j) iff rD(i, j) = 1. In particular, the pairing defined by the lowest ones inthe reduced matrix does not depend on R.Proof. We have rD= rRsince adding columns from the left maintains therank of every lower left submatrix. It therefore suffices to prove that i = low(j)iff rR(i, j) = 1. First assume i = low(j). We recall that the rank of Ri,jisequal to its number of non-zero columns. The last column is non-zero, sorank Ri,j− rank Ri,j−1= 1. Deleting the top row makes the last column zero,so rank Ri+1,j− rank Ri+1,j−1= 0, as required. Second assume i 6= low(j).If low(j) < i then the last column is zero, so rank Ri,j− rank Ri,j−1= 0and rank Ri+1,j− rank Ri+1,j−1= 0. If low(j) > i then the last column isnon-zero even after deleting the first row, so rank Ri,j− rank Ri,j−1= 1 andrank Ri+1,j− rank Ri+1,j−1= 1. In both cases the claim follows.Transpositions. Suppose we change the order of just two simplices, trans-posing the two corresponding rows and columns in the boundary matrix. Thenew boundary matrix is P DP , where P is the permutation matrix that swapsi with i + 1. Multiplication with P from the left swaps the two rows andmultiplication from the right swaps the two columns. Letting D = RU be anRU-decomposition we now get P RU P = (P RP )(P U P ), but this is not neces-sarily an RU-decomposition of P DP . It can fail to be one because P RP is notreduced or because P U P is not upper triangular. However, in each case thiscan be remedied with relatively little effort. Recall that a simplex is positive ifits addition to the complex increases the Betti number of the same dimension.It corresponds to a zero column in R. A simplex is negative if its addition tothe complex decreases the Betti number of one lower dimension. It correspondsto a non-zero column with a lowest one in R.Case 1. The simplices in positions i and i + 1 are both positive. Then columni is zero so we may set U[i, i + 1] = 0. It follows that P U P is uppertriangular and we only need to worry about P RP . If it fails to be reduced,as in Figure VI.7 on the left, we add column k to column l and thus obtainan RU-decomposition.VI.2 Stability 137i+1i+1PUPik lPRPii+1i+1PRPiPUPi1111 1111Figure VI.7: Left: after swapping the two positive simplices at positions i and i + 1the matrix on the left may no longer be reduced. Right: after swapping the twonegative simplices at positions i and i + 1 the matrix on the right may no longer beupper triangular.Case 2. The simplices in positions i and i + 1 are both negative. The corre-sponding rows do not contain any lowest ones so we only need to worryabout P U P . It fails to be upper triangular iff U[i, i + 1] = 1, as in FigureVI.7 on the right. We fix the trouble by adding row i +1 to row i in U andadding column i to column i + 1 in R. This does not affect the productof the two matrices. If low(i) < low(i + 1) before this operation then thelowest ones remain unique and we have an RU-decomposition after thetransposition. On the other hand, if low(i) > low(i + 1) then we need tomake the lowest ones unique again, which we do by adding column i+1 tocolumn i. After the transposition this is adding column i to column i + 1and we get again an RU-decomposition.Case 3. The simplex at position i is negative and that at position i + 1 ispositive. Since row i + 1 has no lowest one we only need to worry aboutP U P . The only troublesome case is U [i, i + 1] = 1 and we can remedy thesituation the same way as in Case 2.Case 4. The simplex at position i is positive and that at position i + 1 isnegative. Because row i has no lowest one P RP is reduced. Furthermore,column i is zero so we may set U [i, i + 1] = 0 to make sure that P UP isupper triangular.The above algorithm maintains the RU-decomposition of the boundary matrixin a constant number of row and column operations. It thus takes linear timeto perform a transposition of two contiguous simplices in the ordering of thefiltration.Switches. A transposition of two simplices may or
View Full Document
Unlocking...