Persistent Homology

画像認識などを計算機で行なうために Edelsbrunner と Letscher と Zomorodian [ELZ02] により定義されたもので persistent homology と呼ばれるものがある。 Koyama らの [Koy+] によると, 同様のアイデアは, 独立に Robins [Rob99] によっても考えられていたようである。 また, 彼等によると, Frosini により導入された size function の理論 [Fro90] は \(0\)次元の persistent homology と同等のものであり, 最初に persistent homology のアイデア (と同等のもの) が現れたのは, この Frosini の仕事のようである。

現在では応用トポロジーの主要な道具の一つになっている。 既に, 2012年の Edinburgh での応用および計算トポロジーの集会でも, 8割ぐらいの講演で使われていたように思う。 その後参加した応用トポロジーの集会でも, ほとんどの講演は persistent homology に関するものだった。その理由の一つは, 実際に様々な現実の問題に応用できることにある。 Persistent homology を用いて様々なデータを分析することを topological data analysis (TDA) と言ったりする。

• persistent homology の応用
• TDA

解説も既にいくつも出ている。Edelsbrunner と Harer の [EH08], Carlsson の [Car09], Bubenik と Kim の [BK07], Adler らの [Adl+10], Chazal らの [CSO14] など。 AMSのNotices 2011年 1月号には, Weinberger の “WHAT IS \(\ldots \)” [Wei11] がある。 本も, Zomorodian の [Zom05] や Edelsbrunner と Harer の [EH10] などが出ている。 日本語では, 平岡氏の [平岡裕13] が出た。 Curry による cosheaf の視点からの解説 [Cur15] もある。

Vjedemo-Johansson [Vej14] が言うように, これらはほとんどが data analyst 向けに algorithm を主眼に書かれたものである。Vjedemo-Johansson は, 数学者向けに書いた, と言っている。

基本的なアイデアは, Euclid 空間の点をサンプリングしてできたデータ (point cloud) から, 実数のパラメータを用いて filtered chain complex を作り, パラメータを変化させたときの homology の変化から元の point cloud に関する情報を読み取る, というものである。

Filtration と homology と言えば spectral sequence であるが, persistent homology と spectral sequence の関係を調べたものとして Basu と Parida の [BP17] がある。 彼等によると, spectral sequence の各 \(E^r\)-term の次元は persistent homology から計算できるようである。

Persistent homology が使われる filtered chain complex は, filtered simplicial complex からできることが多いが, point cloud から作られる filtered simplicial complex は, Vietoris-Rips complex を始めとして, 様々なものがある。

• filtered simplicial complexes

できた homology は, poset \(\R \) を small category とみなしたものから加群の圏への functor になっている。そのようなものを, persistence module という。 Chazal と de Silva と Glisse と Oudot の [Cha+16] を見るとよい。

• persistence module

Edelsbrunner ら [EJM15] は \(\R \) から matchings の成す圏への functor とみなすことを提案している。 それに基いて, Bauerと Lesnick [BL20] は stability theorem の categorification を考えている。

Persistent homology は, 大量のデータを扱う場合に用いられるので, その計算結果をうまく表示する方法が必要である。Bubenik はそのような方法を persistent homology の descriptor と呼んでいる。有名なものに, barcode や persistence diagram といったものがある。

• persistent homology の表示方法

もちろん, 表示する以前に計算しないといけない。効率よく計算するために, discrete Morse theory を使うというアイデアがある。Mischaikov と Nanda の仕事 [MN13] や Dlotko と Wagner の [DW] である。

Di Fabio と Landi [DL11] は, Mayer-Vietoris sequence を考えている。

Blumberg らの [Blu+14] で指摘されている persistent homology の欠点として, sampling のことが考慮されていないことがある。つまり sampling された後のデータの不変量ではあるが, point cloud の各点が選ばれる確率も考慮した measure space としての不変量にはなっていない, ということである。

Persistent homology のアイデアはとても単純なものなので, 類似のものや変種が色々考えられている。

• persistent homology の変種

Bobrowski と Borman は, [BB12] で persistent homology と Euler 標数の関係を考えている。 Persistent homology に対する Euler標数の定義や Ghrist らの Euler integration との関係を考えていて面白い。

コホモロジーの場合, Steenrod operation を使うことが考えられるが, それについては, Lupo, Medina-Mardones, Tauzin の [LMT22] がある。

Persistent homology の元々の動機は画像認識だったことから, 数学的に「形」をとらえるためにも使えると考えてもおかしくはない。実際, MacPherson と Schweinhart [MS12] が persistent homology を用いて, P.H. (persistent homology) dimension などの概念を定義している。

• P.H. dimension
• P.H. self-similarity

P.H. dimension は Hausdorff dimension とかなり近いもののようである。

References

[Adl+10]

Robert J. Adler, Omer Bobrowski, Matthew S. Borman, Eliran Subag, and Shmuel Weinberger. “Persistent homology for random fields and complexes”. In: Borrowing strength: theory powering applications—a Festschrift for Lawrence D. Brown. Vol. 6. Inst. Math. Stat. (IMS) Collect. Inst. Math. Statist., Beachwood, OH, 2010, pp. 124–143. arXiv: 1003.1001.

[BB12]

Omer Bobrowski and Matthew Strom Borman. “Euler integration of Gaussian random fields and persistent homology”. In: J. Topol. Anal. 4.1 (2012), pp. 49–70. arXiv: 1003 . 5175. url: https://doi.org/10.1142/S1793525312500057.

[BK07]

Peter Bubenik and Peter T. Kim. “A statistical approach to persistent homology”. In: Homology, Homotopy Appl. 9.2 (2007), pp. 337–362. arXiv: math/0607634. url: http://projecteuclid.org/euclid.hha/1201127341.

[BL20]

Ulrich Bauer and Michael Lesnick. “Persistence diagrams as diagrams: a categorification of the stability theorem”. In: Topological data analysis—the Abel Symposium 2018. Vol. 15. Abel Symp. Springer, Cham, [2020] ©2020, pp. 67–96. arXiv: 1610.10085. url: https://doi.org/10.1007/978-3-030-43408-3_3.

[Blu+14]

Andrew J. Blumberg, Itamar Gal, Michael A. Mandell, and Matthew Pancia. “Robust statistics, hypothesis testing, and confidence intervals for persistent homology on metric measure spaces”. In: Found. Comput. Math. 14.4 (2014), pp. 745–789. arXiv: 1206.4581. url: https://doi.org/10.1007/s10208-014-9201-4.

[BP17]

Saugata Basu and Laxmi Parida. “Spectral sequences, exact couples and persistent homology of filtrations”. In: Expo. Math. 35.1 (2017), pp. 119–132. arXiv: 1308 . 0801. url: https://doi.org/10.1016/j.exmath.2016.06.007.

[Car09]

Gunnar Carlsson. “Topology and data”. In: Bull. Amer. Math. Soc. (N.S.) 46.2 (2009), pp. 255–308. url: http://dx.doi.org/10.1090/S0273-0979-09-01249-X.

[Cha+16]

Frédéric Chazal, Vin de Silva, Marc Glisse, and Steve Oudot. The structure and stability of persistence modules. SpringerBriefs in Mathematics. Springer, [Cham], 2016, pp. x+120. isbn: 978-3-319-42543-6; 978-3-319-42545-0. arXiv: 1207 . 3674. url: https://doi.org/10.1007/978-3-319-42545-0.

[CSO14]

Frédéric Chazal, Vin de Silva, and Steve Oudot. “Persistence stability for geometric complexes”. In: Geom. Dedicata 173 (2014), pp. 193–214. arXiv: 1207.3885. url: https://doi.org/10.1007/s10711-013-9937-z.

[Cur15]

Justin Michael Curry. “Topological data analysis and cosheaves”. In: Jpn. J. Ind. Appl. Math. 32.2 (2015), pp. 333–371. arXiv: 1411. 0613. url: https://doi.org/10.1007/s13160-015-0173-9.

[DL11]

Barbara Di Fabio and Claudia Landi. “A Mayer-Vietoris formula for persistent homology with an application to shape recognition in the presence of occlusions”. In: Found. Comput. Math. 11.5 (2011), pp. 499–527. url: https://doi.org/10.1007/s10208-011-9100-x.

[DW]

Paweł Dłotko and Hubert Wagner. Computing homology and persistent homology using iterated Morse decomposition. arXiv: 1210.1429.

[EH08]

Herbert Edelsbrunner and John Harer. “Persistent homology—a survey”. In: Surveys on discrete and computational geometry. Vol. 453. Contemp. Math. Providence, RI: Amer. Math. Soc., 2008, pp. 257–282.

[EH10]

Herbert Edelsbrunner and John L. Harer. Computational topology. An introduction. Providence, RI: American Mathematical Society, 2010, pp. xii+241. isbn: 978-0-8218-4925-5.

[EJM15]

Herbert Edelsbrunner, Grzegorz Jabłoński, and Marian Mrozek. “The persistent homology of a self-map”. In: Found. Comput. Math. 15.5 (2015), pp. 1213–1244. url: http://dx.doi.org/10.1007/s10208-014-9223-y.

[ELZ02]

Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. “Topological persistence and simplification”. In: Discrete Comput. Geom. 28.4 (2002). Discrete and computational geometry and graph drawing (Columbia, SC, 2001), pp. 511–533. url: http://dx.doi.org/10.1007/s00454-002-2885-2.

[Fro90]

Patrizio Frosini. “A distance for similarity classes of submanifolds of a Euclidean space”. In: Bull. Austral. Math. Soc. 42.3 (1990), pp. 407–416. url: https://doi.org/10.1017/S0004972700028574.

[Koy+]

Musashi Ayrton Koyama, Vanessa Robins, Katharine Turner, and Facundo Memoli. Reduced Vietoris-Rips Complexes: New methods to compute Vietoris-Rips Persistent Homology. arXiv: 2307.16333.

[LMT22]

Umberto Lupo, Anibal M. Medina-Mardones, and Guillaume Tauzin. “Persistence Steenrod modules”. In: J. Appl. Comput. Topol. 6.4 (2022), pp. 475–502. arXiv: 1812 . 05031. url: https://doi.org/10.1007/s41468-022-00093-7.

[MN13]

Konstantin Mischaikow and Vidit Nanda. “Morse Theory for Filtrations and Efficient Computation of Persistent Homology”. In: Discrete Comput. Geom. 50.2 (2013), pp. 330–353. url: http://dx.doi.org/10.1007/s00454-013-9529-6.

[MS12]

Robert MacPherson and Benjamin Schweinhart. “Measuring shape with topology”. In: J. Math. Phys. 53.7 (2012), pp. 073516, 13. arXiv: 1011.2258. url: https://doi.org/10.1063/1.4737391.

[Rob99]

V. Robins. “Towards computing homology from finite approximations”. In: Proceedings of the 14th Summer Conference on General Topology and its Applications (Brookville, NY, 1999). Vol. 24. Summer. 1999, 503–532 (2001).

[Vej14]

Mikael Vejdemo-Johansson. “Sketches of a platypus: a survey of persistent homology and its algebraic foundations”. In: Algebraic topology: applications and new directions. Vol. 620. Contemp. Math. Amer. Math. Soc., Providence, RI, 2014, pp. 295–319. arXiv: 1212. 5398. url: https://doi.org/10.1090/conm/620/12371.

[Wei11]

Shmuel Weinberger. “What is\(\ldots \)persistent homology?” In: Notices Amer. Math. Soc. 58.1 (2011), pp. 36–39.

[Zom05]

Afra J. Zomorodian. Topology for computing. Vol. 16. Cambridge Monographs on Applied and Computational Mathematics. Cambridge: Cambridge University Press, 2005, pp. xiv+243. isbn: 0-521-83666-2. url: http://dx.doi.org/10.1017/CBO9780511546945.

[平岡裕13]

平岡裕章. タンパク質構造とトポロジー – パーシステントホモロジー群入門 –. シリーズ・現象を解明する数学. 東京: 共立出版, 2013, p. 131.