In this work we study the framework of mathematical morphology on simplicial complex spaces. Simplicial complexes are a versatile and widely used structure to represent multidimensional data, such as meshes, that are tridimensional complexes, or graphs, that can be interpreted as bidimensional complexes. Mathematical morphology is one of the most powerful frameworks for image processing, including the processing of digital structures, and is heavily used for many applications. However, mathematical morphology operators on simplicial complex spaces is not a concept fully developped in the literature. In this work, we review some classical operators from simplicial complexes under the light of mathematical morphology, to show that they are morphology operators. We define some basic lattices and operators acting on these lattices: dilations, erosions, openings, closings and alternating sequential filters, including their extension to weighted simplexes. However, the main contributions of this work are what we called dimensional operators, small, versatile operators that can be used to define new operators on simplicial complexes, while mantaining properties from mathematical morphology. These operators can also be used to express virtually any operator from the literature. We illustrate all the defined operators and compare the alternating sequential filters against filters defined in the literature, where our filters show better results for removal of small, intense, noise from binary images

Title: Algebraic Substructures in ℂ Author: Vítězslav Kala Department: Department of Algebra Supervisor: Prof. RNDr. Tomáš Kepka, DrSc., Department of Algebra Abstract: We study the structure of finitely generated semirings, parasemifields and other algebraic structures, developing and applying tools based on the geom- etry of algebraic substructures of the Euclidean space ℂ . To a parasemifield which is finitely generated as a semiring we attach a certain subsemigroup of the semigroup ℕ0 (defined using elements such that + = for some ∈ and ∈ ℕ). Algebraic and geometric properties of carry important structural information about ; we use them to show that if a parasemifield is 2-generated as a semiring, then it is additively idempotent. We also provide a ring-theoretic reformulation of this conjecture in the case of -generated semirings. We also classify all additively idempotent parasemifields which are finitely gen- erated as semirings by using the fact that they correspond to certain finitely generated unital lattice ordered groups. Busaniche, Cabrer, and Mundici [4] re- cently classified these using the combinatorial and geometric notion of a stellar sequence which is a sequences of certain simplicial complexes in [0, 1] . We use their results to prove that each such parasemifield is a finite product of...

In the realm of ever increasing data volume and traffic the processing of data as a stream is key in order to build flexible and scalable data processing engines. On-line machine learning provides powerful algorithms for extracting predictive models from such data streams even if the modeled relation is time-variant in nature. The modeling of real valued data in on-line regression tasks is especially important as it connects to modeling and system identification tasks in engineering domains and bridges to other fields of machine learning like classification and reinforcement learning. Therefore, this thesis considers the problem of on-line regression on time variant data streams and introduces a new multi resolution perspective for tackling it. The proposed incremental learning system, called AS-MRA, comprises a new interpolation scheme for symmetric simplicial input segmentations, a layered approximation structure of sequential local refinement layers and a learning architecture for efficiently training the layer structure. A key concept for making these components work together in harmony is a differential parameter encoding between subsequent refinement layers which allows to decompose the target function into independent additional components represented as individual refinement layers. The whole AS-MRA approach is designed to form a smooth approximation while having its computational demands scaling linearly towards the input dimension and the overall expressiveness and therefore potential storage demands scaling exponentially towards input dimension. The AS-MRA provides no mandatory design parameters, but offers opportunities for the user to state tolerance parameters for the expected prediction performance which automatically and adaptively shape the resulting layer structure during the learning process. Other optional design parameters allow to restrict the resource consumption with respect to computational and memory demands. The effect of these parameters and the learning behavior of the AS-MRA as such are investigated with respect to various learning issues and compared to different related on-line learning approaches. The merits and contributions of the AS-MRA are experimentally shown and linked to general considerations about the relation between key concepts of the AS-MRA and fundamental results in machine learning.

Homologie simpliciale est un outil très efficace pour accéder à des informations importantes sur la topologie des réseaux sans fil, tels que : la couverture et la connectivité. Dans cette thèse, nous modélisons le réseau sans fil comme un déploiement aléatoire des cellules. Tout d’abord, nous introduisons un algorithme pour construire le complexe de Cech, qui décrit exactement la topologie du réseau. Ensuite, ˇ le complexe de Cech est utilisé dans des applications avancées. La première application est d’économiser ˇ l’énergie de transmission pour les réseaux sans fil. Cette application non seulement maximise la couverture de le réseau, mais réduit également la puissance de transmission. En même temps, la couverture et la puissance de transmission sont optimisées. La deuxième application est pour équilibrer la charge de trafic dans les réseaux sans fil. Cette application contrôle la puissance de transmission de chaque cellule dans le réseau, toujours sous contrainte de couverture. Avec la puissance d’émission contrôlée, les utilisateurs sont redirigés vers des cellules de charge plus faibles. Par conséquent, la charge du trafic est répartie entre lesdifférentes cellules. / Simplicial homology is a useful tool to access important information about the topology of wireless networks such as : coverage and connectivity. In this thesis, we model the wireless network as a random deployment of cells. Firstly, we introduce an algorithm to construct the Cech complex, which describes exactly the topology of the network. Then, the Cech complex is used in further applications. The first application is to save transmission power for wireless networks. This application not only maximizes the coverage of the network but also minimizes its transmission power. At the same time, the coverage and the transmission power are optimized. The second application is to balance the traffic load in wireless networks. This application controls the transmission power of each cell in the network, always under the coverage constraint. With the controlled transmission power, the users are redirected to connect to the lower traffic load cells. Consequentially, the balanced traffic load is obtained for the network.

No description available.

No description available.

This thesis is comprised of three parts. The first part describes a novel framework for computing importance measures on graph vertices. The concept of a D-spectrum is introduced, based on vertex ranks within certain chains of nested sub-graphs. We show that the D- spectrum integrates the degree distribution and coreness information of the graph as two particular such chains. We prove that these spectra are realized as fixed points of certain monotone and contractive SDSs we call t-systems. Finally, we give a vertex deletion algorithm that efficiently computes D-spectra, and we illustrate their correlation with stochastic SIR-processes on real world networks. The second part deals with the topology of the intersection nerve for a bi-secondary structure, and its singular homology. A bi-secondary structure R, is a combinatorial object that can be viewed as a collection of cycles (loops) of certain at most tetravalent planar graphs. Bi-secondary structures arise naturally in the study of RNA riboswitches - molecules that have an MFE binary structural degeneracy. We prove that this loop nerve complex has a euclidean 3-space embedding characterized solely by H2(R), its second homology group. We show that this group is the only non-trivial one in the sequence and furthermore it is free abelian. The third part further describes the features of the loop nerve. We identify certain disjoint objects in the structure of R which we call crossing components (CC). These are non-trivial connected components of a graph that captures a particular non-planar embedding of R. We show that each CC contributes a unique generator to H2(R) and thus the total number of these crossing components in fact equals the rank of the second homology group. / Doctor of Philosophy / This Thesis is divided into three parts. The first part describes a novel mathematical framework for decomposing a real world network into layers. A network is comprised of interconnected nodes and can model anything from transportation of goods to the way the internet is organized. Two key numbers describe the local and global features of a network: the number of neighbors, and the number of neighbors in a certain layer, a node has. Our work shows that there are other numbers in-between the two, that better characterize a node. We also give explicit means of computing them. Finally, we show that these numbers are connected to the way information spreads on the network, uncovering a relation between the network’s structure and dynamics on said network. The last two parts of the thesis have a common theme and study the same mathematical object. In the first part of the two, we provide a new model for the way riboswtiches organize themselves. Riboswitches, are RNA molecules within a cell, that can take two mutually opposite conformations, depending on what function they need to perform within said cell. They are important from an evolutionary standpoint and are actively studied within that context, usually being modeled as networks. Our model captures the shapes of the two possible conformations, and encodes it within a mathematical object called a topological space. Once this is done, we prove that certain numbers that are attached to all topological spaces carry specific values for riboswitches. Namely, we show that the shapes of the two possible conformations for a riboswich are always characterized by a single integer. In the last part of the Thesis we identify what exactly in the structure of riboswitches contributes to this number being large or small. We prove that the more tangled the two conformations are, the larger the number. We can thus conclude that this number is directly proportional to how complex the riboswitch is.

Variational Auto-Encoders (VAEs) are one of the most famous deep generative models. After showing that standard VAEs may not preserve the topology, that is the shape of the data, between the input and the latent space, we tried to modify them so that the topology is preserved. This would help in particular for performing interpolations in the latent space. Our main contribution is two folds. Firstly, we propose successfully the InvMap-VAE which is a simple way to turn any dimensionality reduction technique, given its embedding, into a generative model within a VAE framework providing an inverse mapping, with all the advantages that this implies. Secondly, we propose the Witness Simplicial VAE as an extension of the Simplicial Auto-Encoder to the variational setup using a Witness Complex for computing a simplicial regularization. The Witness Simplicial VAE is independent of any dimensionality reduction technique and seems to better preserve the persistent Betti numbers of a data set than a standard VAE, although it would still need some further improvements. Finally, the two first chapters of this master thesis can also be used as an introduction to Topological Data Analysis, General Topology and Computational Topology (or Algorithmic Topology), for any machine learning student, engineer or researcher interested in these areas with no background in topology. / Variations autokodare (VAE) är en av de mest kända djupa generativa modellerna. Efter att ha visat att standard VAE inte nödvändigtvis bevarar topologiska egenskaper, det vill säga formen på datan, mellan inmatningsdatan och det latenta rummet, försökte vi modifiera den så att topologin är bevarad. Det här skulle i synnerhet underlätta när man genomför interpolering i det latenta rummet. Denna avhandling består av två centrala bidrag. I första hand så utvecklar vi InvMap-VAE, som är en enkel metod att omvandla vilken metod inom dimensionalitetsreducering, givet dess inbäddning, till en generativ modell inom VAE ramverket, vilket ger en invers avbildning och dess tillhörande fördelar. För det andra så presenterar vi Witness Simplicial VAE som en förlängning av en Simplicial Auto-Encoder till dess variationella variant genom att använda ett vittneskomplex för att beräkna en simpliciel regularisering. Witness Simplicial VAE är oberoende av dimensionalitets reducerings teknik och verkar bättre bevara Betti-nummer av ett dataset än en vanlig VAE, även om det finns utrymme för förbättring. Slutligen så kan de första två kapitlena av detta examensarbete också användas som en introduktion till Topologisk Data Analys, Allmän Topologi och Beräkningstopologi (eller Algoritmisk Topologi) till vilken maskininlärnings student, ingenjör eller forskare som är intresserad av dessa ämnesområden men saknar bakgrund i topologi.

In this dissertation we first study partition posets and their topology. For each composition c we show that the order complex of the poset of pointed set partitions is a wedge of spheres of the same dimension with the multiplicity given by the number of permutations with descent composition c. Furthermore, the action of the symmetric group on the top homology is isomorphic to the Specht module of a border strip associated to the composition. We also study the filter of pointed set partitions generated by knapsack integer partitions. In the second half of this dissertation we study descent avoidance in permutations. We extend the notion of consecutive pattern avoidance to considering sums over all permutations where each term is a product of weights depending on each consecutive pattern of a fixed length. We study the problem of finding the asymptotics of these sums. Our technique is to extend the spectral method of Ehrenborg, Kitaev and Perry. When the weight depends on the descent pattern, we show how to find the equation determining the spectrum. We give two length 4 applications, and a weighted pattern of length 3 where the associated operator only has one non-zero eigenvalue. Using generating functions we show that the error term in the asymptotic expression is the smallest possible.

Soit G un groupe de présentation finie. Un résultat de Gromov affirme l'existence de cycles géométriques réguliers qui représentent une classe d'homologie non nulle h dans le énième groupe d'homologie à coefficients entiers de G, cycles géométriques dont le volume systolique est aussi proche que souhaité du volume systolique de h. Ce théorème, dont aucune démonstration exhaustive n'avait été faite, a servi à obtenir plusieurs résultats importants en géométrie systolique. La première partie de cette thèse est consacrée à une démonstration complète de ce résultat. L'utilisation de ces cycles géométriques réguliers est connue sous le nom de technique de régularisation. Cette technique permet notamment de relier le volume systolique de certaines variétés fermées à d'autres invariants topologiques de ces variétés, tels que les nombres de Betti ou l'entropie minimale. La seconde partie de cette thèse propose d'examiner ces relations, et la mise en oeuvre de la technique de régularisation.La troisième partie est consacrée à trois problèmes liés à la géométrie systolique. Dans un premier temps on s'intéresse à une inégalité concernant les tores pleins plongés dans l'espace tridimensionnel. Puis, on s'intéresse ensuite aux triangulations minimales des surfaces compactes, afin d'obtenir des informations sur le volume systolique de ces surfaces. Enfin, on présente la notion de complexité simpliciale d'un groupe de présentation finie, et ses liens avec la géométrie systolique. / Let G be a finitely presented group. A theorem of Gromov asserts the existence of regular geometric cycles which represent a non null homology class h in the nth homology group with integral coefficients of G, geometric cycles which have a systolic volume as close as desired to the systolic volume of h. This theorem, of which no complete proof has been given, has lead to major results in systolic geometry. The first part of this thesis is devoted to a complete proof of this result.The regularizationtechnique consists in the use of these regular geometric cycles to obtain information about the class $h$. This technique allows to link the systolic volume of some closed manifolds to homotopical invariants of these manifolds, such as the minimal entropy and the Betti numbers. The second part of this thesis proposes to investigate these links.The third part of this thesis is devoted to three problems of systolic geometry. First we are investigating an inequality about embeded tori in $R^3$. Second, we are looking into minimal triangulations of compact surfaces and some information they can provide in systolic geometry. And finally, we are presenting the notion of simplicial complexity of a finitely-presented group and its links with the systolic geometry.