PORTALE DELLA DIDATTICA

Ricerca CERCA
  KEYWORD

Geometria algebrica computazionale e differenziale

Theses at Politecnico

C++ implementation of the construction of HoPeS - the Homologically Persistent Skeleton

keywords C++, COMPUTATIONAL TOPOLOGY, ALGORITHMS DEVELOPMENT, DATA ANALYSIS

Reference persons FRANCESCO VACCARINO

External reference persons Dr. Sara Kalisnik - Max Planck Institut - Leipzig (D)
http://personal-homepages.mis.mpg.de/kalisnik/index.html

Research Groups Geometria algebrica computazionale e differenziale

Thesis type SW DEVELOPEMENT

Description A data set is often given as a point cloud, i.e. a non-empty finite metric space.
An important problem is to detect the topological shape of data — for example,
to approximate a point cloud by a low-dimensional non-linear subspace such as a
graph or a simplicial complex. Classical clustering methods and principal
component analysis work very well when data points split
into well-separated groups or lie near linear subspaces. Methods from
topological data analysis detect more complicated patterns such as holes and voids that
persist for a long time in a 1- parameter family of simplicial complexes associated
to a point cloud. We can think of this 1-parameter family as a weighted complex.

The homologically persistent skeleton (HoPeS) is a subcomplex of a
weighted complex that arises from point cloud data
which topologically approximates the point cloud, in
the sense that it has the same homology up to a prescribed dimension at
every stage of the filtration. It is constructed by taking the
higher-dimensional analogue of a spanning tree with minimal total weight
and adding the so-called critical faces -- those that create non-trivial
homology. Whenever homology is enlarged, suitable critical faces have to
be added (the stage when that happens is called their birth time) and when
homology is reduced, the corresponding critical faces have to be removed
(this is called their death time).

The project would entail the C++ implementation of the construction of
HoPeS, sufficiently effective to be used on real-world data. The
participant should be well familiar with C++ methods used in linear
algebra.

Sources:
http://kurlin.org/projects/persistent-skeleton.pdf
https://arxiv.org/pdf/1701.08395.pdf

Required skills C++, Geometry, Topology, Computational Linear Algebra, Graph Theory

Notes Additional advisor will be Dr.Sara Kalisnik from Max Planck Institut in Leipzig. Scientific visits to her will be contemplated.


Deadline 28/09/2018      PROPONI LA TUA CANDIDATURA




© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
Contatti