Primož Škraba, João Pita Costa
Abstract. Decomposition results are of great importance in all areas of mathematics, permitting us to study a certain problem within its indecomposable components. Such results have proven to be of great importance in the study of persistent homology, particularly for the encoding of topological information in barcodes. In this paper we present novel decomposition results for persistence based on the diagram of vector spaces and linear maps describing the persistent features. We will derive several algorithmic constructions from the modularity properties of the underlying lattice construction over such diagram, and present some applications to topological data analysis.
1. Motivation. Decomposition results are of great importance as they permit to study wide problems locally in the indecomposable elements of the algebra, which is in general a more accessible task, and transfer local answers to a general algebraic structure constituted by those irreducibles. The concept of irreducible element is frequent and common to different mathematical contexts (a matrix is irreducible if it is not similar via a permutation to a block upper triangular matrix that has more than one block of positive size; a commutative ring R is irreducible if its prime spectrum Spec R is an irreducible topological space; or a n-manifold is irreducible if any embedded (n - 1)-sphere bounds an embedded n-ball). A direct sum decomposition of interval modules is possible for any persistence module consisting of finite-dimensional vector spaces under a totally ordered indexing set. This result can be extended to any persistence module with the descending chain condition on images and kernels.
A more general result, known as Krull-Schmidt Theorem, states that any nontrivial module satisfying certain finiteness conditions (the ACC and the DCC, simultaneously) on submodules satisfies the Remak decomposition, that is, it can be expressed as a direct sum of indecomposable modules. This decomposition is unique up to permutation of the summands and up to isomorphism. The consequences of the Remak-Krull-Schmidt decomposition are an explicit example of the role of such result permitting the use of barcodes to capture the topological information in the zigzag persistence case.
The Jordan-Holder Theorem generalizes the decomposition of a natural number by a product of primes unique up to the permutation of factors. It states that any two composition series of a given group have the same composition length and the same composition factors, up to permutation of the factors and isomorphism. This is a particular case of the application to the lattice of submodules of a given module, of a more general result in lattice theory establishing that all maximal chains of finite length in a modular lattice have the same length. In fact, the Krull-Schmidt Theorem is a particular case of the Jordan-Holder Theorem due to a result by Azumaya.
2. Related Work. Since the first papers on persistent homology in the beginning of the century, there were several successful generalizations focusing different aspects of real problems and the computability of achieved solutions. Introduced as an extension of persistent homology, zigzag persistent homology can handle diagrams of spaces that are not strictly filtrations. Given a zigzag diagram of vector spaces, the arrows between vector spaces are not ordered in the same direction but, due to the machinery of quiver theory, one can prove that still it decomposes into summands that can be described by a barcode, much like the case of standard persistence.
Multidimensional persistence was established to work on different dimensions simultaneously and not along a single dimension as standard persistence does. It functions along maps between spaces which are parametrized with respect to multiple dimensions and coincides with standard persistence when fixing all but one parameters.In such generalization there is no analog to the barcode to capture all topological information. Although, the rank invariant is a natural extension of the barcode, it can be shown that there is no complete invariant for multidimensional persistence.
By defining persistent homology groups over any set of spaces which have inclusions defined, there exists a direct and acyclic underlying graph between the spaces. With such a method they offer a generalization for standard, zigzag and multidimensional persistence, and give an algorithm to compute the persistent homology groups simultaneously for all subgraphs which contain a single sink in O(n^4) as well as an algorithm to compute persistence for any subgraph in the same running time.
3. Contributions. A particular order structure - a lattice structure - on the diagrams of vector spaces was studied by the authors. Due to its nice properties of this distributive algebra, one can determine robust decomposition results due to the modularity of the underlying lattice structure. In this paper we will present some of this derived decomposition theorems, and discuss its interpretation in the framework of persistence. We shall start this paper by introducing some background notions on lattice theory and persistent homology that can help the reader through the following sections. Still in this preliminaries section we will review the lattice construction focusing aspects that will later be of great importance when deriving algorithms. In the following section will present several structural results that establish novel decompositions in the framework of persistence. We will start with the largest injective, derived from the completeness of the underlying lattice, where the computation of joins for several simultaneous given elements can be obtained in one go. Next we will focus on the study of trees, presenting several decomposition results based on the lattice construction over that given order structure. The bifiltration case shall follow the decomposition for trees, where we will discuss the sections of that structure as irreducible elements. A last section is dedicated to concrete applications of these decomposition results to topological data analysis.
JOÃO PITA COSTA 2014