Robust Invariants of Nonlinear Systems

Over the past decade several connections between algebraic topology and computer science have generated new theories and computational techniques with an immense number of applications in data mining, image processing, robot motion planning and analysis of sensor networks, to name just a few. The common denominator of these methods is the robustness and stability with respect to noise which are general features of all topological applications. In this project we will apply tools from computational topology to develop methods for solving nonlinear systems of real equations, a fundamental problem in mathematics and computer science. Topological methods can be used to localize a solution and to describe those properties of the solution set that are invariant with respect to continuous perturbations of the system. Such properties are favorable as the system may come from imprecise measurements or from a model with inherent uncertainty. One example of such invariants is the notion of well groups developed recently by Edelsbrunner, Morozov and Patel. However, the computability of well groups has been shown only in a few special cases and the connection between nonlinear systems and topological ideas has not been much analyzed from algorithmic point of view. The objectives of this proposal are: (1) to analyze the computability of well groups and other invariants of systems of nonlinear equations that do not change under perturbations of the system, (2) to analyze the usability of topological methods for robust optimization problems where we want to compute a lower bound on the maximum of an objective function when the constraint is given by a system of nonlinear equations with an inherent uncertainty, and (3) to make computational experiments with low-dimensional data and create a software package that can encode topological invariants of nonlinear systems to so-called persistent diagrams, which is a technique that helps visualize important robust properties by means of certain barcodes. We expect potential future applications in processing data in those situations where one needs to describe the level sets of functions. For scalar functions, there is the famous marching cube algorithm that is being used to extract level sets of medical images. Our research could yield techniques for the extraction of level sets of more dimensional data that are robust with respect to the input. The persons responsible for this project are Peter Franek and the co-applicant Uli Wagner from IST Austria.

Main goals of the project were to analyse algorithms for finding invariants of nonlinear equations using topological methods. Such invariants are robust with respect to perturbations of the system and/or rounding errors. Results: (1) A theoretical analysis of topological tools that are suitable for this purpose: we proposed several algebraic descriptors of such invariants as well as algorithm how to compute them. (2) A demonstration that such invariants are indeed computable, but probably in low dimensions only. In all computational experiments, the number of variables or equations was at most 7. (3) While the previous item excludes some application where high dimension is crucial, we recognised a potential area of industrial application: robotics. To our surprise, we found an application of invariants of nonlinear systems for improving the localisation of unmanned underwater robots. (4) Beyond systems of nonlinear equations, we analysed the computability of topological invariants of spaces in general, namely the computability of homotopy groups and their representatives. It turned out that explicit computation of functions with a given homotopical property is possibly, but not practically feasible, as the lower complexity bounds are typically exponential in the input size, even if the dimension is fixed.