Filtración Vietoris-Rips

Un conjunto de tres subcomplejos anidados dentro de la filtración de Vietoris-Rips en un conjunto de puntos en el plano euclidiano.

En el análisis de datos topológicos , la filtración de Vietoris-Rips (a veces abreviada como " filtración de Rips ") es la colección de complejos de Vietoris-Rips anidados en un espacio métrico creado al tomar la secuencia de complejos de Vietoris-Rips sobre un parámetro de escala creciente. A menudo, la filtración de Vietoris-Rips se utiliza para crear un modelo discreto y simple sobre datos de nubes de puntos incrustados en un espacio métrico ambiental. ^[1] La filtración de Vietoris-Rips es una extensión multiescala del complejo de Vietoris-Rips que permite a los investigadores detectar y rastrear la persistencia de características topológicas , sobre un rango de parámetros, mediante el cálculo de la homología persistente de toda la filtración. ^{[2] [3] [4]} Lleva el nombre de Leopold Vietoris y Eliyahu Rips .

Definición

La filtración de Vietoris-Rips es la colección anidada de complejos de Vietoris-Rips indexados por un parámetro de escala creciente. El complejo de Vietoris-Rips es una construcción clásica en matemáticas que se remonta a un artículo de 1927 ^[5] de Leopold Vietoris , aunque fue considerado independientemente por Eliyahu Rips en el estudio de los grupos hiperbólicos , como señaló Mikhail Gromov en la década de 1980. ^[6] El nombre conjunto "Vietoris-Rips" se debe a Jean-Claude Hausmann. ^[7]

Un ejemplo de un complejo Vietoris-Rips construido sobre puntos en el plano euclidiano.

Dado un espacio métrico y un parámetro de escala (a veces llamado parámetro de umbral o de distancia ) , el complejo de Vietoris-Rips (con respecto a ) se define como , donde es el diámetro , es decir, la distancia máxima de los puntos que se encuentran en . ^[8] ${\displaystyle X}$ ${\displaystyle r\in [0,\infty )}$ ${\displaystyle r}$ ${\displaystyle \mathbf {VR} _{r}(X)=\{\emptyset \neq S\subseteq X\mid S{\text{ finite}};\operatorname {diam} S\leq r\}}$ ${\displaystyle \operatorname {diam} S}$ ${\displaystyle S}$

Observe que si , existe un mapa de inclusión simplicial . La filtración de Vietoris-Rips es la colección anidada de complejos  : ${\displaystyle r\leq s\in [0,\infty )}$ ${\displaystyle \mathbf {VR} _{r}(X)\hookrightarrow \mathbf {VR} _{s}(X)}$ ${\displaystyle \mathbf {VR} _{r}(X)}$

$${\displaystyle \mathbf {VR} (X)=\{\mathbf {VR} _{r}(X)\}_{r\in [0,\infty )}}$$

Si los números reales no negativos se consideran una categoría posetal a través de la relación , entonces la filtración de Vietoris-Rips puede verse como un funtor valorado en la categoría de complejos simpliciales y mapas simpliciales, donde los morfismos (es decir, relaciones en el poset) en la categoría fuente inducen mapas de inclusión entre los complejos. ^[9] Nótese que la categoría de complejos simpliciales puede verse como una subcategoría de , la categoría de espacios topológicos , mediante la postcomposición con el funtor de realización geométrica . ${\displaystyle [0,\infty )}$ ${\displaystyle \leq }$ ${\displaystyle \mathbf {VR} (X):[0,\infty )\to \mathbf {Simp} }$ ${\displaystyle \mathbf {Top} }$

Propiedades

El tamaño de una filtración se refiere al número de símplices en el complejo más grande, asumiendo que el espacio métrico subyacente es finito. Se sabe que el -esqueleto, es decir, el número de símplices hasta la dimensión , de la filtración de Vietoris-Rips es , donde es el número de puntos. ^[10] El tamaño del esqueleto completo tiene precisamente símplices, uno para cada subconjunto no vacío de puntos. ^[9] Dado que esto es exponencial, los investigadores generalmente solo calculan el esqueleto de la filtración de Vietoris-Rips hasta valores pequeños de . ^[2] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O\left(n^{k+1}\right)}$ ${\displaystyle n}$ ${\displaystyle 2^{n}-1}$ ${\displaystyle k}$

Cuando el espacio métrico subyacente es finito, la filtración de Vietoris-Rips a veces se denomina esencialmente discreta , ^[9] lo que significa que existe algún parámetro de escala terminal o máximo tal que para todos , y además que el mapa de inclusión es un isomorfismo para todos excepto un número finito de parámetros . En otras palabras, cuando el espacio métrico subyacente es finito, la filtración de Vietoris-Rips tiene un complejo más grande, y el complejo cambia solo en un número finito de pasos. Esto último implica que la filtración de Vietoris-Rips en un espacio métrico finito puede considerarse como indexada sobre un conjunto discreto como , al restringir la filtración a los parámetros de escala en los que cambia la filtración, y luego reetiquetar los complejos utilizando los números naturales . ${\displaystyle r_{\text{max}}\in [0,\infty )}$ ${\displaystyle \mathbf {VR} _{s}(X)=\mathbf {VR} _{r_{\max }}(X)}$ ${\displaystyle s\geq r_{\max }}$ ${\displaystyle \mathbf {VR} _{s\to t}(X):\mathbf {VR} _{s}(X)\hookrightarrow \mathbf {VR} _{t}(X)}$ ${\displaystyle s\leq t}$ ${\displaystyle \mathbb {N} }$

También se puede dar un límite explícito para el número de pasos en los que cambia la filtración de Vietoris-Rips. El complejo de Vietoris-Rips es un complejo de clique , lo que significa que está completamente determinado por su 1-esqueleto. ^[11] Por lo tanto, el número de pasos en los que cambia la filtración de Vietoris-Rips está limitado por el número de aristas en el complejo más grande. El número de aristas en el complejo más grande es , ya que todos los vértices están unidos por una arista. Por lo tanto, la filtración de Vietoris-Rips cambia en los pasos, donde denota un límite superior asintótico . ${\displaystyle {n \choose 2}=n(n-1)/2}$ ${\displaystyle n}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(-)}$

Para los puntos en el espacio euclidiano , la filtración de Vietoris-Rips es una aproximación a la filtración de Čech, en el sentido de la distancia de entrelazado. ^[1] Esto se deduce del hecho de que para cualquier parámetro de escala , los complejos de Vietoris-Rips y de Čech en un conjunto finito de puntos en el espacio euclidiano satisfacen la relación de inclusión , a la que a veces se hace referencia como el lema de Vietoris-Rips. ^[12] En espacios métricos generales, una aplicación directa de la desigualdad triangular muestra que para cualquier parámetro de escala . ${\displaystyle \alpha }$ ${\displaystyle X}$ ${\displaystyle \mathbf {VR} _{\alpha }(X)\subseteq \operatorname {{\check {C}}ech} _{{\sqrt {2}}\alpha }(X)\subseteq \mathbf {VR} _{{\sqrt {2}}\alpha }(X)}$ ${\displaystyle \mathbf {VR} _{\alpha }(X)\subseteq \operatorname {{\check {C}}ech} _{2\alpha }(X)\subseteq \mathbf {VR} _{2\alpha }(X)}$ ${\displaystyle \alpha }$

Variantes

Aproximaciones

Dado que la filtración de Vietoris-Rips tiene un número exponencial de símplices en su esqueleto completo, se ha realizado una cantidad significativa de investigación para aproximar la homología persistente de la filtración de Vietoris-Rips utilizando construcciones de menor tamaño. El primer trabajo en esta dirección fue publicado por el científico informático Donald Sheehy en 2012, quien mostró cómo construir una filtración de tamaño en el tiempo que aproxima la homología persistente de la filtración de Vietoris-Rips a un margen de error deseado. ^[10] Este tipo de filtración se conoce como filtración de Vietoris-Rips de parse S , ya que elimina puntos de la filtración estándar de Vietoris-Rips utilizando ideas de geometría computacional relacionadas con llaves geométricas . ^[13] Desde entonces, se han desarrollado varios métodos más eficientes para aproximar la filtración de Vietoris-Rips, principalmente utilizando las ideas de Sheehy, pero también basándose en esquemas de aproximación desarrollados para las filtraciones de Čech ^[14] y Delaunay ^[15] . ^{[16] [2]} ${\displaystyle O(n)}$ ${\displaystyle O(n\log n)}$

Extensiones multiparamétricas

Se sabe que la homología persistente puede ser sensible a valores atípicos en el conjunto de datos subyacente. ^[17] Para remediar esto, en 2009 Gunnar Carlsson y Afra Zomorodian propusieron una versión multidimensional de la persistencia, que considera filtraciones con respecto a múltiples parámetros, como la escala y la densidad. ^[18]

Con ese fin, se han desarrollado varias extensiones multiparamétricas de la filtración Vietoris-Rips.

• La bifiltración Degree-Rips extiende la filtración Vietoris–Rips mediante la construcción de un subgrafo del 1-esqueleto de cada complejo en la filtración Vietoris–Rips, restringiendo solo a los vértices cuyo grado es al menos un parámetro dado , luego construyendo el complejo clique en ese subgrafo. El grado de un vértice codifica información de densidad sobre los datos, porque cuantifica qué tan "central" es ese punto por medio de cuántos otros vértices está conectado. La colección sobre todos los parámetros de grado define una filtración de cada complejo en la filtración Vietoris–Rips, donde los complejos se hacen más pequeños a medida que aumenta. En conjunto, esto define una extensión de 2 parámetros de la filtración Vietoris–Rips, al considerar la colección de complejos bifiltrados sobre todos los parámetros de escala , donde "op" denota el poset opuesto . ^[19] ${\displaystyle a\in [0,\infty )}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle (a,r)\in \mathbb {R} ^{\operatorname {op} }\times \mathbb {R} }$
• La bifiltración Function-Rips extiende la filtración Vietoris-Rips al bifiltrar cada complejo según los conjuntos de superniveles de alguna función , donde puede ser una función de densidad, una función de excentricidad o cualquier otra función. Es decir, cada complejo se define mediante , lo que produce una bifiltración indexada sobre . ^[20] ${\displaystyle \gamma :X\to \mathbb {R} }$ ${\displaystyle \gamma }$ ${\displaystyle \mathbf {F} {\text{-}}\mathbf {VR} _{a,r}(\gamma )=\mathbf {VR} _{r}(\gamma ^{-1}[a,\infty ))}$ ${\displaystyle \mathbb {R} ^{\operatorname {op} }\times [0,\infty )}$
• La bifiltración por subdivisión-Rips extiende la filtración de Vietoris-Rips tomando la subdivisión baricéntrica de cada complejo en la filtración de Vietoris-Rips y luego filtrando estos complejos por dimensión de cada bandera. Es decir, la subdivisión baricéntrica de un complejo simplicial es el complejo simplicial abstracto definido usando banderas de símplices en el complejo subyacente, donde una bandera (a veces llamada cadena ) es una serie anidada de símplices . Luego, dada la subdivisión baricéntrica de un complejo, se puede filtrar tomando el subcomplejo abarcado por vértices correspondientes a símplices en el complejo original de alguna dimensión mínima . La colección de todos esos complejos produce una bifiltración indexada sobre . ^[21] ${\displaystyle \sigma _{0}\subset \cdots \subset \sigma _{m}}$ ${\displaystyle k}$ ${\displaystyle [0,\infty )^{\operatorname {op} }\times [0,\infty )}$

Referencias

1. Chazal, Frédéric; Oudot, Steve Y. (2013). "Filtraciones intercaladas: teoría y aplicaciones en el análisis de datos de nubes de puntos". En Nielsen, Frank; Barbaresco, Frédéric (eds.). Ciencia geométrica de la información. Vol. 8085. Berlín, Heidelberg: Springer Berlin Heidelberg. págs. 587–592. doi :10.1007/978-3-642-40020-9_65. ISBN 978-3-642-40019-3. S2CID  8701910 . Consultado el 5 de abril de 2023 .
2. 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.
3. Oudot, Steve Y.; Sheehy, Donald R. (17 de junio de 2013). "Zigzag zoology". Actas del vigésimo noveno simposio anual sobre geometría computacional . SoCG '13. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 387–396. doi :10.1145/2462356.2462371. ISBN 978-1-4503-2031-3.S2CID 485245  .
4. Lee, Hyekyoung; Chung, Moo K.; Kang, Hyejin; Kim, Bung-Nyun; Lee, Dong Soo (2011). "Homología persistente discriminativa de redes cerebrales". Simposio internacional IEEE de 2011 sobre imágenes biomédicas: de nano a macro . págs. 841–844. doi :10.1109/ISBI.2011.5872535. ISBN . 978-1-4244-4127-3. Número de identificación S2CID  12511452.
5. Vietoris, L. (1 de diciembre de 1927). "Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen". Mathematische Annalen (en alemán). 97 (1): 454–472. doi :10.1007/BF01447877. ISSN  1432-1807. S2CID  121172198.
6. Gromov, M. (1987). "Grupos hiperbólicos". En Gersten, SM (ed.). Ensayos sobre teoría de grupos. Publicaciones del Instituto de Investigación de Ciencias Matemáticas. Vol. 8. Nueva York, NY: Springer New York. págs. 75–263. doi :10.1007/978-1-4613-9586-7_3. ISBN 978-1-4613-9588-1. Consultado el 5 de abril de 2023 .
7. Reitberger, Heinrich (2002), "Leopold Vietoris (1891–2002)", Avisos de la Sociedad Matemática Americana, 49 (20).
8. Bauer, Ulrich; Rollo, Fabián (2022). "Hiperbolicidad de Gromov, defecto geodésico y pares aparentes en filtraciones de Vietoris-Rips". En Goaoc, Xavier; Kerber, Michael (eds.). 38º Simposio Internacional sobre Geometría Computacional (SoCG 2022). Procedimientos internacionales de informática de Leibniz (LIPIcs). vol. 224. Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. págs. 15:1–15:15. doi : 10.4230/LIPIcs.SoCG.2022.15 . ISBN 978-3-95977-227-3. Número de identificación del sujeto  245124031.
9. Lesnick, Michael (1 de abril de 2023). "Apuntes de clase para AMAT 840: Persistencia multiparamétrica" ​​(PDF) . Universidad de Albany, SUNY : 33.
10. Sheehy, Donald R. (17 de junio de 2012). "Aproximaciones de tamaño lineal a la filtración de Vietoris-Rips". Actas del vigésimo octavo simposio anual sobre geometría computacional . SoCG '12. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 239–248. arXiv : 1203.6786 . doi :10.1145/2261250.2261286. ISBN 978-1-4503-1299-8. Número de identificación del sujeto  2392303.
11. Chambers, Erin W. ; de Silva, Vin; Erickson, Jeff; Ghrist, Robert (2010). "Complejos Vietoris–Rips de conjuntos de puntos planos". Geometría discreta y computacional . 44 (1): 75–90. doi : 10.1007/s00454-009-9209-8 . ISSN  0179-5376. S2CID  7900163.
12. Edelsbrunner, Herbert (2010). Topología computacional: una introducción. J. Harer. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4925-5.OCLC 427757156  .
13. Har-Peled, Sariel; Mendel, Manor (2006). "Construcción rápida de redes en métricas de baja dimensión y sus aplicaciones". Revista SIAM de Computación . 35 (5): 1148–1184. doi :10.1137/S0097539704446281. ISSN  0097-5397. S2CID  37346335.
14. 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.
15. Sheehy, Donald R. (3 de diciembre de 2020). "Una filtración de Delaunay dispersa". arXiv : 2012.01947 [cs.CG].
16. Choudhary, Aruni; Kerber, Michael; Raghvendra, Sharath (1 de septiembre de 2021). "Filtraciones de rips aproximadas mejoradas con redes enteras desplazadas y complejos cúbicos". Revista de topología aplicada y computacional . 5 (3): 425–458. doi :10.1007/s41468-021-00072-4. ISSN  2367-1734. PMC 8549989 . PMID  34722862. 
17. Vishwanath, Siddharth; Sriperumbudur, Bharath K.; Fukumizu, Kenji; Kuriki, Satoshi (3 de junio de 2022). "Inferencia topológica robusta en presencia de valores atípicos". arXiv : 2206.01795 [math.ST].
18. Carlsson, Gunnar; Zomorodian, Afra (2009). "La teoría de la persistencia multidimensional". Geometría discreta y computacional . 42 (1): 71–93. doi : 10.1007/s00454-009-9176-0 . ISSN  0179-5376.
19. Lesnick, Michael; Wright, Matthew (1 de diciembre de 2015). "Visualización interactiva de módulos de persistencia 2-D". arXiv : 1512.00180 [math.AT].
20. Botnan, Magnus Bakke; Lesnick, Michael (13 de marzo de 2023). "Una introducción a la persistencia multiparamétrica". arXiv : 2203.14289 [matemáticas.AT].
21. DR Sheehy, “Un nervio multicobertura para la inferencia geométrica”, en CCCG: Conferencia canadiense en geometría computacional , 2012.