Campus Event Calendar
Event Entry
What and Who
Approximation Algorithms for Vietoris-Rips and Cech Filtrations
Aruni Choudhary
Max-Planck-Institut für Informatik - D1
Promotionskolloquium
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 11 December 2017
11:00
75 Minutes
E1 4
019
Saarbrücken
Abstract
Persistent Homology is the prominent tool in the field of Topological Data Analysis that aims at understanding and summarizing the shape of data coming from metric spaces. It computes a topological summary that can identify the important features of data, while being stable to imperfections in the data. Vietoris-Rips and Cech complexes are popular simplicial complexes that are used by Persistent Homology to compute the topological summary. Unfortunately, the question of computation becomes prohibitively expensive when dealing with high-dimensional metric spaces, as the size of these simplicial complexes blows up.
In my thesis, we attack this problem from several different angles. We present several techniques to approximate the topological summary. Some of our techniques are tailored towards point clouds in Euclidean space and make use of high-dimensional lattice geometry. We present the first polynomial-sized approximation schemes which are independent of the ambient dimension. On the other hand, we also show that polynomial complexity is impossible when a high approximation quality is desired. In addition, we also develop results for metric spaces which have low intrinsic dimension.
Contact
Aruni Choudhary
--email hidden
passcode not visible
logged in users only
Aruni Choudhary, 12/07/2017 12:36
Aruni Choudhary, 12/07/2017 12:33 -- Created document.
Aruni Choudhary, 12/07/2017 12:33 -- Created document.