1,721,004 research outputs found
Discrete Morse theory for Filtrations
No full textThe central result of this dissertation is an extension of discrete Morse theory to filtered cell complexes. Discrete Morse theory imposes a pairing on some cells of a complex X and uses that pairing to introduce a new complex M – called the Morse complex – consisting of the unpaired cells of X along with a boundary operator constructed from the incidence relations of the paired cells. It turns out that the homology groups of X and M are isomorphic. Now assume that the complex X admits a filtration by sub-complexes {X k}K 1 as follows X 1 ⊂ X 2 ⊂... ⊂ XK = X. Our theory constructs a pairing subordinate to this filtration, and hence produces a Morse complex M which is also filtered by subcomplexes {Mk}K 1 so that not only are each X k and Mk homologically isomorphic, but the map induced o
Approximation methods in geometry and topology: learning, coarsening, and sampling
Get PDFData materialize in many different forms and formats. These can be continuous or
discrete, from algebraic expressions to unstructured pointclouds and highly structured graphs and simplicial complexes. Their sheer volume and plethora of different
modalities used to manipulate and understand them highlight the need for expressive abstractions and approximations, enabling novel insights and efficiency.
Geometry and topology provide powerful and intuitive frameworks for modelling
structure, form, and connectivity. Acting as a multi-focal lens, they enable inspection
and manipulation at different levels of detail, from global discriminant features to
local intricate characteristics. However, these fundamentally algebraic theories do
not scale well in the digital world.
Adjusting topology and geometry to the computational setting is a non-trivial task,
adhering to the “no free lunch” adage. The necessary discretizations can be inaccurate, the underlying combinatorial structures can grow unmanageably in size, and
computing salient topological and geometric features can become computationally
taxing. Approximations are a necessity when theory cannot accommodate for efficient algorithms.
This thesis explores different approaches to simplifying computations pertaining to
geometry and topology via approximations. Our methods contribute to the approximation of topological features on discrete domains, and employ geometry and topology to efficiently guide discretizations and approximations. This line of work fits un der the umbrella of Topological Data Analysis (TDA) and Discrete Geometry, which
aim to bridge the continuous algebraic mindset with the discrete.
We construct topological and geometric approximation methods operating on three
different levels. We approximate topological features on discrete combinatorial spaces;
we approximate the combinatorial spaces themselves; and we guide processes that
allow us to discretize domains via sampling. With our Dist2Cycle model we learn geometric manifestations of topological features, the “optimal” homology generating
cycles. This is achieved by a novel simplicial complex neural network that exploits
the kernel of Hodge Laplacian operators to localize concise homology generators.
Compression of meshes and arbitrary simplicial complexes is made possible by our
general spectral coarsening strategy. Functional and structural properties are preserved by optimizing for important eigenspaces of general differential operators, the
Hodge Laplacians, at multiple dimensions. Finally, we offer a geometry-driven sampling strategy for data accumulation and stochastic integration. By employing the
kd-tree geometric partitioning algorithm we construct a sample set with provable
equidistribution guarantees.
Our findings are contextualized within prior and recent work, and our methods are
thoroughly discussed and evaluated on diverse settings. Ultimately, we are making
a claim towards the usefulness of examining the ever-present topological and geometric properties of data, not only in terms of feature discovery, but also as informed
generation, manipulation, and simplification tools
Harder-Narasimhan filtrations of persistence modules
Get PDFMultiparameter persistence modules are central objects in Topological Data Analysis. Unlike ordinary persistence modules, they do not admit a complete discrete invariant such as the barcode. This thesis explores the use of Harder-Narasimhan theory as a way to devise discrete invariants of multiparameter persistence modules that are discriminating, computable, stable and interpretable.Harder-Narasimhan types are a family of discrete invariants of persistence modules over finite posets. We first study their discriminating power in several settings arising in Topological Data Analysis. We then use Harder-Narasimhan types to define the skyscraper invariant, a novel discrete invariant of multiparameter persistence modules. We show that this invariant is strictly more discriminating than the rank invariant and is stable with respect to the interleaving distance
Topics in multidimensional persistence
Get PDFA multiparameter persistence module is a representation of the lattice quiver Nd, where maps along all squares commute. When d = 1, Gabriel’s theorem applies and these modules admit interval decompositions, allowing us to classify one dimen- sional persistence modules through their associated barcode, a combinatorial invariant first introduced in by Carlsson and Zomorodian. When d > 1, no such classification is possible. In this thesis we study these higher dimensional persistence modules, seeking to over- come their lack of simple classification by defining discrete invariants with as much discriminative power as possible. The thesis is composed of three parts.
First, we give an in depth analysis of barcode bases. These are bases of one-dimensional persistence modules that realise the interval decom- position given by Gabriel’s theorem. We present a novel algorithm that computes these barcode bases, and give theoretical results that characterise the set of barcode bases of a given persistence module. This allows for a decomposition results of certain types of ladder persistence modules. We generalise all these results to zigzag persistence.
Second, we consider Harder-Narasimhan filtrations for quiver representations and define the skyscraper invariant, a novel discrete invariant for multidimensional persistence which is finer than the rank invariant. We further show the skyscraper invariant can be refined to create a complete invariant on certain families of ladder persistence modules.
Finally, we discuss computation methods for the skyscraper invariant. We exhibit an algorithm that computes the skyscraper invariant for ladder persistence modules. This is done by leveraging the decomposition result for ladder persistence modules from the first chapter. In doing so, we introduce the ladder invariant, which is computable and more discriminative than the rank invariant. It coincides with the skyscraper invariant on ladder persistence modules and is non-comparable to the skyscraper invariant in general.
Algorithms from the first chapter are given as pseudo-code. These were later implemented as a python package and we give an overview of this package in the appendix
Random simplicial complexes and Stein’s method
Get PDFThe work presented in this thesis is largely motivated by the pressing need for statistical foundations in topological data analysis (TDA). By studying random simplicial complexes, which serve as null models in TDA, the thesis falls within the framework of stochastic topology. Despite various success stories involving applications of algebraic topology, there is a lack of statistical tools that allow to rigorously evaluate topological data under uncertainty. Here we use Stein’s method for multivariate normal distributions to prove distributional approximation results for random variables that arise in the study of random simplicial complexes. We also apply the results to statistical inference and hypothesis testing using simplicial complex data. The main body of the work consists of two articles: one accepted journal publication, and one preprint, which has been submitted for publication.
The first main result of the thesis is an abstract multivariate central limit theorem with explicit bounds, established via Stein’s method, for sums of locally dependent random variables, which pro- vides the greatest generality for this type of dependence structure so far. The result is then applied to prove multivariate central limit theorems for variables that arise in the study of the clique complexes of Erd ̋os–R ́enyi random graphs. The abstract central limit theorem applies to multivariate sums of random variables which contain different order of summands in each component, allowing it to be applied in the context of the random clique complexes.
The subsequent chapter extends and generalises the probabilistic results of the previous chapter and applies them to statistical inference and hypothesis testing. Here we work with a more general random simplicial complex model: the multi-parameter random complex X(n, p). The statistical applications include properties of the maximum likelihood estimator of X(n, p) given a single observed simplicial complex as well as using the central limit theorems to devise goodness-of-fit tests.
This thesis not only contributes to the Stein’s method literature but also offers better under- standing of multivariate statistics of random simplicial complexes from a probabilistic point of view as well as shows how such probabilistic understanding leads to useful statistical tools in practice
Numerical algorithms for the mathematics of information
Get PDFThis 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.</p
Local inference of Morse indices using finite point samples
Get PDFWe consider a smooth function f : M → R on a Riemannian submanifold M embedded in an ambient Euclidean space Rd. We provide theoretical guarantees for inferring the Morse index of a compact, dynamically isolated critical set of f using a pair of finite point clouds X and X− in Rd, and detail sufficient conditions which X and X− have to satisfy. We also outline a realisable computational procedure for obtaining X and X− and inferring the Morse index.
In a separate study with Jacob Leygonie, we discuss how persistent homology and wavelet signatures can be applied to graph classification problems in machine learning. We construct a supervised learning model which backpropagates through persistent homology to optimise over the space of wavelet signatures. We then apply this model to several benchmark graph classification problems and obtain accuracies in line with state of the art models.
The final portion of this thesis investigates how maximum diversity, a notion of effective cardinality in geometric measure theory, can be applied to industrial applications of interest to Elsevier, who sponsor this DPhil. In particular, we apply maximum diversity to assess the multi-disciplinarity of a collection of EPSRC grants, which takes relations between topics and grants into account. We also derive a generalised notion of Jaccard similarity such that we can measure the topical similarity between two grants, leveraging the pairwise similarities between their associated topics. We give recommendations on further industrial applications of maximum diversity in Elsevier’s business
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
