Montréal Trigonix inc. 2018

No description available.

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.

Cette thèse s'articule autour de deux thèmes : une transformation de B(H) introduite par Aluthge et la méthode d'Ansari-Enflo. La première partie fait l'objet de l'étude de la transformation d'Aluthge qui a eu un impact important ces dernières années en théorie des opérateurs. Des résultats optimaux sur la stabilité d'un certain nombre de classes d'opérateurs, telles que la classe des isométries partielles et les classes associées au comportement asymptotique d'un opérateur, sont fournis. Nous étudions également l'évolution d'invariants opératoriels, tels que le polynôme minimal, la fonction minimum, l'ascente et la descente, sous l'action de la transformation ; nous comparons plus précisément les suites des noyaux et images relatives aux itérés d'un opérateur et de sa transformée de Aluthge. La deuxième partie est l'occasion d'étudier la théorie d'Ansari-Enflo, qui a permis de gros progrès pour le problème du sous-espace hyper-invariant. Nous développons plus particulièrement la notion fondatrice de la méthode, celle de vecteur extrémal. La localisation et une nouvelle caractérisation de ces vecteurs sont données. Leur régularité et leur robustesse, au regard de différents paramètres, sont éprouvées. Enfin, nous comparons les vecteurs extrémaux d'un shift à poids et ceux associés à sa transformée d'Aluthge. Cette étude aboutit à la construction d'une suite de vecteurs extrémaux associés aux itérés de la transformation d'Aluthge, pour laquelle certaines propriétés sont mises en évidence.

Ce mémoire d'habilitation comporte deux parties. Dans la première, nous étudions une famille de mesures de probabilité construite à partir de la loi du mouvement brownien via une procédure appelée pénalisation. Nous expliquons une partie des résultats obtenus par la construction d'une mesure sigma-finie, que nous généralisons ensuite à d'autres contextes. Dans la deuxième partie, nous étudions des objets infini-dimensionnels associés à des modèles de matrices aléatoires.

Cette thèse s'articule autour de deux thèmes : une transformation de B(H) introduite par Aluthge et la méthode d'Ansari-Enflo. La première partie fait l'objet de l'étude de la transformation d’Aluthge qui a eu un impact important ces dernières années en théorie des opérateurs. Des résultats optimaux sur la stabilité d'un certain nombre de classes d'opérateurs, telles que la classe des isométries partielles et les classes associées au comportement asymptotique d'un opérateur, sont fournis. Nous étudions également l'évolution d'invariants opératoriels, tels que le polynôme minimal, la fonction minimum, l'ascente et la descente, sous l'action de la transformation ; nous comparons plus précisément les suites des noyaux et images relatives aux itérés d'un opérateur et de sa transformée de Aluthge. La deuxième partie est l'occasion d'étudier la théorie d'Ansari-Enflo, qui a permis de gros progrès pour le problème du sous-espace hyper-invariant. Nous développons plus particulièrement la notion fondatrice de la méthode, celle de vecteur extrémal. La localisation et une nouvelle caractérisation de ces vecteurs sont données. Leur régularité et leur robustesse, au regard de différents paramètres, sont éprouvées. Enfin, nous comparons les vecteurs extrémaux d'un shift à poids et ceux associés à sa transformée d’Aluthge. Cette étude aboutit à la construction d'une suite de vecteurs extrémaux associés aux itérés de la transformation d’Aluthge, pour laquelle certaines propriétés sont mises en évidence. / This thesis is based on two topics : a transformation of B(H) introduced by Aluthge and the Ansari-Enflo method. In the first part, we study the Aluthge transformation which really had an impact on operator theory in the past ten years. Some optimal results about stability for several operators classes, such as isometries class and classes of operators defined by their asymptotic behaviour, are given. We also study changes generated by Aluthge transform about some usual tools in operator theory like minimum polynomial, minimum function, ascent and descent ; precisely, we compare iterated kernels and iterated ranges sequences related to an operator and to its Aluthge transform. The second part is devoted to the study of the Ansari-Enflo theory, which allowed to make progress in the hyper-invariant subspace problem. We develop the notion of extremal vectors which is the fundamental point of the theory. We clarify their spatial localization and a new caracterisation for these vectors is given. Regularity and robustness with regard to different parameters are tried and tested. Finally, we compare extremal vectors associated with weighted shifts and the one corresponding to their Aluthge transform. This study leads to build a sequence of extremal vectors associated with the iterated Aluthge transform, for which we highlight several properties.

Dans cette thèse, nous considérons les chemins possibles pour donner une mesure quantitative du fait que deux espaces ne sont pas quasi-isométriques. De ce point de vue quantitatif, on reprend la définition de quasi-isométrie et on propose une notion de “croissance de distorsion quasi-isométrique” entre deux espaces métriques. Nous révisons notre article [32] où une borne supérieure optimale pour le lemme de Morse est donnée, avec la variante duale que nous appelons Anti-Morse Lemma, et leurs applications.Ensuite, nous nous concentrons sur des bornes inférieures sur la croissance de distorsion quasi-isométrique pour des espaces métriques hyperboliques. Dans cette classe, les espaces de $L^p$-cohomologie fournissent des invariants de quasi-isométrie utiles et les constantes de Poincaré des boules sont leur incarnation quantitative. Nous étudions comment les constantes de Poincaré sont transportées par quasi-isométries. Dans ce but, nous introduisons la notion de transnoyau. Nous calculons les constantes de Poincaré pour les métriques localement homogènes de la forme $dt^2+\sum_ie^{2\mu_it}dx_i^2$, et donnons une borne inférieure sur la croissance de distorsion quasi-isométrique entre ces espaces.Cela nous permet de donner des exemples présentant différents type de croissance de distorsion quasi-isométrique, y compris un exemple sous-linéaire (logarithmique). / In this thesis we discuss possible ways to give quantitative measurement for two spaces not being quasi-isometric. From this quantitative point of view, we reconsider the definition of quasi-isometries and propose a notion of ``quasi-isometric distortion growth'' between two metric spaces. We revise our article [32] where an optimal upper-bound for Morse Lemma is given, together with the dual variant which we call Anti-Morse Lemma, and their applications.Next, we focus on lower bounds on quasi-isometric distortion growth for hyperbolic metric spaces. In this class, $L^p$-cohomology spaces provides useful quasi-isometry invariants and Poincar\'e constants of balls are their quantitative incarnation. We study how Poincar\'e constants are transported by quasi-isometries. For this, we introduce the notion of a cross-kernel. We calculate Poincar\'e constants for locally homogeneous metrics of the form $dt^2+\sum_ie^dx_i^2$, and give a lower bound on quasi-isometric distortion growth among such spaces.This allows us to give examples of different quasi-isometric distortion growths, including a sublinear one (logarithmic).

Le fameux Théorème d’Extension de MacWilliams affirme que, pour les codes classiques, toute isométrie deHamming linéaire d'un code linéaire se prolonge en une application monomiale. Cependant, pour les codeslinéaires sur les alphabets de module, l'existence d'un analogue du théorème d'extension n'est pas garantie.Autrement dit, il existe des codes linéaires sur certains alphabets de module dont les isométries de Hammingne sont pas toujours extensibles. Il en est de même pour un contexte plus général d'un alphabet de module munid'une fonction de poids arbitraire. Dans la présente thèse, nous prouvons des analogues du théorèmed'extension pour des codes construits sur des alphabets et fonctions de poids arbitraires. La propriétéd'extension est analysée notamment pour les codes de petite longueur sur un alphabet de module de matrices,les codes MDS généraux, ou encore les codes sur un alphabet de module muni de la composition de poidssymétrisée. Indépendamment de ce sujet, une classification des deux groupes des isométries des codescombinatoires est donnée. Les techniques développées dans la thèse sont prolongées aux cas des codesstabilisateurs quantiques et aux codes de Gabidulin dans le cadre de la métrique rang. / The famous MacWilliams Extension Theorem states that for classical codes each linear Hamming isometry ofa linear code extends to a monomial map. However, for linear codes over module alphabets an analogue of theextension theorem does not always exist. That is, there may exists a linear code over a module alphabet with anunextendable Hamming isometry. The same holds in a more general context of a module alphabet equippedwith a general weight function. Analogues of the extension theorem for different classes of codes, alphabetsand weights are proven in the present thesis. For instance, extension properties of the following codes arestudied: short codes over a matrix module alphabet, maximum distance separable codes, codes over a modulealphabet equipped with the symmetrized weight composition. As a separate result, a classification of twoisometry groups of combinatorial codes is given. The thesis also contains applications of the developedtechniques to quantum stabilizer codes and Gabidulin codes.

<p>Un code de permutations G(n,d) un sous-ensemble C de Sym(n) tel que la distance de Hamming D entre deux éléments de C est supérieure ou égale à d. Dans cette thèse, le groupe des isométries de (Sym(n),D) est déterminé et il est prouvé que ces isométries sont des automorphismes du schéma d'association induit sur Sym(n) par ses classes de conjugaison. Ceci mène, par programmation linéaire, à de nouveaux majorants de la taille maximale des G(n,d) pour n et d fixés et n compris entre 11 et 13. Des algorithmes de génération avec rejet d'objets isomorphes sont développés. Pour classer les G(n,d) non isométriques, des invariants ont été construits et leur efficacité étudiée. Tous les G(4,3) et les G(5,4) ont été engendrés à une isométrie près, il y en a respectivement 61 et 9445 (dont 139 sont maximaux et décrits explicitement). D’autres classes de G(n,d) sont étudiées.<p><p><p><p> <p><p><p><p>A permutation code G(n,d) is a subset C of Sym(n) such that the Hamming distance D between two elements of C is larger than or equal to d. In this thesis, we characterize the isometry group of the metric space (Sym(n),D) and we prove that these isometries are automorphisms of the association scheme induced on Sym(n) by the conjugacy classes. This leads, by linear programming, to new upper bounds for the maximal size of G(n,d) codes for n and d fixed and n between 11 and 13. We develop generating algorithms with rejection of isomorphic objects. In order to classify the G(n,d) codes up to isometry, we construct invariants and study their efficiency. We generate all G(4,3) and G(4,5)codes up to isometry; there are respectively 61 and 9445 of them. Precisely 139 out of the latter codes are maximal and explicitly described. We also study other classes of G(n,d)codes.<p><p><p><p> / Doctorat en sciences, Spécialisation mathématiques / info:eu-repo/semantics/nonPublished

La reconstruction 3D monoculaire déformable est le problème général d'estimation de forme 3D d'un objet déformable à partir d'images 2D. Plusieurs scénarios ont émergé : le Shape-from-Template (SfT) et le Non-Rigid Structure-from-Motion (NRSfM) sont deux approches qui ont été grandement étudiées pour leur applicabilité. La première utilise une seule image qui montre un objet se déformant et un patron (une forme 3D texturée de l'objet dans une pose de référence). La seconde n'utilise pas de patron, mais utilise plusieurs images et estime la forme 3D dans chaque image. Les deux approches s'appuient sur le mouvement de points de correspondances entre les images et sur des a priori de déformations, restreignant ainsi leur utilisation à des surfaces texturées qui se déforment de manière lisse. Cette thèse fait avancer l'état de l'art du SfT et du NRSfM dans deux directions. La première est l'étude du SfT dans le cas de patrons 1D (c’est-à-dire des courbes comme des cordes et des câbles). La seconde direction est le développement d'algorithmes de SfT et de NRSfM qui exploitent plusieurs indices visuels et qui résolvent des cas réels et complexes non-résolus précédemment. Nous considérons des déformations isométriques et reconstruisons la partie extérieure de l'objet. Les contributions techniques et scientifiques de cette thèse sont divisées en quatre parties.La première partie de cette thèse étudie le SfT curvilinéaire, qui est le cas du patron curvilinéaire plongé dans un espace 2D ou 3D. Nous proposons une analyse théorique approfondie et des solutions pratiques pour le SfT curvilinéaire. Malgré son apparente simplicité, le SfT curvilinéaire s'est avéré être un problème complexe : il ne peut pas être résolu à l'aide de solutions locales non-holonomes d'une équation différentielle ordinaire et ne possède pas de solution unique, mais un nombre fini de solutions ambiguës. Une contribution technique majeure est un algorithme basé sur notre théorie, qui génère toutes les solutions ambiguës. La deuxième partie de cette thèse traite d'une limitation des méthodes de SfT : la reconstruction de plis. Cette limitation vient de la parcimonie de la contrainte de mouvement et de la régularisation. Nous proposons deux contributions qui s'appuient sur un cadre de minimisation d'énergie non-convexe. Tout d'abord, nous complétons la contrainte de mouvement avec une contrainte robuste de bord. Ensuite, nous modélisons implicitement les plis à l'aide d'une représentation dense de la surface basée maillage et d'une contrainte robuste de lissage qui désactive automatiquement le lissage de la courbure sans connaître a priori la position des plis.La troisième partie de cette thèse est dédiée à une autre limitation du SfT : la reconstruction de surfaces peu texturées. Cette limitation vient de la difficulté d'obtenir des correspondances (parcimonieuses ou denses) sur des surfaces peu texturées. Comme l'ombrage révèle les détails sur des surfaces peu texturées, nous proposons de combiner l'ombrage avec le SfT. Nous présentons deux contributions. La première est une initialisation en cascade qui estime séquentiellement la déformation de la surface, l'illumination de la scène, la réponse de la caméra et enfin les albédos de la surface à partir d'images monoculaires où la surface se déforme. La seconde est l'intégration de l'ombrage à notre précédent cadre de minimisation d'énergie afin de raffiner simultanément les paramètres photométriques et de déformation.La dernière partie de cette thèse relâche la connaissance du patron et aborde deux limitations du NRSfM : la reconstruction de surfaces peu texturées avec des plis. Une contribution majeure est l'extension du second cadre d'optimisation pour la reconstruction conjointe de la forme 3D de la surface sur toutes les images d'entrée et des albédos de la surface sans en connaître un patron. / Monocular deformable 3D reconstruction is the general problem of recovering the 3D shape of a deformable object from monocular 2D images. Several scenarios have emerged: the Shape-from-Template (SfT) and the Non-Rigid Structure-from-Motion (NRSfM) are two approaches intensively studied for their practicability. The former uses a single image depicting the deforming object and a template (a textured 3D shape of this object in a reference pose). The latter does not use a template, but uses several images and recovers the 3D shape in each image. Both approaches rely on the motion of correspondences between the images and deformation priors, which restrict their use to well-textured surfaces which deform smoothly. This thesis advances the state-of-the-art in SfT and NRSfM in two main directions. The first direction is to study SfT for the case of 1D templates (i.e. curved, thin structures such as ropes and cables). The second direction is to develop algorithms in SfT and NRSfM that exploit multiple visual cues and can solve complex, real-world cases which were previously unsolved. We focus on isometric deformations and reconstruct the outer part of the object. The technical and scientific contributions of this thesis are divided into four parts. The first part of this thesis studies the case of a curvilinear template embedded in 2D or 3D space, referred to Curve SfT. We propose a thorough theoretical analysis and practical solutions for Curve SfT. Despite its apparent simplicity, Curve SfT appears to be a complex problem: it cannot be solved locally using exact non-holonomic partial differential equation and is only solvable up to a finite number of ambiguous solutions. A major technical contribution is a computational solution based on our theory, which generates all the ambiguous solutions.The second part of this thesis deals with a limitation of SfT methods: reconstructing creases. This is due to the sparsity of the motion constraint and regularization. We propose two contributions which rely on a non-convex energy minimization framework. First, we complement the motion constraint with a robust boundary contour constraint. Second, we implicitly model creases with a dense mesh-based surface representation and an associated robust smoothing constraint, which deactivates curvature smoothing automatically where needed, without knowing a priori the crease location. The third part of this thesis is dedicated to another limitation of SfT: reconstructing poorly-textured surfaces. This is due to correspondences which cannot be obtained so easily on poorly-textured surfaces (either sparse or dense). As shading reveals details on poorly-textured surfaces, we propose to combine shading and SfT. We have two contributions. The first is a cascaded initialization which estimates sequentially the surface's deformation, the scene illumination, the camera response and then the surface albedos from deformed monocular images. The second is to integrate shading to our previous energy minimization framework for simultaneously refining deformation and photometric parameters.The last part of this thesis relaxes the knowledge of the template and addresses two limitations of NRSfM: reconstructing poorly-textured surfaces with creases. Our major contribution is an extension of the second framework to recover jointly the 3D shapes of all input images and the surface albedos without any template.