BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Michael Lesnick

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.ATComputational Geometrymath.ACMachine Learningmath.STPopulations and EvolutionQuantitative MethodsStatistics TheorySymbolic Computation

Catalog footprint

Research overview

10works
9topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

10 publications

preprint2022arXiv

Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology

Motivated by applications to topological data analysis, we give an efficient algorithm for computing a (minimal) presentation of a bigraded K[x,y]K[x,y]-module MM, where KK is a field. The algorithm takes as input a short chain complex of free modules X→fY→gZX\xrightarrow{f} Y \xrightarrow{g} Z such that M≅ker⁡g/imfM\cong \ker{g}/\mathrm{im}{f}. It runs in time O(∣X∣3+∣Y∣3+∣Z∣3)O(|X|^3+|Y|^3+|Z|^3) and requires O(∣X∣2+∣Y∣2+∣Z∣2)O(|X|^2+|Y|^2+|Z|^2) memory, where ∣⋅∣|\cdot | denotes the rank. Given the presentation computed by our algorithm, the bigraded Betti numbers of MM are readily computed. Our approach is based on a simple matrix reduction algorithm, slight variants of which compute kernels of morphisms between free modules, minimal generating sets, and Gröbner bases. Our algorithm for computing minimal presentations has been implemented in RIVET, a software tool for the visualization and analysis of two-parameter persistent homology. In experiments on topological data analysis problems, our implementation outperforms the standard computational commutative algebra packages Singular and Macaulay2 by a wide margin.

Open access
preprint2022arXiv

Computing the Multicover Bifiltration

Given a finite set A⊂RdA\subset\mathbb{R}^d, let Covr,k_{r,k} denote the set of all points within distance rr to at least kk points of AA. Allowing rr and kk to vary, we obtain a 2-parameter family of spaces that grow larger when rr increases or kk decreases, called the \emph{multicover bifiltration}. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a \v Cech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.

Open access
preprint2022arXiv

Stability of 2-Parameter Persistent Homology

The Čech and Rips constructions of persistent homology are stable with respect to perturbations of the input data. However, neither is robust to outliers, and both can be insensitive to topological structure of high-density regions of the data. A natural solution is to consider 2-parameter persistence. This paper studies the stability of 2-parameter persistent homology: We show that several related density-sensitive constructions of bifiltrations from data satisfy stability properties accommodating the addition and removal of outliers. Specifically, we consider the multicover bifiltration, Sheehy's subdivision bifiltrations, and the degree bifiltrations. For the multicover and subdivision bifiltrations, we get 1-Lipschitz stability results closely analogous to the standard stability results for 1-parameter persistent homology. Our results for the degree bifiltrations are weaker, but they are tight, in a sense. As an application of our theory, we prove a law of large numbers for subdivision bifiltrations of random data.

Open access
preprint2022arXiv

The Universal ℓp\ell^p-Metric on Merge Trees

Adapting a definition given by Bjerkevik and Lesnick for multiparameter persistence modules, we introduce an ℓp\ell^p-type extension of the interleaving distance on merge trees. We show that our distance is a metric, and that it upper-bounds the pp-Wasserstein distance between the associated barcodes. For each p∈[1,∞]p\in[1,\infty], we prove that this distance is stable with respect to cellular sublevel filtrations and that it is the universal (i.e., largest) distance satisfying this stability property. In the p=∞p=\infty case, this gives a novel proof of universality for the interleaving distance on merge trees.

Open access
preprint2022arXiv

Universality of the Homotopy Interleaving Distance

As a step towards establishing homotopy-theoretic foundations for topological data analysis (TDA), we introduce and study homotopy interleavings between filtered topological spaces. These are homotopy-invariant analogues of interleavings, objects commonly used in TDA to articulate stability and inference theorems. Intuitively, whereas a strict interleaving between filtered spaces XX and YY certifies that XX and YY are approximately isomorphic, a homotopy interleaving between XX and YY certifies that XX and YY are approximately weakly equivalent. The main results of this paper are that homotopy interleavings induce an extended pseudometric dHId_{HI} on filtered spaces, and that this is the universal pseudometric satisfying natural stability and homotopy invariance axioms. To motivate these axioms, we also observe that dHId_{HI} (or more generally, any pseudometric satisfying these two axioms and an additional "homology bounding" axiom) can be used to formulate lifts of several fundamental TDA theorems from the algebraic (homological) level to the level of filtered spaces. Finally, we consider the problem of establishing a persistent Whitehead theorem in terms of homotopy interleavings. We provide a counterexample to a naive formulation of the result.

Open access
preprint2020arXiv

Quantifying Genetic Innovation: Mathematical Foundations for the Topological Study of Reticulate Evolution

A topological approach to the study of genetic recombination, based on persistent homology, was introduced by Chan, Carlsson, and Rabadán in 2013. This associates a sequence of signatures called barcodes to genomic data sampled from an evolutionary history. In this paper, we develop theoretical foundations for this approach. First, we present a novel formulation of the underlying inference problem. Specifically, we introduce and study the novelty profile, a simple, stable statistic of an evolutionary history which not only counts recombination events but also quantifies how recombination creates genetic diversity. We propose that the (hitherto implicit) goal of the topological approach to recombination is the estimation of novelty profiles. We then study the problem of obtaining a lower bound on the novelty profile using barcodes. We focus on a low-recombination regime, where the evolutionary history can be described by a directed acyclic graph called a galled tree, which differs from a tree only by isolated topological defects. We show that in this regime, under a complete sampling assumption, the 1st1^\mathrm{st} barcode yields a lower bound on the novelty profile, and hence on the number of recombination events. For i>1i>1, the ithi^{\mathrm{th}} barcode is empty. In addition, we use a stability principle to strengthen these results to ones which hold for any subsample of an arbitrary evolutionary history. To establish these results, we describe the topology of the Vietoris--Rips filtrations arising from evolutionary histories indexed by galled trees. As a step towards a probabilistic theory, we also show that for a random history indexed by a fixed galled tree and satisfying biologically reasonable conditions, the intervals of the 1st1^{\mathrm{st}} barcode are independent random variables. Using simulations, we explore the sensitivity of these intervals to recombination.

Open access
preprint2016arXiv

Induced Matchings and the Algebraic Stability of Persistence Barcodes

We define a simple, explicit map sending a morphism f:M→Nf:M \rightarrow N of pointwise finite dimensional persistence modules to a matching between the barcodes of MM and NN. Our main result is that, in a precise sense, the quality of this matching is tightly controlled by the lengths of the longest intervals in the barcodes of ker⁡f\ker f and cokerf\mathop{\mathrm{coker}} f. As an immediate corollary, we obtain a new proof of the algebraic stability of persistence, a fundamental result in the theory of persistent homology. In contrast to previous proofs, ours shows explicitly how a δδ-interleaving morphism between two persistence modules induces a δδ-matching between the barcodes of the two modules. Our main result also specializes to a structure theorem for submodules and quotients of persistence modules, and yields a novel "single-morphism" characterization of the interleaving relation on persistence modules.

Open access
preprint2015arXiv

Interactive Visualization of 2-D Persistence Modules

The goal of this work is to extend the standard persistent homology pipeline for exploratory data analysis to the 2-D persistence setting, in a practical, computationally efficient way. To this end, we introduce RIVET, a software tool for the visualization of 2-D persistence modules, and present mathematical foundations for this tool. RIVET provides an interactive visualization of the barcodes of 1-D affine slices of a 2-D persistence module MM. It also computes and visualizes the dimension of each vector space in MM and the bigraded Betti numbers of MM. At the heart of our computational approach is a novel data structure based on planar line arrangements, on which we can perform fast queries to find the barcode of any slice of MM. We present an efficient algorithm for constructing this data structure and establish bounds on its complexity.

Open access
preprint2015arXiv

The Theory of the Interleaving Distance on Multidimensional Persistence Modules

In 2009, Chazal et al. introduced εε-interleavings of persistence modules. εε-interleavings induce a pseudometric dId_I on (isomorphism classes of) persistence modules, the interleaving distance. The definitions of εε-interleavings and dId_I generalize readily to multidimensional persistence modules. In this paper, we develop the theory of multidimensional interleavings, with a view towards applications to topological data analysis. We present four main results. First, we show that on 1-D persistence modules, dId_I is equal to the bottleneck distance dBd_B. This result, which first appeared in an earlier preprint of this paper, has since appeared in several other places, and is now known as the isometry theorem. Second, we present a characterization of the εε-interleaving relation on multidimensional persistence modules. This expresses transparently the sense in which two εε-interleaved modules are algebraically similar. Third, using this characterization, we show that when we define our persistence modules over a prime field, dId_I satisfies a universality property. This universality result is the central result of the paper. It says that dId_I satisfies a stability property generalizing one which dBd_B is known to satisfy, and that in addition, if dd is any other pseudometric on multidimensional persistence modules satisfying the same stability property, then d≤dId\leq d_I. We also show that a variant of this universality result holds for dBd_B, over arbitrary fields. Finally, we show that dId_I restricts to a metric on isomorphism classes of finitely presented multidimensional persistence modules.

Open access
preprint2012arXiv

Multidimensional Interleavings and Applications to Topological Inference

This work concerns the theoretical foundations of persistence-based topological data analysis. We develop theory of topological inference in the multidimensional persistence setting, and directly at the (topological) level of filtrations rather than only at the (algebraic) level of persistent homology modules. Our main mathematical objects of study are interleavings. These are tools for quantifying the similarity between two multidimensional filtrations or persistence modules. They were introduced for 1-D filtrations and persistence modules by Chazal, Cohen-Steiner, Glisse, Guibas, and Oudot. We introduce generalizations of the definitions of interleavings given by Chazal et al. and use these to define pseudometrics, called interleaving distances, on multidimensional filtrations and multidimensional persistence modules. We present an in-depth study of interleavings and interleaving distances. We then use them to formulate and prove several multidimensional analogues of a topological inference theorem of Chazal, Guibas, Oudot, and Skraba. These results hold directly at the level of filtrations; they yield as corollaries corresponding results at the module level.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.