Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Approximation Algorithms for Vietoris-Rips and Cech Filtrations
Speaker:Aruni Choudhary
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Promotionskolloquium
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Monday, 11 December 2017
Time:11:00
Duration:75 Minutes
Location:Saarbrücken
Building:E1 4
Room:019
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
Name(s):Aruni Choudhary
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Aruni Choudhary, 12/07/2017 12:33 PMLast modified by:Uwe Brahm/MPII/DE, 12/11/2017 07:01 AM
  • Aruni Choudhary, 12/07/2017 12:36 PM
  • Aruni Choudhary, 12/07/2017 12:33 PM -- Created document.