This thesis presents a series of algorithmic innovations in Combinatorial Compressed Sensing and Persistent Homology. The unifying strategy across these contributions is in translating structural patterns in the underlying data into specific algorithmic designs in order to achieve: better guarantees in computational complexity, the ability to operate on more complex data, highly efficient parallelisations, or any combination of these.

Dans cette thèse, on s'intéresse à des algorithmes d'analyse de données utilisant des marches aléatoires sur des graphes de voisinage, ou graphes géométriques aléatoires, construits à partir des données. On sait que les marches aléatoires sur ces graphes sont des approximations d'objets continus appelés processus de diffusion. Dans un premier temps, nous utilisons ce résultat pour proposer un nouvel algorithme de partitionnement de données flou de type recherche de modes. Dans cet algorithme, on définit les paquets en utilisant les propriétés d'un certain processus de diffusion que l'on approche par une marche aléatoire sur un graphe de voisinage. Après avoir prouvé la convergence de notre algorithme, nous étudions ses performances empiriques sur plusieurs jeux de données. Nous nous intéressons ensuite à la convergence des mesures stationnaires des marches aléatoires sur des graphes géométriques aléatoires vers la mesure stationnaire du processus de diffusion limite. En utilisant une approche basée sur la méthode de Stein, nous arrivons à quantifier cette convergence. Notre résultat s'applique en fait dans un cadre plus général que les marches aléatoires sur les graphes de voisinage et nous l'utilisons pour prouver d'autres résultats : par exemple, nous arrivons à obtenir des vitesses de convergence pour le théorème central limite. Dans la dernière partie de cette thèse, nous utilisons un concept de topologie algébrique appelé homologie persistante afin d'améliorer l'étape de "pooling" dans l'approche "sac-de-mots" pour la reconnaissance de formes 3D. / In this thesis, we study data analysis algorithms using random walks on neighborhood graphs, or random geometric graphs. It is known random walks on such graphs approximate continuous objects called diffusion processes. In the first part of this thesis, we use this approximation result to propose a new soft clustering algorithm based on the mode seeking framework. For our algorithm, we want to define clusters using the properties of a diffusion process. Since we do not have access to this continuous process, our algorithm uses a random walk on a random geometric graph instead. After proving the consistency of our algorithm, we evaluate its efficiency on both real and synthetic data. We then deal tackle the issue of the convergence of invariant measures of random walks on random geometric graphs. As these random walks converge to a diffusion process, we can expect their invariant measures to converge to the invariant measure of this diffusion process. Using an approach based on Stein's method, we manage to obtain quantitfy this convergence. Moreover, the method we use is more general and can be used to obtain other results such as convergence rates for the Central Limit Theorem. In the last part of this thesis, we use the concept of persistent homology, a concept of algebraic topology, to improve the pooling step of the bag-of-words approach for 3D shapes.

The theory of multidimensional persistence was introduced in a paper by G. Carlsson and A. Zomorodian as an extension to persistent homology. The central object in multidimensional persistence is the persistence module, which represents the homology of a multi filtered space. In this thesis, a novel algorithm for computing the persistence module is described in the case where the homology is computed with coefficients in a field. An algorithm for computing the feature counting invariant, introduced by Chachólski et al., is investigated. It is shown that its computation is in general NP-hard, but some special cases for which it can be computed efficiently are presented. In addition, a generalization of the barcode for persistent homology is defined and conditions for when it can be constructed uniquely are studied. Finally, a new topology is investigated, defined for fields of characteristic zero which, via the feature counting invariant, leads to a unique denoising of a tame and compact functor. / Teorin om multidimensionell persistens introduserades i en artikel av G. Carlsson och A. Zomorodian som en generalisering av persistent homologi. Det centrala objektet i multidimensionell persistens är persistensmodulen, som representerar homologin av ett multifilterat rum. I denna uppsats beskrivs en ny algoritm för beräkning av persistensmodulen i fallet där homologin beräknas med koefficienter i en kropp. En algoritm för beräkning av karaktäristik-räknings-invarianten, som introducerade av Chachólski et al., utforskas och det visar sig att dess beräkning i allmänhet är NP-svår. Några specialfall för vilka den kan beräknas effektivt presenteras. Vidare definieras en generalisering av stäckkoden för persistent homologi och kraven för när den kan konstrueras unikt studeras. Slutligen undersöks en ny topologi, definierad för kroppar av karaktäristik noll, som via karaktäristik-räknings-invarianten leder till en unik avbränning.

No description available.

Mudanças de padrão são variações nos dados da série temporal. Tais mudanças podem representar transições que ocorrem entre estados. A análise de dados topológicos (TDA) permite uma caracterização de dados de séries temporais obtidos a partir de sistemas dinâmicos complexos. Neste trabalho, apresentamos uma técnica de detecção de mudança de padrão baseada em TDA. Especificamente, a partir de uma determinada série temporal, dividimos o sinal em janelas deslizantes sem sobreposição e para cada janela calculamos a homologia persistente, ou seja, o barcode associado. A partir desse barcode, o intervalo médio e a entropia persistente são calculados e plotados em relação à duração do sinal. Resultados experimentais em conjuntos de dados reais e artificiais mostram bons resultados do método proposto: 1) Detecta mudança de padrões identificando a mudança no intervalo médio e calculando a entropia persistente para os barcodes gerados pelo conjunto de dados de entrada. 2) Mostra qualitativamente quão sensível é a escolha do método de filtragem para evidenciar características topológicas do espaço original sob exame. Isto é conseguido usando duas filtragens: uma filtragem métrica e uma do tipo lower-star. 3) Variando o tamanho da janela, o método pode caracterizar a presença de estruturas locais do conjunto de dados, como o período de convulsão nos sinais EEG. 4) O método proposto é capaz de caracterizar a complexidade pela medida de entropia persistente dos barcodes, uma medida de entropia baseada na definição de entropia de Shannon. Além disso, neste trabalho, mostramos a evidência de mudanças de complexidade associadas a um período de convulsão de um sinal de EEG / Pattern changings are variations in time series data. Such changes may represent transitions that occur between states. Topological data analysis (TDA) allows characterization of time-series data obtained from complex dynamical systems. In this work, we present a pattern changing detection technique based on TDA. Specifically, starting from a given time series, we divide the signal in slicing windows with no overlapping and for each window we calculate the persistent homology, i.e., the associated barcode. From the barcode the average interval size and persistent entropy are calculated and plotted against the signal duration. Experimental results on artificial and real data sets show good results of the proposed method: 1) It detects pattern changing by identifying the change in the average interval size and calculated persistent entropy for the barcodes generated by the input data set. 2) It shows qualitatively how sensible the choice of filtration method is to evidence topological features of the original space under examination. This is accomplished by using two filtrations: a metric and a lower-star filtration. 3) By varying the slice window size, the method can characterize the presence of local structures of the data set such as the seizure period in EEG signals. 4) The proposed method can characterize complexity by the measure persistent entropy for barcodes, an entropy measure based on Shannon´s entropy definition. Moreover, in this work, we show the evidence of complexity changes associated with a seizure period of an EEG signal

Recently computational topology had an important development in data analysis giving birth to the field of Topological Data Analysis. Persistent homology appears as a fundamental tool based on the topology of data that can be represented as points in metric space. In this work, we apply techniques of Topological Data Analysis, more precisely, we use persistent homology to calculate topological features more persistent in data. In this sense, the persistence diagrams are processed as feature vectors for applying Machine Learning algorithms. In order to classification, we used the following classifiers: Partial Least Squares-Discriminant Analysis, Support Vector Machine, and Naive Bayes. For regression, we used Support Vector Regression and KNeighbors. Finally, we will give a certain statistical approach to analyze the accuracy of each classifier and regressor. / Recentemente a topologia computacional teve um importante desenvolvimento na análise de dados dando origem ao campo da Análise Topológica de Dados. A homologia persistente aparece como uma ferramenta fundamental baseada na topologia de dados que possam ser representados como pontos num espaço métrico. Neste trabalho, aplicamos técnicas da Análise Topológica de Dados, mais precisamente, usamos homologia persistente para calcular características topológicas mais persistentes em dados. Nesse sentido, os diagramas de persistencia são processados como vetores de características para posteriormente aplicar algoritmos de Aprendizado de Máquina. Para classificação, foram utilizados os seguintes classificadores: Análise de Discriminantes de Minimos Quadrados Parciais, Máquina de Vetores de Suporte, e Naive Bayes. Para a regressão, usamos a Regressão de Vetores de Suporte e KNeighbors. Finalmente, daremos uma certa abordagem estatística para analisar a precisão de cada classificador e regressor.

No description available.

Parkinson’s Disease (PD) is the fastest growing neurodegenerative disease, currently affecting two to three percent of the population over 65. Studying functional connectivity (FC) in PD patients may provide new insights into how the disease alters brain organization in different subjects. We explored persistent homology (PH) as a method for studying FC based on the functional magnetic resonance imaging (fMRI) recordings of 63 subjects, of which 56 were diagnosed with PD.  We used PH to translate each set of fMRI recordings into a stable rank. Stable ranks are homological invariants that are amenable for statistical analysis. The pipeline has multiple parameters, and we explored the effect of these parameters on the shape of the stable ranks. Moreover, we fitted functions to reduce the stable ranks to points in two or three dimensions. We clustered the stable ranks based on the fitted parameter values and based on the integral distance between them. For some of the parameter combinations, not all clusters were located in the space covered by controls. These clusters correspond to patients with a topologically distinct connectivity structure, which may be clinically relevant. However, we found no relation between the clusters and the medication status or cognitive ability of the patients. It should be noted that this study was an exploration of applying persistent homology to PD data, and that statistical testing was not performed. Consequently, the presented results should be considered with care. Furthermore, we did not explore the full parameter space, as time was limited and the data set was small. In a follow-up study, a measurable desired outcome of the pipeline should be defined and the data set should be expanded to allow for optimizing over the full parameter space. / Parkinsons sjukdom är den snabbast växande neurodegenerativa sjukdomen och drabbar för närvarande två till tre procent av befolkningen över 65 år. Att studera funktionell konnektivitet (FC) hos patienter med Parkinson kan ge nya insikter om hur sjukdomen förändrar hjärnans uppsättning i olika områden. Vi använde oss av persistent homologi (PH) som en metod för att studera FC baserat på inspelningar av funktionell magnetresonanstomografi (fMRI) av 63 försökspersoner varav 56 hade diagnosen PD. Vi använde oss av persistent homologi (PH) som en metod för att studera FC baserat på inspelningar av funktionell magnetresonanstomografi (fMRI) av 63 försökspersoner varav 56 hade diagnosen PD. Vi använde PH för att översätta varje uppsättning fMRI-prov vardera till en stable rank. Stable ranks är homologiska invarianter som är lämpliga för statistisk analys. Pipelinen har flera parametrar och vi undersökte effekten av dessa parametrar på formen av dessa stable ranks. Vi anpassade funktioner för att reducera alla stable ranks till punkter i två eller tre dimensioner. Vi grupperade alla stable ranks utifrån de anpassade parametervärdena och utifrån det integrala avståndet mellan dem. För vissa parameterkombinationer kunde inte alla kluster inom det område som täcks av kontrollerna bli funna. Dessa kluster motsvarar patienter med en topologiskt distinkt konnektivitetsstruktur, vilket kan vara kliniskt relevant. Vi fann dock inget samband mellan klustren och patienternas läkemedelsstatus eller kognitiva förmåga.  Det bör noteras att den här studien var en undersökning på tillämpningen av persistent homologi på PD-data och att statistiska tester inte utfördes. Följaktligen bör de presenterade resultaten betraktas med försiktighet. Dessutom undersökte vi inte hela parameterutrymmet eftersom tiden var begränsad och datamängden liten. I en uppföljningsstudie bör man definiera ett mätbart önskat resultat av pipelinen och datamängden bör utökas för att möjliggöra optimering av hela parameterutrymmet.

<p>The only datasets used in my thesis work are from TUDatasets, <a href="https://chrsmrrs.github.io/datasets/">TUDataset | TUD Benchmark datasets (chrsmrrs.github.io)</a>, a collection of public benchmark datasets for graph classification and regression.</p><p><br></p>

This thesis explores a new way to analyze spatiotemporal data. By combining topology, the path signature and machine learning a robust model to analyze swarming behavior over time is created. Using persistent homology a representation of spatial data is obtained and the path signature gives us a representation for how this changes over time. This representation allows us to compare samples even if they have different amounts of time steps and different length of the sequence. It is also resistant to noise in the spatial representation. Using this data is then used to train a gaussian process regressor to extract parameters that govern the movement of swarms. Our analysis shows that the tested method is a good candidate for analyzing spatiotemporal data and that it warrants further studies. / Detta examensarbete utforskar ett nytt sätt att analysera spatiotemporal data. Genom att kombinera topologi, vägsignaturer och maskininlärning skapas en robust modell för att analysera svärmar beter sig över tid. Genom persistent homology erhålls en representation av spatial data och dess vägsignatur ger oss en representation för hur detta förändras över tiden. Denna representation gör det möjligt för oss att jämföra data även om de har olika antal tidssteg och sekvenserna är olika långa. Den är också motståndskraftig mot brus i den spatiala representationen. Denna data används sedan för att träna en gaussisk process-regressor för att extrahera parametrar som styr svärmarnas rörelse. Vår analys visar att den testade metoden är en bra kandidat för att analysera spatiotemporal data och att den är värd att studera ytterligare.