Michael Lesnick
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Michael Lesnick has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Michael Kerber
Graz University of Technology, Graz, Austria
4 shared publications - Andrew J. Blumberg
Department of Mathematics, Columbia University, New York, USA
3 shared publications - Georg Osang
IST Austria (Institute of Science and Technology Austria), Klosterneuburg, Austria
2 shared publications - René Corbet
Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden
2 shared publications - Andrew J. Blumberg
University of Texas at Austin
1 shared publication - Daniel Scholes Rosenbloom
Columbia University
1 shared publication
Latest Publications
- Open Access
Fast Queries of Fibered Barcodes
The fibered barcode $\mathcal{F}(M)$ of a bipersistence module $M$ is the map sending each non-negatively sloped affine line $\ell \subset \mathbb{R}^2$ to the barcode of the restriction of $M$ along $\ell$. The simplicity, computability, and stability of $\mathcal{F}(M)$ make it a natural choice of invariant for data analysis applications. In an earlier preprint [arXiv:1512.00180], we introduced a framework for real-time interactive visualization of $\mathcal{F}(M)$, which allows the user to select a single line $\ell$ via a GUI and then plots the associated barcode. This visualization is a key feature of our software RIVET for the visualization and analysis of bipersistent homology. Such interactive visualization requires a framework for efficient queries of $\mathcal{F}(M)$, i.e., for quickly obtaining the barcode along a given line $\ell$. To enable such queries, we introduced a novel data structure based on planar line arrangements, called an augmented arrangement. The aim of the present paper is to give an updated and improved exposition of the parts of our preprint [arXiv:1512.00180] concerning the mathematics of the augmented arrangement and its computation. Notably, by taking the input to be a minimal presentation rather than a chain complex, we are able to substantially simplify our main algorithm and its complexity analysis.Open AccessFast Queries of Fibered Barcodes
The fibered barcode $\mathcal{F}(M)$ of a bipersistence module $M$ is the map sending each non-negatively sloped affine line $\ell \subset \mathbb{R}^2$ to the barcode of the restriction of $M$ along $\ell$. The simplicity, computability, and stability of $\mathcal{F}(M)$ make it a natural choice of invariant for data analysis applications. In an earlier preprint [arXiv:1512.00180], we introduced a framework for real-time interactive visualization of $\mathcal{F}(M)$, which allows the user to select a single line $\ell$ via a GUI and then plots the associated barcode. This visualization is a key feature of our software RIVET for the visualization and analysis of bipersistent homology. Such interactive visualization requires a framework for efficient queries of $\mathcal{F}(M)$, i.e., for quickly obtaining the barcode along a given line $\ell$. To enable such queries, we introduced a novel data structure based on planar line arrangements, called an augmented arrangement. The aim of the present paper is to give an updated and improved exposition of the parts of our preprint [arXiv:1512.00180] concerning the mathematics of the augmented arrangement and its computation. Notably, by taking the input to be a minimal presentation rather than a chain complex, we are able to substantially simplify our main algorithm and its complexity analysis. - Open Access
Sparse Approximation of the Subdivision-Rips Bifiltration for Doubling Metrics
The Vietoris-Rips filtration, the standard filtration on metric data in topological data analysis, is notoriously sensitive to outliers. Sheehy's subdivision-Rips bifiltration $\mathcal{SR}(-)$ is a density-sensitive refinement that is robust to outliers in a strong sense, but whose 0-skeleton has exponential size. For $X$ a finite metric space of constant doubling dimension and fixed $ε>0$, we construct a $(1+ε)$-homotopy interleaving approximation of $\mathcal{SR}(X)$ whose $k$-skeleton has size $O(|X|^{k+2})$. For $k\geq 1$ constant, the $k$-skeleton can be computed in time $O(|X|^{k+3})$.Open AccessSparse Approximation of the Subdivision-Rips Bifiltration for Doubling Metrics
The Vietoris-Rips filtration, the standard filtration on metric data in topological data analysis, is notoriously sensitive to outliers. Sheehy's subdivision-Rips bifiltration $\mathcal{SR}(-)$ is a density-sensitive refinement that is robust to outliers in a strong sense, but whose 0-skeleton has exponential size. For $X$ a finite metric space of constant doubling dimension and fixed $ε>0$, we construct a $(1+ε)$-homotopy interleaving approximation of $\mathcal{SR}(X)$ whose $k$-skeleton has size $O(|X|^{k+2})$. For $k\geq 1$ constant, the $k$-skeleton can be computed in time $O(|X|^{k+3})$. - Open Access
Delaunay Bifiltrations of Functions on Point Clouds
The Delaunay filtration $\mathcal{D}_{\bullet}(X)$ of a point cloud $X\subset \mathbb{R}^d$ is a central tool of computational topology. Its use is justified by the topological equivalence of $\mathcal{D}_{\bullet}(X)$ and the offset (i.e., union-of-balls) filtration of $X$. Given a function $γ: X \to \mathbb{R}$, we introduce a Delaunay bifiltration $\mathcal{DC}_{\bullet}(γ)$ that satisfies an analogous topological equivalence, ensuring that $\mathcal{DC}_{\bullet}(γ)$ topologically encodes the offset filtrations of all sublevel sets of $γ$, as well as the topological relations between them. $\mathcal{DC}_{\bullet}(γ)$ is of size $O(|X|^{\lceil\frac{d+1}{2}\rceil})$, which for $d$ odd matches the worst-case size of $\mathcal{D}_{\bullet}(X)$. Adapting the Bowyer-Watson algorithm for computing Delaunay triangulations, we give a simple, practical algorithm to compute $\mathcal{DC}_{\bullet}(γ)$ in time $O(|X|^{\lceil \frac{d}{2}\rceil +1})$. Our implementation, based on CGAL, computes $\mathcal{DC}_{\bullet}(γ)$ with modest overhead compared to computing $\mathcal{D}_{\bullet}(X)$, and handles tens of thousands of points in $\mathbb{R}^3$ within seconds.Open AccessDelaunay Bifiltrations of Functions on Point Clouds
The Delaunay filtration $\mathcal{D}_{\bullet}(X)$ of a point cloud $X\subset \mathbb{R}^d$ is a central tool of computational topology. Its use is justified by the topological equivalence of $\mathcal{D}_{\bullet}(X)$ and the offset (i.e., union-of-balls) filtration of $X$. Given a function $γ: X \to \mathbb{R}$, we introduce a Delaunay bifiltration $\mathcal{DC}_{\bullet}(γ)$ that satisfies an analogous topological equivalence, ensuring that $\mathcal{DC}_{\bullet}(γ)$ topologically encodes the offset filtrations of all sublevel sets of $γ$, as well as the topological relations between them. $\mathcal{DC}_{\bullet}(γ)$ is of size $O(|X|^{\lceil\frac{d+1}{2}\rceil})$, which for $d$ odd matches the worst-case size of $\mathcal{D}_{\bullet}(X)$. Adapting the Bowyer-Watson algorithm for computing Delaunay triangulations, we give a simple, practical algorithm to compute $\mathcal{DC}_{\bullet}(γ)$ in time $O(|X|^{\lceil \frac{d}{2}\rceil +1})$. Our implementation, based on CGAL, computes $\mathcal{DC}_{\bullet}(γ)$ with modest overhead compared to computing $\mathcal{D}_{\bullet}(X)$, and handles tens of thousands of points in $\mathbb{R}^3$ within seconds. - Top Cited PapersOpen Access
- 14 September 2023
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 376 (12) , 8269-8307
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 X X and Y Y certifies that X X and Y Y are approximately isomorphic, a homotopy interleaving between X X and Y Y certifies that X X and Y Y are approximately weakly equivalent. The main results of this paper are that homotopy interleavings induce an extended pseudometric d H I d_{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 d H I d_{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.
- 14 September 2023
- Published by American Mathematical Society (AMS) in Transactions of the American Mathematical Society
- Vol. 376 (12) , 8269-8307
Top Cited PapersOpen AccessUniversality 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 X X and Y Y certifies that X X and Y Y are approximately isomorphic, a homotopy interleaving between X X and Y Y certifies that X X and Y Y are approximately weakly equivalent. The main results of this paper are that homotopy interleavings induce an extended pseudometric d H I d_{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 d H I d_{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
- 20 February 2023
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 70 (2) , 376-405
Computing the Multicover Bifiltration
Given a finite set $$A\subset {\mathbb {R}}^d$$ , let $$\text {Cov}_{r,k}$$ denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the 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 Čech-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.- 20 February 2023
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 70 (2) , 376-405
Open AccessComputing the Multicover Bifiltration
Given a finite set $$A\subset {\mathbb {R}}^d$$ , let $$\text {Cov}_{r,k}$$ denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the 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 Čech-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. - Top Cited Papers
- 17 October 2022
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 24 (2) , 385-427
Stability of 2-Parameter Persistent Homology
- 17 October 2022
- Published by Springer Nature in Foundations of Computational Mathematics
- Vol. 24 (2) , 385-427
Top Cited PapersStability of 2-Parameter Persistent Homology
- Top Cited Papers
- 26 May 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Applied Algebra and Geometry
- Vol. 6 (2) , 267-298
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]$-module $M$, where $K$ is a field. The algorithm ...- 26 May 2022
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Applied Algebra and Geometry
- Vol. 6 (2) , 267-298
Top Cited PapersComputing 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]$-module $M$, where $K$ is a field. The algorithm ... - Open Access
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 $X$ and $Y$ certifies that $X$ and $Y$ are approximately isomorphic, a homotopy interleaving between $X$ and $Y$ certifies that $X$ and $Y$ are approximately weakly equivalent. The main results of this paper are that homotopy interleavings induce an extended pseudometric $d_{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 $d_{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 AccessUniversality 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 $X$ and $Y$ certifies that $X$ and $Y$ are approximately isomorphic, a homotopy interleaving between $X$ and $Y$ certifies that $X$ and $Y$ are approximately weakly equivalent. The main results of this paper are that homotopy interleavings induce an extended pseudometric $d_{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 $d_{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
Stability of 2-Parameter Persistent Homology
The \v{C}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 AccessStability of 2-Parameter Persistent Homology
The \v{C}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
Computing the Multicover Bifiltration
Given a finite set $A\subset\mathbb{R}^d$, let Cov$_{r,k}$ denote the set of all points within distance $r$ to at least $k$ points of $A$. Allowing $r$ and $k$ to vary, we obtain a 2-parameter family of spaces that grow larger when $r$ increases or $k$ 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 AccessComputing the Multicover Bifiltration
Given a finite set $A\subset\mathbb{R}^d$, let Cov$_{r,k}$ denote the set of all points within distance $r$ to at least $k$ points of $A$. Allowing $r$ and $k$ to vary, we obtain a 2-parameter family of spaces that grow larger when $r$ increases or $k$ 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.