Computing Zigzag Persistence with HDVF

Aldo Gonzalez-Lorenzo
Aix-Marseille University (France), LIS

Introduction

Persistent homology: add simplices, track holes

Zigzag persistent homology: add or remove simplices, track holes

Practical algorithms:

  • Carlsson, de Silva, Morozov (2009) 📄: simple algorithm, convoluted theory.
  • Maria, Oudot (2015) 📄: different approach and algorithm.
  • Dey, Hou (2022) 📄: offline algorithm, just computes persistent homology, fastest.

Same time complexity: \(\mathcal{O}(n \cdot m^2)\), where

  • n: number of steps in the filtration
  • m: size of largest simplicial complex

Motivation:

  • More straightforward algorithm
  • with same complexity

Menu of the day:

  • Easy explanation of zigzag persistent homology
  • \(\mathcal{O}(n \cdot m^2)\) algorithm for zigzag persistent relative homology

Homology

(with Homological Discrete Vector Fields)

Simplicial complex

Homology group

\(H(K) := \text{ker}(\partial) / \text{im}(\partial)\)

HDVF

Let \(K\) be a simplicial complex. Let \(P, S \subset K, P \cap S = \emptyset\).
A pair \(X = (P, S)\) is a homological discrete vector field if \(d(S)_{|P}\) is an invertible matrix.

Its associated reduction: four maps \((f, g, h, d)\) carrying homological information.

\[\begin{align*} h &= i_S \circ (j_P \circ \partial \circ i_S)^{-1} \circ j_P \\ f &= j_C \circ (1 - \partial \circ h) \\ g &= (1 - h \circ \partial) \circ i_C \\ d &= f \circ \partial \circ i_C \end{align*}\]

There are 6 elementary operations to transform an HDVF (and its reduction)

How to make an HDVF?

  • Look for a non-zero entry in the matrix of \(d\)
  • Change its pair of simplices with \(\mathtt{A}\)
  • No need to check invertibility of submatrix

An HDVF is perfect if \(d = 0\) (we can't add more red-green simplices)

  • \(\{[g(\gamma)] \mid \gamma \in C\}\) is a basis of \(H(K)\)
  • \(f(x) = 0\) if and only if \(x\) is a boundary
  • \( x \sim y \iff f(x) = f(y)\)
  • \(x \sim g \circ f(x)\)

Simplicial complex + perfect HDVF = homology group

Zigzag Persistent Homology

(with Representative Interval Decompositions)

Zigzag filtration

Sequence of simplicial complexes, add or remove one simplex

Representative basis

Set of cycles whose homology classes form a basis for \(H(K)\)

Representative Interval Module

Sequence of cycles where inclusions send non-empty cycles to the same homology class

Representative Interval Decomposition

Grid of cycles where

  • each column is a representative basis
  • each row is a representative interval module

Representative Interval Decomposition

Theorem The intervals of non-empty cycles are the persistence intervals âœ…

Zigzag filtration + RID = persistence intervals

Computing Zigzag Persistent Homology

(spoiler: it is not efficient)

Problem: extend a RID after appending a new simplicial complex

New representative basis

There are four cases:

  • add or remove a simplex
  • which adds or removes a hole

(A.1) Add a simplex, add a hole

Lemma If \(\partial(\sigma)\) is a boundary, then add a cycle \(x\) containing \(\sigma\)

(A.2) Add a simplex, remove a hole

Lemma If \(\partial(\sigma) \sim\) some cycle \(x\) of the basis, then remove it

(B.1) Remove a simplex, add a hole

Lemma If \(\sigma\) does not belong to any cycle of the basis, then add \(\partial(\sigma)\)

(B.2) Remove a simplex, remove a hole

Lemma If \(\sigma\) belongs to exactly one cycle of the basis, then remove it

Linear combinations in a RID

What if

  • \(\partial(\sigma) \sim x + x'\) in case A.2?
  • \(\sigma\) belongs to two cycles in case B.2?

We need to change the representative basis ⟶ RID

Lemma If \(\mathbf{x} \leq \mathbf{y}\) then we can replace \(\mathbf{y} \gets \mathbf{x} + \mathbf{y}\) to change the representative basis

\[\mathbf{x} \leq \mathbf{y} \iff \begin{cases} \left( b(\mathbf{x}) \leq b(\mathbf{y}) \text{ and } \mathbf{y} \text{ is forward} \right) & \text{or} \\ \left( b(\mathbf{y}) \leq b(\mathbf{x}) \text{ and } \mathbf{x} \text{ is backward} \right) \end{cases}\]

Abstract algorithm

  • initializeModules() (first column)
  • for each step:
    • if add simplex \(\sigma\):
      • \(x = \sum \lambda_{k} \cdot x^{(k)} \gets\) decompose(\(\partial(\sigma))\)
      • if \(x = 0\):    case A.1 (add a hole)
      • else:   case A.2 (remove a hole)
    • if remove simplex \(\sigma\):
      • \(x = \sum \lambda_{k} \cdot x^{(k)} \gets\) cyclesWith(\(\sigma)\)
      • if \(x = 0\):   case B.1 (add a hole)
      • else:   case B.2 (remove a hole)

Case A.1

  • placeholderA1()
  • \(y \gets\) newCycleForward() (the new cycle)
  • extend all rows, add row \((0, ..., 0, y)\)

Case A.2

  • \(\mathbf{x}^{(i)} \gets\) maximum RIM in \(x\)
  • replace \(\mathbf{x}^{(i)}\) by \(\sum \lambda_{k} \cdot \mathbf{x}^{(k)}\) (now \(\partial(\sigma) \sim \mathbf{x}^{(i)}\))
  • append 0 to \(\mathbf{x}^{(i)}\), extend other rows
  • placeholderA2()

Case B.1

  • placeholderB1()
  • \(y \gets\) newCycleBackward() (the new cycle)
  • extend all rows, add row \((0, ..., 0, y)\)

Case B.2

  • \(\mathbf{x}^{(i)} \gets\) minimum RIM in \(x\)
  • replace \(\mathbf{x}^{(k)}\) by \(\mathbf{x}^{(k)} - \lambda_{k} \cdot \mathbf{x}^{(i)}\) (now \(\sigma\) belongs to a single cycle)
  • append 0 to \(\mathbf{x}^{(i)}\), extend other rows
  • placeholderB2()

Explicit algorithm

We use a perfect HDVF

  • initializeModules(): make a perfect HDVF, use \(g\)
  • decompose(): use \(f\), solve a linear system of equations
  • placeholderA1(), newCycleForward(): use \(\mathtt{I}\), \(g\)
  • placeholderA2(): use \(\mathtt{I}\), \(\mathtt{A}\)
  • placeholderB1(), newCycleBackward(): use \(\mathtt{R}\), \(\mathtt{D}\), \(g \circ f\)
  • placeholderB2(): use \(\mathtt{W}\), \(\mathtt{D}\)

Explicit algorithm

We use a perfect HDVF

  • initializeModules(): make a perfect HDVF, use \(g\)
  • decompose(): use \(f\), solve a linear system of equations
  • placeholderA1(), newCycleForward(): use \(\mathtt{I}\), \(g\)
  • placeholderA2(): use \(\mathtt{I}\), \(\mathtt{A}\)
  • placeholderB1(), newCycleBackward(): use \(\mathtt{R}\), \(\mathtt{D}\), \(g \circ f\)
  • placeholderB2(): use \(\mathtt{W}\), \(\mathtt{D}\)

Time complexity: \(\mathcal{O}(n \cdot m^3 + n^2 \cdot m)\)

Row operations in RID + update perfect HDVF = extend RID

Improvements and Extensions

(spoiler: best for relative homology)

Efficient version of the algorithm

We avoid matrix inversions and multiplications:

  • Operations \(\mathtt{I}\), \(\mathtt{D}\), \(\mathtt{A}\), \(\mathtt{R}\), \(\mathtt{W}\) in \(\mathcal{O}(m^2)\): reuse previous reduction maps
  • decompose() in \(\mathcal{O}(m^2)\): update a change-of-basis matrix

Time complexity: \(\mathcal{O}(n m^3 + n^2 m) \longrightarrow \mathcal{O}(n m^2 + n^2 m)\)

Just the intervals

Ignore the previous columns of the RID

Time complexity: \(\mathcal{O}(n m^2 + n^2 m) \longrightarrow \mathcal{O}(n m^2)\) ✅

Extension for relative homology

If \(L \subset K\), then its relative homology group is \(H(K, L)\)

  • Same algorithm, with four extra cases
  • We also use operation \(\mathtt{W}\)

Time complexity: \(\mathcal{O}(n \cdot m^2)\), where

  • n: number of steps in the filtration
  • m: maximum \(|K - L|\)

Best performance when \(|K-L| \ll |K|\)

Conclusion

In summary

  • RID = zigzag persistent (relative) homology
  • Practical algorithm
  • How to use an HDVF

Future work

  • Zigzag persistent relative cohomology
  • Parallel algorithm: merge two RIDs

Thanks for listening. Questions?