Random geometric graphs and data structures: discrete estimations of the continuous

Abstract

In recent years, there have been significant efforts to develop rigourous geometric and topological methodologies to better understand data sets, with the view of performing machine learning tasks such as spectral clustering, non-linear dimensionality reduction and Topological Data Analysis. These methodologies have various objectives, use different techniques and are fundamentally different. For instance, the techniques used to tackle the consistency of spectral clustering or Cheeger consistency which are also discussed in this thesis, follow the so-called variational approach (proposed by Trillos and Slepcev in a series of works, initiated in [63]). On the other hand, techniques used to investigate topological features of random geometric complexes usually require knowledge of different fields such as Morse theory. While these methodologies are fundamentally different, they may be related through the concept of random geometric graphs. On the one hand, problems such as spectral clustering and Cheeger consistency can be seen as optimisation problems on functionals defined on random geometric graphs. On the other hand, random geometric complexes can be thought as generalisations of random geometric graphs, where we not only take into consideration vertices and edges, but also higher order simplices. Another common point is that all these methodologies are attempts to capture various geometric invariants of a manifold from an underlying sampled set of i.i.d. points (e.g., Betti numbers, Cheeger constants, spectrum of the Laplacian). While these methodologies have been applied successfully, there is still a lack of results providing theoretical guarantees and rigorously explaining the extent to which these various frameworks effectively work, under various settings. The aim of this thesis is to contribute to the development of such theoretical guarantees, building on existing results and methods.