Subdivisión de bifiltración

En el análisis de datos topológicos , una bifiltración de subdivisión es una colección de complejos simpliciales filtrados , típicamente construidos sobre un conjunto de puntos de datos en un espacio métrico , que captura información de forma y densidad sobre el conjunto de datos subyacente. La bifiltración de subdivisión se basa en una filtración natural de la subdivisión baricéntrica de un complejo simplicial por banderas de dimensión mínima, que codifica información de densidad sobre el espacio métrico sobre el que se construye el complejo. La bifiltración de subdivisión fue introducida por primera vez por Donald Sheehy en 2011 como parte de su tesis doctoral ^[1] (posteriormente subsumida por un artículo de conferencia en 2012 ^[2] ) como un modelo discreto de la bifiltración multicubierta , una construcción continua cuyo marco subyacente se remonta a la década de 1970. ^[3] En particular, Sheehy aplicó la construcción a las filtraciones de Vietoris-Rips y Čech , dos objetos comunes en el campo del análisis de datos topológicos. ^[4]^[5]^[6] Mientras que las filtraciones de un solo parámetro no son robustas con respecto a los valores atípicos en los datos, ^[7] las bifiltraciones de subdivisión Rips y Cech satisfacen varias propiedades de estabilidad deseables. ^[8]

Definición

Sea un complejo simplicial . Entonces una secuencia anidada de símplices de se llama bandera o cadena de . El conjunto de todas las banderas de comprende un complejo simplicial abstracto , conocido como la subdivisión baricéntrica de , denotada por . La subdivisión baricéntrica se identifica naturalmente con una subdivisión geométrica de , creada al colocar una estrella en la realización geométrica de en el baricentro de cada símplex. ^[9] ${\estilo de visualización T}$ $\sigma _{1}\subconjunto \sigma _{2}\subconjunto \cdots \subconjunto \sigma _{k}$ ${\estilo de visualización T}$ ${\estilo de visualización T}$ ${\estilo de visualización T}$ ${\estilo de visualización T}$ $\operatorname {Bary} (T)$ ${\estilo de visualización T}$ ${\estilo de visualización T}$

Existe una filtración natural en al considerar para cada número natural el subcomplejo máximo de abarcado por vértices de correspondientes a símplices de de dimensión al menos , que se denota . En particular, por esta convención, entonces . Considerando la secuencia de subcomplejos anidados dada al variar el parámetro , obtenemos una filtración en conocida como filtración de subdivisión. Dado que los complejos en la filtración de subdivisión se contraen a medida que aumenta, podemos considerarlo como un funtor de la categoría posetal opuesta a la categoría de complejos simpliciales y morfismos simpliciales . $\operatorname {Bary} (T)$ ${\estilo de visualización k}$ $\operatorname {Bary} (T)$ $\operatorname {Bary} (T)$ ${\estilo de visualización T}$ ${\estilo de visualización k-1}$ ${\tilde {\mathcal {S}}}(T)_{k}$ ${\tilde {\mathcal {S}}}(T)_{1}=\operatorname {Bary} (T)$ ${\estilo de visualización k}$ $\operatorname {Bary} (T)$ ${\estilo de visualización k}$ ${\tilde {\mathcal {S}}}(-):\mathbb {N} ^{\operatorname {op} }\to \mathbf {Simp}$ $\mathbb {N} ^{\operatorname {op} }$ $\mathbf {Simp}$

Sea un conjunto parcialmente ordenado . Dada una filtración simplicial , considerada como un funtor de la categoría posetal de a la categoría , al aplicar la filtración por subdivisión objeto a objeto en , obtenemos una filtración de dos parámetros , llamada bifiltración por subdivisión. ^[10] ${\estilo de visualización P}$ $F:P\to \mathbf {Simp}$ ${\estilo de visualización P}$ $\mathbf {Simp}$ ${\estilo de visualización F}$ ${\mathcal {S}}(F):\mathbb {N} ^{\operatorname {op} }\times P\to \mathbf {Simp}$

En particular, cuando tomamos como filtración Rips o Čech , obtenemos bifiltraciones y , respectivamente. ${\estilo de visualización F}$ ${\mathcal {S}}\operatorname {Rips} (-)$ ${\mathcal {S}}\operatorname {{\check {C}}ech} (-)$

Propiedades

La bifiltración de subdivisión-Čech es débilmente equivalente a la bifiltración multicapa, lo que implica que tienen homología persistente isomórfica. Una prueba combinatoria de esta afirmación se dio en el artículo de conferencia original de Sheehy, pero Cavanna et al. presentaron una versión más algebraica en 2017. ^[11] Las ideas de la prueba de Cavanna fueron generalizadas posteriormente por Blumberg y Lesnick en un artículo de 2022 sobre homología persistente de 2 parámetros. ^[8]

Por tamaño de una bifiltración, nos referimos al número de símplices en el complejo más grande. La bifiltración de subdivisión-Čech tiene un tamaño exponencial en función del número de vértices. ^[12] Esto implica que su homología no se puede calcular directamente en tiempo polinomial . Sin embargo, para puntos en el espacio euclidiano, la homología de la subdivisión-Čech se puede calcular en tiempo polinomial, hasta la equivalencia débil , mediante una construcción conocida como bifiltración romboide . Como precursor de la bifiltración romboide, Edelsbrunner y Osang presentaron en 2021 un complejo de celdas poliédricas llamado teselación romboide , que utilizaron para calcular cortes horizontales o de vértices de la bifiltración multicubierta hasta la equivalencia débil. ^[13] Esto fue ampliado un año después por Corbet et al. a la bifiltración romboide, que es débilmente equivalente a la bifiltración multicubierta, pero tiene un tamaño polinomial. ^[12]

Referencias

^ Sheehy, DR (2011). Generación de mallas y homología geométrica persistente (tesis doctoral, Universidad Carnegie Mellon).
^ Sheehy, Donald R. 2012. “Un nervio multicobertura para la inferencia geométrica”. en CCCG: Conferencia canadiense en geometría computacional .
^ Fejes Tóth, G. (marzo de 1976). "Múltiples embalajes y coberturas del avión con círculos". Acta Mathematica Academiae Scientiarum Hungaricae . 27 (1–2): 135–140. doi :10.1007/BF01896768. ISSN 0001-5954. S2CID 189778121.
^ Chazal, Frédéric; Oudot, Steve Yann (2008). "Hacia la reconstrucción basada en la persistencia en espacios euclidianos". Actas del vigésimo cuarto simposio anual sobre geometría computacional . págs. 232–241. arXiv : 0712.2638 . doi :10.1145/1377676.1377719. ISBN. 9781605580715.S2CID1020710 .
^ Ghrist, Robert (2007). "Códigos de barras: la topología persistente de los datos". Boletín de la Sociedad Matemática Americana . 45 : 61–76. doi : 10.1090/s0273-0979-07-01191-3 .
^ Chazal, Federico; De Silva, Vin; Oudot, Steve (2014). "Estabilidad de persistencia para complejos geométricos". Geometriae Dedicata . 173 : 193–214. arXiv : 1207.3885 . doi :10.1007/s10711-013-9937-z. S2CID 254508455.
^ Chazal, Frédéric; Cohen-Steiner, David; Mérigot, Quentin (diciembre de 2011). "Inferencia geométrica para medidas de probabilidad". Fundamentos de las matemáticas computacionales . 11 (6): 733–751. doi :10.1007/s10208-011-9098-0. ISSN 1615-3375. S2CID 15371638.
^ ab Blumberg, Andrew J.; Lesnick, Michael (17 de octubre de 2022). "Estabilidad de la homología persistente de 2 parámetros". Fundamentos de las matemáticas computacionales . arXiv : 2010.09628 . doi :10.1007/s10208-022-09576-6. ISSN 1615-3375. S2CID 224705357.
^ Rourke, CP (1982). Introducción a la topología lineal por partes. BJ Sanderson. Berlín: Springer-Verlag. ISBN 0-387-11102-6.OCLC 7948164 .
^ Lesnick, Michael (11 de marzo de 2023). "Lecture notes for AMAT 840: Multiparameter Persistence" (PDF) . Consultado el 27 de marzo de 2023 .
^ Cavanna, Nicholas J.; Gardner, Kirk P.; Sheehy, Donald R. (2017). "Cuándo y por qué funciona el criterio de cobertura topológica". Actas del vigésimo octavo simposio anual ACM-SIAM sobre algoritmos discretos . págs. 2679–2690. doi :10.1137/1.9781611974782.177. ISBN 978-1-61197-478-2.
^ ab Corbet, René; Kerber, Michael; Lesnick, Michael; Osang, Georg (20 de febrero de 2023). "Computación de la bifiltración multicubierta". Geometría discreta y computacional . 70 (2): 376–405. arXiv : 2103.07823 . doi :10.1007/s00454-022-00476-8. ISSN 0179-5376. PMC 10423148 . PMID 37581017.
^ Edelsbrunner, Herbert; Osang, Georg (2021). "La persistencia de múltiples capas de bolas euclidianas". Geometría discreta y computacional . 65 (4): 1296–1313. doi :10.1007/s00454-021-00281-9. ISSN 0179-5376. PMC 8550220 . PMID 34720303.