Homología persistente

Method for computing topological features of a space at different spatial resolutions

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

La homología persistente es un método para calcular las características topológicas de un espacio en diferentes resoluciones espaciales. Las características más persistentes se detectan en un amplio rango de escalas espaciales y se considera que es más probable que representen características reales 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, que es 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 desplazamiento en la nube de puntos y tomar su nervio para obtener la filtración simplicial conocida como filtración de Čech . ^[2] Una construcción similar utiliza una secuencia anidada de complejos de Vietoris-Rips conocida como filtración de Vietoris-Rips . ^[3]

Definición

Formalmente, considere una función de valor real en un complejo simplicial que no es decreciente en secuencias crecientes de caras, por lo que siempre que es una cara de en . Entonces, para cada conjunto de subniveles es un subcomplejo de K , y el ordenamiento de los valores de en los simplices 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 simpliciales 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 los rangos de esos grupos. ^[4] Los números de Betti persistentes para 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 preservando 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 una función lineal siempre que , con igual a la identidad y para . Equivalentemente, podemos considerarlo como un funtor de 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 cuerpo indexado por : La multiplicación por corresponde a avanzar un paso en el módulo de persistencia. Intuitivamente, las partes libres del lado derecho corresponden a los generadores de homología que aparecen a nivel de filtración y nunca desaparecen, mientras que las partes de torsión corresponden a las que aparecen a nivel de filtración y duran pasos de la filtración (o equivalentemente, desaparecen a nivel de filtración ). ^{[7] [6]} ${\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).}$$ ${\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 como el tiempo de nacimiento y su coordenada y como el tiempo de muerte. De manera equivalente, los mismos datos se representan mediante 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 de cuello de botella es una métrica natural en el espacio de diagramas de persistencia dada por los rangos where sobre biyecciones. Una pequeña perturbación en la filtración de entrada conduce a una pequeña perturbación de su diagrama de persistencia en la distancia de cuello de botella. Para ser más concretos, considere una filtración en un espacio homeomorfo a un complejo simplicial determinado por los conjuntos de subniveles de una función continua domesticada . La función que lleva al diagrama de persistencia de su homología th es 1-Lipschitz con respecto a la -métrica en funciones y la distancia de cuello de botella en diagramas de persistencia. Es decir, . ^[8] $${\displaystyle W_{\infty }(X,Y):=\inf _{\varphi :X\to Y}\sup _{x\in X}\Vert x-\varphi (x)\Vert _{\infty },}$$ ${\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 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]

Véase 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 de Čech aproximado en dimensiones bajas y altas". En Cai, Leizhen; Cheng, Siu-Wing; Lam, Tak-Wah (eds.). Algoritmos y computación . Apuntes de clase en 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. Número de identificación del sujeto  5770506.
3. Dey, Tamal K.; Shi, Dayu; Wang, Yusu (30 de enero de 2019). "SimBa: una herramienta eficiente para aproximar la persistencia de la filtración de Rips mediante un colapso por lotes simple". ACM Journal of Experimental Algorithmics . 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 Americana.
5. Verri, A.; Uras, C.; Frosini, P.; Ferri, M. (1993). "Sobre el uso de funciones de tamaño para el análisis de forma". Cibernética biológica . 70 (2): 99–107. doi :10.1007/BF00200823. S2CID  39065932.
6. Barannikov, Sergey (1994). "Complejo de Morse enmarcado y sus invariantes". Avances en las matemáticas soviéticas . 21 : 93–115.
7. Zomorodian, Afra; Carlsson, Gunnar (19 de noviembre de 2004). "Computing Persistent Homology". 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). "Estabilidad de los diagramas de persistencia". Geometría discreta y computacional . 37 (1): 103–120. doi : 10.1007/s00454-006-1276-5 . ISSN  0179-5376.
9. Otter, Nina; Porter, Mason A; Tillmann, Ulrike; et al. (9 de agosto de 2017). "Una hoja de ruta para el cálculo de la homología persistente". EPJ Data Science . 6 (1). Springer: 17. doi : 10.1140/epjds/s13688-017-0109-5 . ISSN  2193-1127. PMC 6979512 . PMID  32025466. 
10. Las licencias que se incluyen aquí son un resumen y no se consideran declaraciones completas de las licencias. Algunos paquetes pueden usar bibliotecas con licencias diferentes.
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. Maria, Clément; 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.