26
$\begingroup$

Persistent homology is a well-developed tool which allows topological analysis of large data sets. From a topological perspective, the input is a filtered complex, and the output is a sequence of collections of intervals (one for each dimension) called a persistence barcode. The barcode gives information about homology classes which are born and die as you vary the scale (filtration parameter).

This is a very brief, non-expert summary. By now there are several good survey articles on the subject by experts in the field, for example by Gunnar Carlsson and Rob Ghrist.

On the other hand, given a filtered complex $X_\bullet$, one obtains a spectral sequence converging to the homology $H_\ast(X_\bullet)$ (or at least its associated graded object) . It is natural to ask how the persistence barcode relates to this spectral sequence. In a formative paper on the subject by Carlsson and Zomorodian, the authors ask exactly this question in section 1.4 of the introduction, claiming that a persistence interval of length $r$ in the barcode corresponds to a differential $d_{r+1}$. Thus, in principle, any algorithm for computing persistent homology should give an algorithmic way of computing the differentials in a spectral sequence. So persistent homology, which already has many applications outside of topology, becomes potentially applicable to topology itself.

Has anyone ever pursued this approach, and used algorithms for persistent homology to compute the differentials in a spectral sequence? Does this lead to any new theoretical insights?

I am imagining that by knowing the values of a differential in a given situation one might guess at a description of the differential (eg, in terms of cohomology operations) which applies more generally.

Edit: The book Computational Topology: An Introduction by Edelsbrunner and Harer states a Spectral Sequence Theorem in Chapter VII.4, which says roughly that the total rank of the $E^r_{\ast,\ast}$ page of the spectral sequence equals the number of homology classes of persistence $r$ or larger. Here coefficients are taken mod 2. This makes precise the claim made by Carlsson and Zomorodian.

$\endgroup$
  • $\begingroup$ Interesting question. Are you familiar with the universal examples of Bousfield and Kan? $\endgroup$ – Sean Tilson Jun 5 '15 at 13:42
  • $\begingroup$ @SeanTilson: Thanks. No, I don't think I am. Could you provide a reference? $\endgroup$ – Mark Grant Jun 5 '15 at 13:56
  • $\begingroup$ This might be the first reference, I don't know if it is the best. what they do is construct a map of SS for each element in the target. The domain is a SS with only one non-zero differential. ams.org/journals/tran/1973-177-00/S0002-9947-1973-0372859-6/… $\endgroup$ – Sean Tilson Jun 5 '15 at 15:32
15
$\begingroup$

The answer to your question is no, nobody has used persistence to improve the algorithmic efficiency of computing differentials, although of course the relationship between persistence intervals of a filtration and various terms in its Leray spectral sequence have been described rather explicitly by Basu and Parida.

Here's an elementary observation: as mentioned in that article by Carlsson and Zomorodian, every sequence of $k$-modules admits a straightforward reinterpretation as a graded $k[t]$-module where $t$ acts by moving things forward one step along the grading. The existence of a persistence barcode relies crucially on the structure theorem for graded modules over graded PIDs. Since $k[t]$ is a PID only when $k$ is a field, relying on persistence will not solve any extension problems for you when you try to compute differentials -- all your $E_{\bullet,\bullet}^\bullet$s will have to be vector spaces already.

$\endgroup$
  • $\begingroup$ Thank you very much for the reference and the observation. $\endgroup$ – Mark Grant Sep 17 '15 at 6:16
7
$\begingroup$

there is actually a bit more to this story. The computational topology community has indeed wrestled with spectral sequences. The connection to spectral sequences has been discussed since as early as the Carlsson & Zomorodian paper mentioned by Vidit (although, not necessarily explicitly in that paper).

To make the connection clear, the $E_\infty$ page is a graded $k[t]$-module containing the "infinite" bars. the bars of length $p$ aren't exactly on the $p^{th}$ page, but, when you compute homology on page $p-1$, you can find the bars of length $p$ by hanging onto the images of the $p$-th differential.

Speaking informally, in the language of numerical linear algebra, this is like looking at successively larger block diagonals of the boundary matrix written down in an appropriate way, reducing them, and then ``expanding."

Infact, this algorithm (albeit not the direct connection to spectral sequences) is written down in the paper ``Clear and Compress" due to Bauer et. al

In particular, there is also the question of whether other spectral sequences speed up computation in a practical sense. There are results that suggest asymptotic improvements in certain cases. In practice the jury is still out.

$\endgroup$
  • $\begingroup$ Hi Ryan (nice to see you on here!). Just a quick comment about your first paragraph: as Mark points out, Carlsson and Zomorodian explicitly mention the connection with spectral sequences in Section 1.4 of their paper. $\endgroup$ – Vidit Nanda Mar 19 '16 at 15:08
  • $\begingroup$ @ViditNanda ah, yes. I guess they do mention the correspondence in the paper. Nevertheless the direct application to a parallel algorithm is not, although, pretty straightforward. $\endgroup$ – rhl Mar 20 '16 at 20:43
  • $\begingroup$ I guess, in direct answer to the question, the differentials in the persistent setting are just essentially connecting homomorphisms, since the usual treatment is with inclusion maps. There isn't much to "speedup" here, as in order to "compute the map" you need to write down the output for each input. I suppose the only thing to do is observe when an output must be zero. Although, I don't think there is any hope for this. $\endgroup$ – rhl Mar 20 '16 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.