Homología persistente

Consulte homología para obtener una introducción a la notación.

La homología persistente es un método para calcular características topológicas de un espacio en diferentes resoluciones espaciales. Las características más persistentes se detectan en una amplia gama de escalas espaciales y se considera que es más probable que representen características verdaderas del espacio subyacente en lugar de artefactos de muestreo, ruido o una elección particular de parámetros. ^[1]

Para encontrar la homología persistente de un espacio, primero se debe representar el espacio como un complejo simplicial . Una función de distancia en el espacio subyacente corresponde a una filtración del complejo simplicial, es decir, una secuencia anidada de subconjuntos crecientes. Un método común para hacer esto es tomar la filtración de subnivel de la distancia a una nube de puntos , o equivalentemente, la filtración de compensación en la nube de puntos y tomar su valor para obtener la filtración simple conocida como filtración de Čech . ^[2] Una construcción similar utiliza una secuencia anidada de complejos Vietoris-Rips conocida como filtración Vietoris-Rips . ^[3]

Definición

Formalmente, considere una función de valor real en un complejo simplicial que no sea decreciente en secuencias crecientes de caras, por lo que siempre que sea una cara de en . Entonces, para cada conjunto de subniveles es un subcomplejo de K , y el ordenamiento de los valores de en los simples en (que en la práctica siempre es finito) induce un ordenamiento en los complejos de subniveles que define una filtración. ${\displaystyle f:K\rightarrow \mathbb {R} }$ ${\displaystyle f(\sigma )\leq f(\tau )}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle K}$ ${\displaystyle a\in \mathbb {R} }$ ${\displaystyle K_{a}=f^{-1}((-\infty ,a])}$ ${\displaystyle f}$ ${\displaystyle K}$

${\displaystyle \emptyset =K_{0}\subseteq K_{1}\subseteq \cdots \subseteq K_{n}=K}$

Cuando , la inclusión induce un homomorfismo en los grupos de homología simplicial para cada dimensión . Los grupos de homología persistentes son las imágenes de estos homomorfismos, y los números de Betti persistentes son las filas de esos grupos. ^[4] Los números de Betti persistentes coinciden con la función de tamaño , un predecesor de la homología persistente. ^[5] ${\displaystyle 0\leq i\leq j\leq n}$ ${\displaystyle K_{i}\hookrightarrow K_{j}}$ ${\displaystyle f_{p}^{i,j}:H_{p}(K_{i})\rightarrow H_{p}(K_{j})}$ ${\displaystyle p}$ ${\displaystyle p^{\text{th}}}$ ${\displaystyle p^{\text{th}}}$ ${\displaystyle \beta _{p}^{i,j}}$ ${\displaystyle p=0}$

Cualquier complejo filtrado sobre un campo puede llevarse mediante una transformación lineal que preserva la filtración a la llamada forma canónica , una suma directa definida canónicamente de complejos filtrados de dos tipos: complejos unidimensionales con diferencial trivial y complejos bidimensionales con homología trivial . ^[6] ${\displaystyle F}$ ${\displaystyle d(e_{t_{i}})=0}$ ${\displaystyle d(e_{s_{j}+r_{j}})=e_{r_{j}}}$

Un módulo de persistencia sobre un conjunto parcialmente ordenado es un conjunto de espacios vectoriales indexados por , con un mapa lineal siempre , con igual a la identidad y para . De manera equivalente, podemos considerarlo como un functor desde lo considerado como una categoría a la categoría de espacios vectoriales (o -módulos ). Existe una clasificación de módulos de persistencia sobre un campo indexado por : ${\displaystyle P}$ ${\displaystyle U_{t}}$ ${\displaystyle P}$ ${\displaystyle u_{t}^{s}:U_{s}\to U_{t}}$ ${\displaystyle s\leq t}$ ${\displaystyle u_{t}^{t}}$ ${\displaystyle u_{t}^{s}\circ u_{s}^{r}=u_{t}^{r}}$ ${\displaystyle r\leq s\leq t}$ ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle F}$ ${\displaystyle \mathbb {N} }$

$${\displaystyle U\simeq \bigoplus _{i}x^{t_{i}}\cdot F[x]\oplus \left(\bigoplus _{j}x^{r_{j}}\cdot (F[x]/(x^{s_{j}}\cdot F[x]))\right).}$$

^{[7] [6]} ${\displaystyle x}$ ${\displaystyle t_{i}}$ ${\displaystyle r_{j}}$ ${\displaystyle s_{j}}$ ${\displaystyle s_{j}+r_{j}}$

Cada uno de estos dos teoremas nos permite representar de forma única la homología persistente de un complejo simplicial filtrado con un código de barras de persistencia o un diagrama de persistencia . Un código de barras representa cada generador persistente con una línea horizontal que comienza en el primer nivel de filtración donde aparece y termina en el nivel de filtración donde desaparece, mientras que un diagrama de persistencia traza un punto para cada generador con su coordenada x, la hora de nacimiento y su Coordenada y del tiempo de muerte. De manera equivalente, los mismos datos están representados por la forma canónica de Barannikov , ^[6] donde cada generador está representado por un segmento que conecta los valores de nacimiento y muerte trazados en líneas separadas para cada uno . ${\displaystyle p}$

Estabilidad

La homología persistente es estable en un sentido preciso, lo que proporciona robustez frente al ruido. La distancia del cuello de botella es una métrica natural en el espacio de los diagramas de persistencia dado por

$${\displaystyle W_{\infty }(X,Y):=\inf _{\varphi :X\to Y}\sup _{x\in X}\Vert x-\varphi (x)\Vert _{\infty },}$$

^[8] ${\displaystyle \varphi }$ ${\displaystyle X}$ ${\displaystyle f:X\to \mathbb {R} }$ ${\displaystyle D}$ ${\displaystyle f}$ ${\displaystyle k}$ ${\displaystyle \sup }$ ${\displaystyle W_{\infty }(D(f),D(g))\leq \lVert f-g\rVert _{\infty }}$

Cálculo

Existen varios paquetes de software para calcular los intervalos de persistencia de una filtración finita. ^[9] El algoritmo principal se basa en llevar el complejo filtrado a su forma canónica mediante matrices triangulares superiores. ^[6]

Ver también

• Análisis de datos topológicos.
• Topología computacional

Referencias

1. Carlsson, Gunnar (2009). "Topología y datos". Boletín AMS 46(2) , 255–308.
2. Kerber, Michael; Sharathkumar, R. (2013). "Complejo Čech aproximado en dimensiones bajas y altas". En Cai, Leizhen; Cheng, Siu-Wing; Lam, Tak-Wah (eds.). Algoritmos y Computación . Apuntes de conferencias sobre informática. vol. 8283. Berlín, Heidelberg: Springer. págs. 666–676. doi :10.1007/978-3-642-45030-3_62. ISBN 978-3-642-45030-3. S2CID  5770506.
3. Dey, Tamal K.; Shi, Dayu; Wang, Yusu (30 de enero de 2019). "SimBa: una herramienta eficaz para aproximar la persistencia de la filtración Rips mediante el colapso de lotes simple". Revista ACM de algorítmica experimental . 24 : 1,5:1–1,5:16. doi : 10.1145/3284360 . ISSN  1084-6654. S2CID  216028146.
4. Edelsbrunner, H y Harer, J (2010). Topología computacional: una introducción . Sociedad Matemática Estadounidense.
5. Verri, A.; Uras, C.; Frosini, P.; Ferri, M. (1993). "Sobre el uso de funciones de tamaño para el análisis de formas". Cibernética biológica . 70 (2): 99-107. doi :10.1007/BF00200823. S2CID  39065932.
6. Barannikov, Sergey (1994). "Complejo Morse enmarcado y sus invariantes". Avances en las matemáticas soviéticas . 21 : 93-115.
7. Zomorodiano, Afra; Carlsson, Gunnar (19 de noviembre de 2004). "Computación de la homología persistente". Geometría discreta y computacional . 33 (2): 249–274. doi : 10.1007/s00454-004-1146-y . ISSN  0179-5376.
8. Cohen-Steiner, David; Edelsbrunner, Herbert; Harer, John (12 de diciembre de 2006). "Diagramas de estabilidad de persistencia". Geometría discreta y computacional . 37 (1): 103–120. doi : 10.1007/s00454-006-1276-5 . ISSN  0179-5376.
9. Nutria, Nina; Portero, Mason A; Tillmann, Ulrike; et al. (09/08/2017). "Una hoja de ruta para el cálculo de la homología persistente". Ciencia de datos de EPJ . 6 (1). Springer: 17. doi : 10.1140/epjds/s13688-017-0109-5 . ISSN  2193-1127. PMC 6979512 . PMID  32025466. 
10. Las licencias aquí son un resumen y no se consideran declaraciones completas de las licencias. Algunos paquetes pueden utilizar bibliotecas con diferentes licencias.
11. Bauer, Ulrich; Kerber, Michael; Reininghaus, enero; Wagner, Hubert (2014). "PHAT - Caja de herramientas de algoritmos de homología persistente". Software Matemático – ICMS 2014 . Springer Berlín Heidelberg. págs. 137-143. doi :10.1007/978-3-662-44199-2_24. ISBN 978-3-662-44198-5. ISSN  0302-9743.
12. María, Clemente; Boissonnat, Jean-Daniel; Glisse, Marc; et al. (2014). "La biblioteca Gudhi: complejos simpliciales y homología persistente". Software matemático - ICMS 2014 (PDF) . Berlín, Heidelberg: Springer. págs. 167-174. doi :10.1007/978-3-662-44199-2_28. ISBN 978-3-662-44198-5. ISSN  0302-9743. S2CID  17810678.