Topological and geometrical methods in data analysis

Abstract

Den här avhandling rör två relaterade data-analys flöden, som använder topologiska respektive geometriska metoder, för att extrahera relevant information. Det första flödet, kallat topological data analysis (TDA) pipeline, konstruerar ett så kallat “filtrerat simpliciellt komplex” på en given datamängd i syfte att beskriva formen på datamängden. Formen beskrivs genom en så kallad persistensmodul, som karaktäriserar de topologiska egenskaperna hos filtreringen, och det slutgiltiga steget i flödet är att extrahera algebraiska invarianter från detta objekt. Det andra flödet, kallat geometric data analysis (GDA) pipeline, associerar en algebraisk varieté till en given datamängd och syftar till att beskriva dess struktur. Strukturen beskrivs med hjälp av homologi, en invariant som för de flesta algebraiska varieteter bara kan beräknas numeriskt med hjälp av testmetoder. 

I Paper A studerar vi invarianter för persistensmoduler med flera parametrar. Vi förklarar vi hur man konverterar diskreta invarianter till stabila via det vi kallar hierarkisk stabilisering. Vi illustrerar denna process genom att konstruera stabila invarianter för persistensmoduler med flera parametrar med avseende på interleaving-metriken och så kallade simple noise systems. För endast en parameter återfår vi barcode-invarianten. För mer än en parameter bevisar vi att de konstruerade invarianterna i allmänhet är NP-svåra att beräkna. En konsekvens är att beräkning av feature counting-funktionen, föreslagen av Scolamiero et. al. (2016), är NP-svår. 

I Paper B introducerar vi en effektiv algoritm för att beräkna en minimal presentation av en multi-parameter persistensmodul, givet ett kedjekomplex av fria moduler som input. Vårt tillvägagångssätt bygger på tidigare arbete med detta problem i fallet med två parametrar och bygger på idéer som ligger till grund för F4 och F5-algoritmerna för att beräkna Gröbner baser. I r-parameter fallet beräknar vi en presentation av homologin för CF−→ AG−→ B med moduler av respektive rang l, n och m med O(r2 nr+1 + nr m + nr−1 m2 + r n2l) aritmetiska operationer. Vi har implementerat vår algoritm i den nya mjukvaran Muphasa, skriven i C++. I preliminära experiment på syntetiska TDA-exempel jämför vi vår strategi med en version av en klassisk algoritm baserat på Schreyer’s algoritm med resultatet att vår algoritm är väsentligt snabbare och mer minneseffektiv. Under utvecklingen av vår algoritm för minimala presentationer så introducerar vi också algoritmer för närbesläktade problem för att beräkna en Gröbner-bas för bilden och kärnan till morfismen G. Vår algoritm i det fallet har tidskomplexiteten O(nr m +nr−1 m2) och minneskomplexitet O(n2 + m n +n r + K),där K är storleken på resultatet. 

Paper C analyserar komplexiteten av att anpassa en algebraisk varietet, som kommer från en klass av varieteter, till en konfiguration av punkter i RN. Komplexitetsmåttet, kallat algebraisk komplexitet, beräknar den Euklidiska avståndsgraden (EDD) för en viss varietet som kallas hypotesvarieteten när antalet punkter i konfigurationen ökar. Slutligen visar vi en koppling till komplexiteten av arkitekturer i polynomiella neurala nätverk. För problemet med att anpassa en (N −1)-sfär till en konfiguration av m punkter i RN, ger vi en sluten formel för hypotesvarietetens algebraiska komplexitet när m växer för fallet N = 1. För fallet N > 1 formulerar vi en förmodan som generaliserar denna formel med stöd av numeriska experiment. 

I Paper D presenterar vi en effektiv algoritm för att producera en bevisligt tät delmängd av en slät och kompakt algebraisk varieté. Algoritmen är delvis baserat på beräkningen av flaskhalsar av varieteten. Med hjälp av geometrisk information så som flaskhalsar och lokal räckvidd ger vi också övre gränser för densiteten som krävs för delmängden för att garantera att varietetens homologi kan återvinnas. En implementation av algoritmen tillhandahålls tillsammans med numeriska experiment och en jämförelse med algoritmen av Dufresne et. al. (2019).

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-294303