This page contains a technical report on the work conducted in the framework of the project.
The main objective of the project was to contribute towards the development of a theoretical basis and specific applications related to the concept of persistent homology in three domains: digital images, data mining, and dynamical systems. Secondary objectives included the developments in numerical analysis of 1-dimensional dynamics and the development of algorithms for the computation of advanced algebraic-topological invariants of multi-dimensional digital images.
The work conducted in the framework of the project concentrated on 6 specific topics (listed in the order of importance):
(1) A method for the computation of the homomorphism induced in homology by a continuous map given by an approximation of its graph, with the focus on weakening the assumptions of the previously developed methods and fitting the new approach into the persistence framework.
(2) Generalization of a comprehensive computational method for automatic topological-combinatorial analysis of dynamical systems from the case of maps to the case of flows, and application of the new method and algorithms to the analysis of a specific dynamical system in epidemiology.
(3) Development of methods based on the persistence paradigm to algorithmic topological analysis of dynamical systems; in particular, to the computation of the Conley index using approximate index pairs, and to the construction of Morse decompositions using gradually better approximations of a dynamical system.
(4) Development of a method for efficient computation of a possibly accurate lower bound for the expansivity rate in 1-dimensional dynamics. The method is based on subdividing the domain of the map into a finite partition and using graph algorithms for obtaining the bound from a weighted directed graph that represents the map on the partition.
(5) Development of effective algorithms and related software prototypes for the computation of advanced algebraic-topological invariants of digital images.
(6) Investigating the possibility of applying the methods of topological data analysis to medical data sets, both text documents or weakly structured data (like medical records), and cardiological data.
The main results in these 6 topics achieved so far are as follows:
(1) A new method for the computation of a homomorphism induced in homology by a correspondence has been developed (described in a journal article). Moreover, it has been proved that an increasing sequence of graphs of correspondences gives rise to a properly defined tower of linear maps, which opens the possibilities for using the persistence paradigm in this context.
(2) A comprehensive comparison of two major rigorous set-oriented integrators was made (described in a journal article), and new algorithms and software were developed, which allowed to successfully apply this methodology to the analysis of an ODE that models infectious disease spreading between two regions connected by transportation (described in a journal article and a popular science article published by 3 onl-line services).
(3) A method was developed for the determination of the Conley index from approximate index pairs, and preliminary results were announced at a conference. The possibility of using the persistence paradigm in the construction of Morse decompositions was discussed, and some examples were generated which show that a naive straightforward approach is not sufficient to address the problem.
(4) A new algorithm was developed and implemented for the computation of the minimum mean cycle weight in a weighted directed graph, which addresses two issues: minimizing memory usage, and conducting the computations using rigorous numerics; this resulted in a journal article, which was submitted, then rejected, and awaits revision and resubmission. The new algorithm allowed to conduct comprehensive computations for the quadratic map; the results have been published as a journal article. A new method for constructing partitions has been developed, which will result in further developments in the field.
(5) Algorithms for the computation of Eilenberg-Zilber contraction were implemented, and added to the ChainCon Software Package, programmed by the Fellow. An algorithm for the computation of Steenrod squares for cubical sets that represent multi-dimensional bitmap images was developed and accepted for conference proceedings to be published in Springer's LNCS series (indexed in ISI).
(6) Several discussions were held, and academic collaboration with a team consisting of an applied mathematician and a cardiologist has been established.
The expected long-term results in the 6 topics that are expected to be achieved in the future are as follows:
(1) Development of effective and efficient methods for the computation of homomorphisms induced in homology by correspondences in the context of finitely representable sets (such as cubical sets) is expected to lead to add the dynamical component to the topological analysis of data. With this method, it will be possible to map topological features from one image to another. Images varying in time appear in medicine (e.g. a beating heart) and can be obtained with modern equipment, yet automatic analysis is still beyond reach. This technology is expected to contribute in this direction.
(2) Generalization of the method for combinatorial-topological automatic analysis of dynamics from the case of maps to the case of flows is a considerable advancement. The steps completed in the framework of the project lay ground for further work, which is expected to eventually result in the development of a comprehensive method that would deal with flows equally efficiently as the method currently does with maps. Since dynamical systems are often used in a wide range of sciences to model the phenomena developing in time, the effective and efficient methods are expected to contribute substantially to the ease of analysis of such models, and thus to further the progress of applied sciences. In particular, the analysis of a model that describes the spreading of an infectious disease between two regions connected by transportation, showed that a simple epidemic model may experience a wide variety of dynamical behaviors, and thus decisions regarding protection against and reaction to the spread of infectious diseases must be made very carefully.
(3) A method for the analysis of Morse decompositions and computing the Conley index based on persistent homology is expected to provide an efficient tool that would yield meaningful results at much lower resolution of the analysis of dynamics, thus requiring much fewer resources than the methods currently available.
(4) With the new and efficient algorithms for the rigorous estimation of expansivity rates in one-dimensional dynamics, it is expected that substantial progress will be achieved in the determination of a specific lower bound for the measure of stochastic parameters of the quadratic map. This one-dimensional example is a model of sophisticated phenomena in dynamics, and its understanding is expected to further our comprehension of dynamical systems that appear in the nature.
(5) Effective computation of advanced algebraic-topological invariants for digital images is expected to contribute to the development of new and more reliable automatic methods for the analysis of digital images. Such methods find applications in various areas, from defence to medicine, e.g., detection of cancer cells in biopsy samples.
(6) Applying automatic methods based on persistent homology for data analysis of biomedical data is expected to provide new insights that can, in the distant future, result in increasing the reliability of automatic diagnosis methods and improve artificial intelligence systems that support the decisions made by medical doctors.
To sum up, the interdisciplinary research conducted in the framework of the project provided several results of academic value, and provided preliminary insight into new areas that are worth further attention of scientists.
The PHIDM project has received funding from the European Union's
Seventh Framework Programme for research, technological development
and demonstration under grant agreement no. 622033.