Topological data analysis

2022/2023
Programme:
Computer Science and Mathematics, Second Cycle
Year:
1 ali 2 year
Semester:
second
Kind:
optional
Group:
B
ECTS:
6
Language:
slovenian, english
Hours per week – 2. semester:
Lectures
3
Seminar
0.67
Tutorial
1.33
Lab
0
Prerequisites

Successful completion of homework and projects is required for students to approach to a final exam.

Content (Syllabus outline)

Topology is the mathematical field dealing with shapes and with modeling and understanding higher dimensional objects. Topologial data analysis is a field between topology and computer science dealing with shapes arising from data, images, and higher dimensional data sets. In view of massive quantities of experimental data on one hand, and available computing power on the other hand, numerous new algorithms and models for qualitative analysis and representation of such data sets using topological models and methods have been developed. Graphs, surfaces, triangulations, simplicial and cell complexes and manifolds are used for data representation and object reconstruction. Topological invariants like the number of components, the fundamental group, hopology groups and the cohomology ring, Morse theory, filtrations and persistence are used for analyzing these models. These invariants are typically computable and give answers to questions like, is the object composed from one or more components, does it have holes and tunnels, which features appear at different resolutions, how do the separate pieces connect into the whole, … On the other hand new algorithms for efficient computation of these invariants are appearing.
In the course, fundamental topological concepts and methods, which are used in modeling and analyzing higher dimensional objects and spaces, will be introduced. Further, basic numerical and algebraic invariants of the topological models will be explained. Special attention will be given to applications of these methods to analysis of data sets and reconstruction of the underlying objects, configuration spaces of robots and mechanical systems, analysis of networks and other practical problems and domains. We will introduce the following topological concepts and models:
Fundamentals of topological and metric spaces
Graphs and surfaces
Triangulations, simplicial and cell complexes
Homology groups and Betti numbers, , their interpretation, and basic algorithms for their computation
Discrete Morse functions and their application to data analysis and object reconstruction
Filtrations and persistence for dealing with changing resolutions
The main part of the course will be devoted to applications of the topological concepts and algorithms in analyzing specific data sets, problems and models.

Readings

Herbert Edelsbrunner, John Harer: Computational Topology, American Mathematical Society, 2010
Afra J. Zomorodian: Topology for Computing, Cambridge University Press, 2005
Hjelle, Øyvind, Dæhlen, Morten: Triangulations and applications, Springer, 2006
Kevin Knudson: Morse theory, smooth and discrete, World Scientific, 2015

Objectives and competences

The aim of this course is to introduce in an informal and intuitive way the basic concepts of algebraic topology which are used in algorithms for analysis of big, possibly higher dimensional data sets, for reconstruction of obects and configuration soaces of robots and mechanical systems and in other practical applications. Mathematical concept will be presented from the point of view of applications, special attention will be given to specific examples and algorithms.

Intended learning outcomes

After completing the course students will:
understand the concept of a topological invariant and its role in analyzing shape and other properties of data;
understand the concept of a simplcial complex and the basic algorithms for constructing simplicial complexes on data sets;
understand the basic computational approches and algorithms for computing Euler characteristic, homology groups and Betti numbers;
understand the concepts of filtrations and persistence;
be able to use the concepts intruduced to construct simple topological algorithms for analysizing data sets and interpret the results.

Learning and teaching methods

Combined lecturing with simultaneous use of the blackboard and computer projection explaining the theoretical concepts and specific meaning in specific cases. Lab work in computer-equipped lecture rooms. Individual and work in team. Emphasis on practical problem solving and group work.

Assessment

Type (examination, oral, coursework, project):
Continuing (homework, midterm exams, project work)
Final: (written and oral exam)
Grading: 6-10 pass, 5 fail.

Lecturer's references

VIRK, Žiga. Small loop spaces. Topology and its Applications, ISSN 0166-8641, 2010, vol. 157, no. 2, str. 451-455.

VIRK, Žiga. Realizations of countable groups as fundamental groups of compacta. Mediterranean journal of mathematics, 2013, vol. 10, no. 3, str. 1573-1589.

DYDAK, Jerzy, VIRK, Žiga. Preserving coarse properties. Revista matemática complutense, 2016, vol. 29, iss. 1, str. 191-206.

EDELSBRUNNER, Herbert, VIRK, Žiga, WAGNER, Hubert. Smallest enclosing spheres and Chernoff points in Bregman geometry. V: SPECKMANN, Bettina (ur.), TÓTH, Csaba D. (ur.). 34th International Symposium on Computational Geometry : SoCG 2018, June 11-14, 2018, Budapest, Hungary,

VIRK, Žiga. Approximations of 1-dimensional intrinsic persistence of geodesic spaces and their stability. Revista matemática complutense, Jan. 2019, vol. 32, iss. 1, str. 195-213.