Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn algebraic Wasserstein distance for generalized persistence modules
159
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The Wasserstein distances are a family of $L^p$ distances, with $1 leq p leq infty$, for persistence diagrams. We define Wasserstein distances for persistence modules, the algebraic counterpart to persistence diagrams, and prove the following isometry theorem. The $p$-Wasserstein distance of a persistence module and its persistence diagram agree. Since our algebraic Wasserstein distances do not require computing a persistence diagram, they apply to persistence modules that are not interval decomposable and also to generalized persistence modules, such as multi-parameter persistence modules. We also prove structure theorems for maps from an interval module and maps to an interval module and show that for monomorphisms and epimorphisms of persistence modules there is an induced algebraic matching.
rate research
Read More
The classical persistence algorithm virtually computes the unique decomposition of a persistence module implicitly given by an input simplicial filtration. Based on matrix reduction, this algorithm is a cornerstone of the emergent area of topological data analysis. Its input is a simplicial filtration defined over the integers $mathbb{Z}$ giving rise to a $1$-parameter persistence module. It has been recognized that multi-parameter version of persistence modules given by simplicial filtrations over $d$-dimensional integer grids $mathbb{Z}^d$ is equally or perhaps more important in data science applications. However, in the multi-parameter setting, one of the main challenges is that topological summaries based on algebraic structure such as decompositions and bottleneck distances cannot be as efficiently computed as in the $1$-parameter case because there is no known extension of the persistence algorithm to multi-parameter persistence modules. We present an efficient algorithm to compute the unique decomposition of a finitely presented persistence module $M$ defined over the multiparameter $mathbb{Z}^d$.The algorithm first assumes that the module is presented with a set of $N$ generators and relations that are emph{distinctly graded}. Based on a generalized matrix reduction technique it runs in $O(N^{2omega+1})$ time where $omega<2.373$ is the exponent for matrix multiplication. This is much better than the well known algorithm called Meataxe which runs in $tilde{O}(N^{6(d+1)})$ time on such an input. In practice, persistence modules are usually induced by simplicial filtrations. With such an input consisting of $n$ simplices, our algorithm runs in $O(n^{2omega+1})$ time for $d=2$ and in $O(n^{d(2omega + 1)})$ time for $d>2$.
We prove that the $infty$-category of $mathrm{MGL}$-modules over any scheme is equivalent to the $infty$-category of motivic spectra with finite syntomic transfers. Using the recognition principle for infinite $mathbb{P}^1$-loop spaces, we deduce that very effective $mathrm{MGL}$-modules over a perfect field are equivalent to grouplike motivic spaces with finite syntomic transfers. Along the way, we describe any motivic Thom spectrum built from virtual vector bundles of nonnegative rank in terms of the moduli stack of finite quasi-smooth derived schemes with the corresponding tangential structure. In particular, over a regular equicharacteristic base, we show that $Omega^infty_{mathbb{P}^1}mathrm{MGL}$ is the $mathbb{A}^1$-homotopy type of the moduli stack of virtual finite flat local complete intersections, and that for $n>0$, $Omega^infty_{mathbb{P}^1} Sigma^n_{mathbb{P}^1} mathrm{MGL}$ is the $mathbb{A}^1$-homotopy type of the moduli stack of finite quasi-smooth derived schemes of virtual dimension $-n$.
Recent years have witnessed a tremendous growth using topological summaries, especially the persistence diagrams (encoding the so-called persistent homology) for analyzing complex shapes. Intuitively, persistent homology maps a potentially complex input object (be it a graph, an image, or a point set and so on) to a unified type of feature summary, called the persistence diagrams. One can then carry out downstream data analysis tasks using such persistence diagram representations. A key problem is to compute the distance between two persistence diagrams efficiently. In particular, a persistence diagram is essentially a multiset of points in the plane, and one popular distance is the so-called 1-Wasserstein distance between persistence diagrams. In this paper, we present two algorithms to approximate the 1-Wasserstein distance for persistence diagrams in near-linear time. These algorithms primarily follow the same ideas as two existing algorithms to approximate optimal transport between two finite point-sets in Euclidean spaces via randomly shifted quadtrees. We show how these algorithms can be effectively adapted for the case of persistence diagrams. Our algorithms are much more efficient than previous exact and approximate algorithms, both in theory and in practice, and we demonstrate its efficiency via extensive experiments. They are conceptually simple and easy to implement, and the code is publicly available in github.
We extend the stable motivic homotopy category of Voevodsky to the class of scalloped algebraic stacks, and show that it admits the formalism of Grothendiecks six operations. Objects in this category represent generalized cohomology theories for stacks like algebraic K-theory, as well as new examples like genuine motivic cohomology and algebraic cobordism. These cohomology theories admit Gysin maps and satisfy homotopy invariance, localization, and Mayer-Vietoris. We also prove a fixed point localization formula for torus actions. Finally, the construction is contrasted with a limit-extended stable motivic homotopy category: we show for example that limit-extended motivic cohomology of quotient stacks is computed by the equivariant higher Chow groups of Edidin-Graham, and we also get a good new theory of Borel-equivariant algebraic cobordism.
We study the ring of algebraic functions on the space of persistence barcodes, with applications to pattern recognition.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
