Random geometric graphs and data structures: discrete estimations of the continuous
View/ Open
Date
06/07/2020Author
de Kergorlay, Henry-Louis Melchior
Metadata
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.