Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Algorithms for Multidimensional Persistence
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Algoritmer för Multidimensionell Persistens (Swedish)
Abstract [en]

The theory of multidimensional persistence was introduced in a paper by G. Carlsson and A. Zomorodian as an extension to persistent homology. The central object in multidimensional persistence is the persistence module, which represents the homology of a multi filtered space. In this thesis, a novel algorithm for computing the persistence module is described in the case where the homology is computed with coefficients in a field. An algorithm for computing the feature counting invariant, introduced by Chachólski et al., is investigated. It is shown that its computation is in general NP-hard, but some special cases for which it can be computed efficiently are presented. In addition, a generalization of the barcode for persistent homology is defined and conditions for when it can be constructed uniquely are studied. Finally, a new topology is investigated, defined for fields of characteristic zero which, via the feature counting invariant, leads to a unique denoising of a tame and compact functor.

Abstract [sv]

Teorin om multidimensionell persistens introduserades i en artikel av G. Carlsson och A. Zomorodian som en generalisering av persistent homologi. Det centrala objektet i multidimensionell persistens är persistensmodulen, som representerar homologin av ett multifilterat rum. I denna uppsats beskrivs en ny algoritm för beräkning av persistensmodulen i fallet där homologin beräknas med koefficienter i en kropp. En algoritm för beräkning av karaktäristik-räknings-invarianten, som introducerade av Chachólski et al., utforskas och det visar sig att dess beräkning i allmänhet är NP-svår. Några specialfall för vilka den kan beräknas effektivt presenteras. Vidare definieras en generalisering av stäckkoden för persistent homologi och kraven för när den kan konstrueras unikt studeras. Slutligen undersöks en ny topologi, definierad för kroppar av karaktäristik noll, som via karaktäristik-räknings-invarianten leder till en unik avbränning.

Place, publisher, year, edition, pages
2016.
Series
TRITA-MAT-E, 2016:36
Keyword [en]
Multidimensional persistence, persistent homology, topological data analy-sis, invariants, barcode, algorithms.
Keyword [sv]
Multidimensionell persistens, persistent homologi, topologisk data-analys, invarianter, streckkod, algoritmer
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-188849OAI: oai:DiVA.org:kth-188849DiVA: diva2:939842
Subject / course
Mathematics
Educational program
Master of Science - Mathematics
Supervisors
Examiners
Available from: 2016-06-20 Created: 2016-06-20 Last updated: 2016-06-20Bibliographically approved

Open Access in DiVA

fulltext(755 kB)130 downloads
File information
File name FULLTEXT01.pdfFile size 755 kBChecksum SHA-512
e0877a643bc5dfec255f121ecf0b99f6c7db76fec2ea32a495fcd7377bd07c1d639f3f05b69ab82eb96b75ac6be5f96a3bf37becfff3dc6a5c029d7a47e48941
Type fulltextMimetype application/pdf

By organisation
Mathematics (Div.)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 130 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 912 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf