Persistent Homology

画像認識などを計算機で行なうために Edelsbrunner と Letscher と Zomorodian [ELZ02] により定義されたもので persistent homology と呼ばれるものがある。 Gunnar Carlsson もかかわっている [ZC05] ようである。

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

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

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

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

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

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

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

  • persistence module

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

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

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

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

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

Frosini と Landi の [FL] によると, persistent homology より前に, 同じ動機で Frosini により導入された概念として size function というものがある。他にも, 類似のものや変種が色々考えられている。

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

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

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

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

References

[Adl+]

Robert J. Adler, Omer Bobrowski, Matthew S. Borman, Eliran Subag, and Shmuel Weinberger. Persistent Homology for Random Fields and Complexes. arXiv: 1003.1001.

[BB]

Omer Bobrowski and Matthew Strom Borman. Euler Integration of Gaussian Random Fields and Persistent Homology. arXiv: 1003.5175.

[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.

[BL]

Ulrich Bauer and Michael Lesnick. Persistence Diagrams as Diagrams: A Categorification of the Stability Theorem. arXiv: 1610.10085.

[Blu+]

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. arXiv: 1206.4581.

[BP]

Saugata Basu and Laxmi Parida. Spectral Sequences, Exact Couples and Persistent Homology of filtrations. arXiv: 1308.0801.

[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+]

Frederic Chazal, Vin de Silva, Marc Glisse, and Steve Oudot. The structure and stability of persistence modules. arXiv: 1207.3674.

[CSO]

Frederic Chazal, Vin de Silva, and Steve Oudot. Persistence stability for geometric complexes. arXiv: 1207.3885.

[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.

[FL]

Patrizio Frosini and Claudia Landi. Stability of multidimensional persistent homology with respect to domain perturbations. arXiv: 1001.1078.

[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.

[MS]

Robert MacPherson and Benjamin Schweinhart. Measuring Shape with Topology. arXiv: 1011.2258.

[Vej]

Mikael Vejdemo-Johansson. Sketches of a platypus: persistent homology and its algebraic foundations. arXiv: 1212.5398.

[Wei11]

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

[ZC05]

Afra Zomorodian and Gunnar Carlsson. “Computing persistent homology”. In: Discrete Comput. Geom. 33.2 (2005), pp. 249–274. url: http://dx.doi.org/10.1007/s00454-004-1146-y.

[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.