Vietoris-Rips-filtreringen är ett mångsidigt verktyg inom topologisk dataanalys. Det är en sekvens av enkla komplex som bygger på ett metriska utrymme för att lägga topologisk struktur till en annars frånkopplad uppsättning punkter. Den används ofta eftersom den kodar användbar information om topologin för det underliggande metriska utrymmet. Denna information utvinns ofta ur dess så kallade persistensdiagram. Tyvärr är denna filtrering ofta för stor för att konstrueras i sin helhet. Vi visar hur man konstruerar en O(n)-storlek filtrerad simplial komplex på en n-punkt metriska utrymme så att dess persistensdiagram är en bra approximation till den av Vietoris-Rips filtrering. Denna nya filtrering kan konstrueras under O(n log n) tid. De konstanta faktorerna i både storlek och körtid beror endast på den dubbla dimensionen av det metriska utrymmet och den önskade tätheten av approximationen. För första gången gör detta det beräkningsbart att approximera persistensdiagrammet för Vietoris-Rips-filtreringen över alla skalor för stora datamängder. Vi beskriver två olika glesa filtreringar. Den första är en sicksackfiltrering som tar bort punkter när skalan ökar. Den andra är en (icke-zigzag) filtrering som ger samma persistensdiagram. Båda metoderna bygger på ett hierarkiskt nettoträd och ger samma garantier.
Don Sheehy REF approximerade nyligen den fullständiga filtreringen av Vietoris-Rips-komplex på n-punkter i ett metriska utrymme genom en filtrering som har en storlek O(n) och approximerar den ihållande homologin med ett multiplikativt fel nära 1.
Linear-size approximations to the vietoris-rips filtration
{'venue': "SoCG '12", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}