Submitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2014-08-29T18:40:14Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) DissertaçãofinalMarcostulio.pdf: 1325302 bytes, checksum: 282aebfee90d1ca1fcbbe83021300b0f (MD5) / Made available in DSpace on 2014-08-29T18:40:14Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) DissertaçãofinalMarcostulio.pdf: 1325302 bytes, checksum: 282aebfee90d1ca1fcbbe83021300b0f (MD5) Previous issue date: 2014-02-25 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / Inthiswork,basedonthearticlesMariaLuízaLeiteandOscasPalmas,wepresentedthe classificationofthecompleterotationhypersurfaceswithconstantscalarcurvature,inRn eHn withn>3. / Neste trabalho, baseado nos artigos de Maria Luíza Leite e Oscas Palmas, classificamos as hipersuperfícies de rotação completas, com curvatura escalar constante, emRn eHn comn>3.

Le résultat principal est une caractérisation homotopique des orbifolds de dimension 3 qui sont fibrés de Seifert : si O est un orbifold de dimension 3 fermé, orientable et petit dont le groupe fondamental admet un sous-groupe infini cyclique normal, alors O est de Seifert. Ce théorème généralise un résultat de Scott, Mess, Tukia, Gabai et Casson-Jungreis pour les variétés. Il repose sur une caractérisation des groupes de surfaces virtuels comme groupes quasi-isométriques à un plan riemannien complet. D'autres résultats sur les quasi-isométries entre groupes et surfaces sont obtenus.

Non-rigid shapes are generally known as objects whose three dimensional geometry may deform by internal and/or external forces. Deformable shapes are all around us, ranging from protein molecules, to natural objects such as the trees in the forest or the fruits in our gardens, and even human bodies. Two deformable shapes may be related by isometry, which means their intrinsic geometries are preserved, even though their extrinsic geometries are dissimilar. An important problem in the analysis of the deformable shapes is to identify the three-dimensional correspondence between two isometric shapes, given that the two shapes may be deviated from isometry by intrinsic distortions. A major challenge is that non-rigid shapes have large degrees of freedom on how to deform. Nevertheless, irrespective of how they are deformed, they may be aligned such that the geodesic distance between two arbitrary points on two shapes are nearly equal. Such alignment may be expressed by a permutation matrix (a matrix with binary entries) that corresponds to every paired geodesic distance in between the two shapes. The alignment involves searching the space over all possible mappings (that is all the permutations) to locate the one that minimizes the amount of deviation from isometry. A brute-force search to locate the correspondence is not computationally feasible. This thesis introduces a novel approach created to locate such correspondences, in spite of the large solution space that encompasses all possible mappings and the presence of intrinsic distortion. In order to find correspondences between two shapes, the first step is to create a suitable descriptor to accurately describe the deformable shapes. To this end, we developed deformation-invariant metric descriptors. A descriptor constitutes pair-wise geodesic distances among arbitrary number of discrete points that represent the topology of the non-rigid shape. Our descriptor provides isometric-invariant representation of the shape irrespective of its circumstantial deformation. Two isometric-invariant descriptors, representing two candidate deformable shapes, are the input parameters to our optimization algorithm. We then proceed to locate the permutation matrix that aligns the two descriptors, that minimizes the deviation from isometry. Once we have developed such a descriptor, we turn our attention to finding correspondences between non deformable shapes. In this study, we investigate the use of both classical and quantum particle swarm optimization (PSO) algorithms for this task. To explore the merits of variants of PSO, integer optimization involving test functions with large dimensions were performed, and the results and the analysis suggest that quantum PSO is more effective optimization method than its classical PSO counterpart. Further, a scheme is proposed to structure the solution space, composed of permutation matrices, in lexicographic ordering. The search in the solution space is accordingly simplified to integer optimization to find the integer rank of the targeted permutation matrix. Empirical results suggest that this scheme improves the scalability of quantum PSO across large solution spaces. Yet, quantum PSO's global search capability requires assistance in order to more effectively manoeuvre through the local extrema prevalent in the large solution spaces. A mutation based genetic algorithm (GA) is employed to augment the search diversity of quantum PSO when/if the swarm stagnates among the local extrema. The mutation based GA instantly disengages the optimization engine from the local extrema in order to reorient the optimization energy to the trajectories that steer to the global extrema, or the targeted permutation matrix. Our resultant optimization algorithm combines quantum Particle Swarm Optimization (PSO) and mutation based Genetic Algorithm (GA). Empirical results show that the optimization method presented is scalable and efficient on standard hardware across different solution space sizes. The performance of the optimization method, in simulations and on various near-isometric shapes, is discussed. In all cases investigated, the method could successfully identify the correspondence among the non-rigid deformable shapes that were related by isometry.

The size of data generated every year follows an exponential growth. The number of data points as well as the dimensions have increased dramatically the past 15 years. The gap between the demand from the industry in data processing and the solutions provided by the machine learning community is increasing. Despite the growth in memory and computational power, advanced statistical processing on the order of gigabytes is beyond any possibility. Most sophisticated Machine Learning algorithms require at least quadratic complexity. With the current computer model architecture, algorithms with higher complexity than linear O(N) or O(N logN) are not considered practical. Dimensionality reduction is a challenging problem in machine learning. Often data represented as multidimensional points happen to have high dimensionality. It turns out that the information they carry can be expressed with much less dimensions. Moreover the reduced dimensions of the data can have better interpretability than the original ones. There is a great variety of dimensionality reduction algorithms under the theory of Manifold Learning. Most of the methods such as Isomap, Local Linear Embedding, Local Tangent Space Alignment, Diffusion Maps etc. have been extensively studied under the framework of Kernel Principal Component Analysis (KPCA). In this dissertation we study two current state of the art dimensionality reduction methods, Maximum Variance Unfolding (MVU) and Non-Negative Matrix Factorization (NMF). These two dimensionality reduction methods do not fit under the umbrella of Kernel PCA. MVU is cast as a Semidefinite Program, a modern convex nonlinear optimization algorithm, that offers more flexibility and power compared to iv KPCA. Although MVU and NMF seem to be two disconnected problems, we show that there is a connection between them. Both are special cases of a general nonlinear factorization algorithm that we developed. Two aspects of the algorithms are of particular interest: computational complexity and interpretability. In other words computational complexity answers the question of how fast we can find the best solution of MVU/NMF for large data volumes. Since we are dealing with optimization programs, we need to find the global optimum. Global optimum is strongly connected with the convexity of the problem. Interpretability is strongly connected with local isometry1 that gives meaning in relationships between data points. Another aspect of interpretability is association of data with labeled information. The contributions of this thesis are the following: 1. MVU is modified so that it can scale more efficient. Results are shown on 1 million speech datasets. Limitations of the method are highlighted. 2. An algorithm for fast computations for the furthest neighbors is presented for the first time in the literature. 3. Construction of optimal kernels for Kernel Density Estimation with modern convex programming is presented. For the first time we show that the Leave One Cross Validation (LOOCV) function is quasi-concave. 4. For the first time NMF is formulated as a convex optimization problem 5. An algorithm for the problem of Completely Positive Matrix Factorization is presented. 6. A hybrid algorithm of MVU and NMF the isoNMF is presented combining advantages of both methods. 7. The Isometric Separation Maps (ISM) a variation of MVU that contains classification information is presented. 8. Large scale nonlinear dimensional analysis on the TIMIT speech database is performed. 9. A general nonlinear factorization algorithm is presented based on sequential convex programming. Despite the efforts to scale the proposed methods up to 1 million data points in reasonable time, the gap between the industrial demand and the current state of the art is still orders of magnitude wide.

Orientadores: Marcelo Firer, Luiz Antonio Barrera San Martin / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-05T23:33:46Z (GMT). No. of bitstreams: 1 Talpo_HumbertoLuiz_D.pdf: 1408389 bytes, checksum: b11f884cbf1e05f81138a8e91a5980dc (MD5) Previous issue date: 2006 / Resumo: Seja G uma árvore homogênea e Aut(G) seu grupo de automorfismos. Um automorfismo f Î Aut(G) é par se d(f(x),x) º0 mod 2 para todo vértice x Î G, onde d(.,.) é a função distância definida pelo comprimento do menor caminho ligando os vértices. O conjunto Aut+(G) de todos os automorfismos pares é um subgrupo de índice 2 em Aut(G). Definimos uma geodésica g Ì G como um subgrafo isomorfo a Z (onde Z é visto como um grafo que possui arestas unindo inteiros consecutivos). Uma reflexão em uma geodésica g é um automorfismo involutivo f (f² =1) tal que f(x) = x se, e somente se, x Î G. Denotamos por R o conjunto de todas as reflexões em geodésicas. Neste trabalho (Capítulo 2) provamos que, dada uma árvore homogênea de grau par G, o número de cobertura de Aut+(G) pelas reflexões em geodésicas é 11, no seguinte sentido: dado f Î Aut+(G) existem f1, f2,... fk com k £ 11, tais que f(x) = fk °fk-1°...°f1(x) para todo vértice x em G. Além disso, considerando árvores homogêneas, sabemos que o grupo de automorfismos é completo e o subgrupo de automorfismos pares é simples. Flexibilizamos a condição de homogeneidade e conseguimos demonstrar (Capítulo 3) para o caso de árvores semi-homogêneas, que o grupo de automorfismos é simples e completo / Abstract: Let G be a homogeneous tree and Aut(G) its group of automorphism. An automorphism Î Aut(G) is said to be even if d(f(x),x) º0 mod 2 for every vertex x Î G of , where d(.,.) is the canonical distance function defined by the minimum length of paths connecting the vertices. The set Aut+(G) of all even automorphism is a subgroup of index 2 in Aut(G). We define a geodesic g Ì G as a subtree isomorphic to the standard tree of the integers Z, that is, a homogeneous subtree of degree 2. A reflection in a geodesic g is an involutive automorphism f (f² =1) such that f(x) = x if x Î G. We denote by R the set of all reflections in geodesics. In this work (Chapter 2) we prove that, for every even degree tree G, the covering number of Aut+(G) by reflections in geodesics is 11, in the sense that give f Î Aut+(G) there are f1, f2,... fk with k £ 11, such that f(x) = fk °fk-1°...°f1(x) for every vertex x in G.Moreover, if we consider homogeneous trees we know that automorphisms group is complete and the even automorphisms subgroup is simple. We vary the homogeneous condition and we prove that (Chapter 3) for the semi-homogeneous trees, the automorphisms group is simple and complete / Doutorado / Doutor em Matemática

Les travaux présentés dans ce mémoire concernent les réseaux, qui sont des objets mathématiques fondamentaux pour de nombreux domaines tel que théorie des nombres et la cryptographie.Nous proposons dans un premier temps une généralisation et une implantation de l'algorithme de réduction de Lenstra, Lenstra et Lov'asz (algorithme LLL) dans le cadre algébrique simple des réseaux sur les anneaux d'entiers quadratiques, imaginaires et euclidiens.Nous nous attachons ensuite à présenter les notions de réseaux algébriques et de formes de Humbert, qui sont des généralisations dans un cadre algébrique aussi large que possible des notions classiques de réseaux euclidiens et de formes quadratiques. L'introduction de ces objets nous permet de présenter une adaptation et une implantation de l'algorithme de Plesken et Souvignier permettant de traiter efficacement les problèmes de l'isométrie et de la détermination des automorphismes pour les réseaux algébriques.Nous proposons finalement une étude détaillée de la complexité de ces deux problèmes. Nous montrons notamment qu'ils sont intiment reliés à des problèmes similaires sur les graphes. Cette réduction nous permet d'exhiber des bornes de complexité inédites. / This thesis deals with lattices, which are fundamental objects in many fields, such as number theory and cryptography.As a first step, we propose a generalization and an implantation of the Lenstra, Lenstra and Lov'asz algorithm (LLL algorithm) in the simple algebraic setting of lattices over quadratic imaginary and euclidean ring of integers.Then, we present the notions of algebraic lattices and Humbert forms, which are extensions of euclidean lattices and quadratic forms in a large algebraic setting. Introducing these objects leads us to develop and implant modifications of the Plesken and Souvignier algorithm. This algorithm efficiently solves the isometric lattices problem and the automorphism group computation problem for algebraic lattices.Eventually, we analyze in depth the complexity of this two algorithmic problems. We show that they are intimately related to similar problems on graphs. This reduction leads us to express unprecedented complexity bounds.

Non-rigid shapes are generally known as objects whose three dimensional geometry may deform by internal and/or external forces. Deformable shapes are all around us, ranging from protein molecules, to natural objects such as the trees in the forest or the fruits in our gardens, and even human bodies. Two deformable shapes may be related by isometry, which means their intrinsic geometries are preserved, even though their extrinsic geometries are dissimilar. An important problem in the analysis of the deformable shapes is to identify the three-dimensional correspondence between two isometric shapes, given that the two shapes may be deviated from isometry by intrinsic distortions. A major challenge is that non-rigid shapes have large degrees of freedom on how to deform. Nevertheless, irrespective of how they are deformed, they may be aligned such that the geodesic distance between two arbitrary points on two shapes are nearly equal. Such alignment may be expressed by a permutation matrix (a matrix with binary entries) that corresponds to every paired geodesic distance in between the two shapes. The alignment involves searching the space over all possible mappings (that is all the permutations) to locate the one that minimizes the amount of deviation from isometry. A brute-force search to locate the correspondence is not computationally feasible. This thesis introduces a novel approach created to locate such correspondences, in spite of the large solution space that encompasses all possible mappings and the presence of intrinsic distortion. In order to find correspondences between two shapes, the first step is to create a suitable descriptor to accurately describe the deformable shapes. To this end, we developed deformation-invariant metric descriptors. A descriptor constitutes pair-wise geodesic distances among arbitrary number of discrete points that represent the topology of the non-rigid shape. Our descriptor provides isometric-invariant representation of the shape irrespective of its circumstantial deformation. Two isometric-invariant descriptors, representing two candidate deformable shapes, are the input parameters to our optimization algorithm. We then proceed to locate the permutation matrix that aligns the two descriptors, that minimizes the deviation from isometry. Once we have developed such a descriptor, we turn our attention to finding correspondences between non deformable shapes. In this study, we investigate the use of both classical and quantum particle swarm optimization (PSO) algorithms for this task. To explore the merits of variants of PSO, integer optimization involving test functions with large dimensions were performed, and the results and the analysis suggest that quantum PSO is more effective optimization method than its classical PSO counterpart. Further, a scheme is proposed to structure the solution space, composed of permutation matrices, in lexicographic ordering. The search in the solution space is accordingly simplified to integer optimization to find the integer rank of the targeted permutation matrix. Empirical results suggest that this scheme improves the scalability of quantum PSO across large solution spaces. Yet, quantum PSO's global search capability requires assistance in order to more effectively manoeuvre through the local extrema prevalent in the large solution spaces. A mutation based genetic algorithm (GA) is employed to augment the search diversity of quantum PSO when/if the swarm stagnates among the local extrema. The mutation based GA instantly disengages the optimization engine from the local extrema in order to reorient the optimization energy to the trajectories that steer to the global extrema, or the targeted permutation matrix. Our resultant optimization algorithm combines quantum Particle Swarm Optimization (PSO) and mutation based Genetic Algorithm (GA). Empirical results show that the optimization method presented is scalable and efficient on standard hardware across different solution space sizes. The performance of the optimization method, in simulations and on various near-isometric shapes, is discussed. In all cases investigated, the method could successfully identify the correspondence among the non-rigid deformable shapes that were related by isometry.

Quantitative traits are an important part of tardigrade taxonomy for both heterotardigrades and eutardigrades. Because most quantitative traits vary as a function of body size, variation in body size complicates comparisons between individuals or populations. Thus, body size effects must be eliminated in morphometric analysis. Although ratios (size of character/body size) are often used to attempt this, they only work for the specific case of isometry (i.e. when a structure grows proportionally to body size). Ratios do not eliminate body size effects for allometric (disproportionate) growth. In eutardigrades, body size is highly correlated with the length of the rigid buccal tube, whereas body length (BL) is highly variable because of the flexibility of the cuticle and the orientation and coverslip pressure on the specimen. In heterotardigrades, BL is typically used to indicate body size because the thickened dorsal plates provide more rigidity and reliability in measurements. We measured 27 traits in 97 specimens of Paramacrobiotus tonollii (Eutardigrada) and 14 traits in 100 specimens of Echiniscus virginicus (Heterotardigrada) and found that many traits are allometric rather than isometric. Thorpe (1975, Biol J Linn Soc 7:27) provided a normalization technique to eliminate body size effects for any trait regardless of its relationship to body size. Using the data from P. tonollii, we show that Thorpe's size normalization does successfully remove buccal tube length effects (body size effects), while pt indices generally do not. We also demonstrate the effectiveness of Thorpe's normalization in species delineations of Macrobiotus recens and Macrobiotus hufelandi, two species that differ primarily in a few quantitative traits and overall body size in addition to the eggs. Based on these examples, we propose that the allometric exponent (b) and the Y-intercept (a*) of the regression of Thorpe normalized traits versus body size are valuable metrics in tardigrade systematics.

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第20886号 / 理博第4338号 / 新制||理||1623(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 長谷川 真人, 教授 向井 茂, 准教授 照井 一成 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

<p>This thesis consists of four papers, all concerning random iteration of isometries. The papers are:</p><p>I. Ambroladze A, Ådahl M, Random iteration of isometries in unbounded metric spaces. Nonlinearity 16 (2003) 1107-1117.</p><p>II. Ådahl M, Random iteration of isometries controlled by a Markov chain. Manuscript.</p><p>III. Ådahl M, Melbourne I, Nicol M, Random iteration of Euclidean isometries. Nonlinearity 16 (2003) 977-987.</p><p>IV. Johansson A, Ådahl M, Recurrence of a perturbed random walk and an iterated function system depending on a parameter. Manuscript.</p><p>In the first paper we consider an iterated function system consisting of isometries on an unbounded metric space. Under suitable conditions it is proved that the random orbit {<i>Z</i>n} ^∞_n=0, of the iterations corresponding to an initial point Z₀, “escapes to infinity" in the sense that <i>P</i>(<i>Z</i>n Є <i>K)</i> → 0, as <i>n</i> → ∞ for every bounded set <i>K</i>. As an application we prove the corresponding result in the Euclidean and hyperbolic spaces under the condition that the isometries do not have a common fixed point.</p><p>In the second paper we let a Markov chain control the random orbit of an iterated function system of isometries on an unbounded metric space. We prove under necessary conditions that the random orbit \escapes to infinity" and we also give a simple geometric description of these conditions in the Euclidean and hyperbolic spaces. The results generalises the results of Paper I.</p><p>In the third paper we consider the statistical behaviour of the reversed random orbit corresponding to an iterated function system consisting of a finite number of Euclidean isometries of <b>R</b>n. We give a new proof of the central limit theorem and weak invariance principles, and we obtain the law of the iterated logarithm. Our results generalise immediately to Markov chains. Our proofs are based on dynamical systems theory rather than a purely probabilistic approach.</p><p>In the fourth paper we obtain a suficient condition for the recurrence of a perturbed (one-sided) random walk on the real line. We apply this result to the study of an iterated function system depending on a parameter and defined on the open unit disk in the complex plane. </p>