Cette thèse est organisée en deux parties indépendantes. La première partie s'intéresse à l'estimation convexe de matrice en prenant en compte à la fois la parcimonie et le rang. Dans le contexte de graphes avec une structure de communautés, on suppose souvent que la matrice d'adjacence sous-jacente est diagonale par blocs dans une base appropriée. Cependant, de tels graphes possèdent généralement une matrice d'adjacente qui est aussi parcimonieuse, ce qui suggère que combiner parcimonie et range puisse permettre de modéliser ce type d'objet de manière plus fine. Nous proposons et étudions ainsi une pénalité convexe pour promouvoir parcimonie et rang faible simultanément. Même si l'hypothèse de rang faible permet de diminuer le sur-apprentissage en diminuant la capacité d'un modèle matriciel, il peut être souhaitable lorsque suffisamment de données sont disponible de ne pas introduire une telle hypothèse. Nous étudions un exemple dans le contexte multiple kernel learning localisé, où nous proposons une famille de méthodes a vaste-marge convexes et accompagnées d'une analyse théorique. La deuxième partie de cette thèse s'intéresse à des problèmes de détection d'objets ou de signaux structurés. Dans un premier temps, nous considérons un problème de test statistique, pour des modèles où l'alternative correspond à des capteurs émettant des signaux corrélés. Contrairement à la littérature traditionnelle, nous considérons des procédures de test séquentielles, et nous établissons que de telles procédures permettent de détecter des corrélations significativement plus faible que les méthodes traditionnelles. Dans un second temps, nous considérons le problème de localiser des objets dans des images. En s'appuyant sur de récents résultats en apprentissage de représentation pour des problèmes similaires, nous intégrons des features de grande dimension issues de réseaux de neurones convolutionnels dans les modèles déformables traditionnellement utilisés pour ce type de problème. Nous démontrons expérimentalement que ce type d'approche permet de diminuer significativement le taux d'erreur de ces modèles. / This thesis is organized in two independent parts. The first part focused on convex matrix estimation problems, where both rank and sparsity are taken into account simultaneously. In the context of graphs with community structures, a common assumption is that the underlying adjacency matrices are block-diagonal in an appropriate basis. However, these types of graphs are usually far from complete, and their adjacency representations are thus also inherently sparse. This suggests that combining the sparse hypothesis and the low rank hypothesis may allow to more accurately model such objects. To this end, we propose and analyze a convex penalty to promote both low rank and high sparsity at the same time. Although the low rank hypothesis allows to reduce over-fitting by decreasing the modeling capacity of a matrix model, the opposite may be desirable when enough data is available. We study such an example in the context of localized multiple kernel learning, which extends multiple kernel learning by allowing each of the kernels to select different support vectors. In this framework, multiple kernel learning corresponds to a rank one estimator, while higher-rank estimators have been observed to increase generalization performance. We propose a novel family of large-margin methods for this problem that, unlike previous methods, are both convex and theoretically grounded. The second part of the thesis is about detection of objects or signals which exhibit combinatorial structures, and we present two such problems. First, we consider detection in the statistical hypothesis testing sense, in models where anomalous signals correspond to correlated values at different sensors. In most existing work, detection procedures are provided with a full sample of all the sensors. However, the experimenter may have the capacity to make targeted measurements in an on-line and adaptive manner, and we investigate such adaptive sensing procedures. Finally, we consider the task of identifying and localizing objects in images. This is an important problem in computer vision, where hand-crafted features are usually used. Following recent successes in learning ad-hoc representations for similar problems, we integrate the method of deformable part models with high-dimensional features from convolutional neural networks, and shows that this significantly decreases the error rates of existing part-based models.

This master's thesis addresses numerical methods of computing the typical ranks of tensors over the real numbers and explores some properties of tensors over finite fields. We present three numerical methods to compute typical tensor rank. Two of these have already been published and can be used to calculate the lowest typical ranks of tensors and an approximate percentage of how many tensors have the lowest typical ranks (for some tensor formats), respectively. The third method was developed by the authors with the intent to be able to discern if there is more than one typical rank. Some results from the method are presented but are inconclusive. In the area of tensors over nite filds some new results are shown, namely that there are eight GLq(2) GLq(2) GLq(2)-orbits of 2 2 2 tensors over any finite field and that some tensors over Fq have lower rank when considered as tensors over Fq2 . Furthermore, it is shown that some symmetric tensors over F2 do not have a symmetric rank and that there are tensors over some other finite fields which have a larger symmetric rank than rank.

L'objet de cette thèse est la réalisation d'algorithmes et d'outils d'aide à l'étude des propriétés de structures combinatoires particulières, les structures décomposables. Nous nous intéressons pour cela à la génération aléatoire et systématique de structures décomposables, puis à leur représentation graphique automatique. Ce travail se situe à la frontière entre calcul mathématique et visualisation. Les structures décomposables sont les structures combinatoires qu'il est possible de former récursivement en utilisant des constructeurs aux propriétés particulières. Le point de vue est similaire à celui adopté dans la théorie des espèces de structures, où l'on privilégie la description d'ensembles de structures à partir de transformations d'ensembles existants. Il est alors possible, grâce à des spécifications, de décrire une infinité d'ensembles de structures combinatoires parmi lesquels les permutations, les graphes fonctionnels, les arbres enracinés ou encore les hiérarchies. L'intérêt de cette démarche tient au fait que l'on sait résoudre des problèmes de dénombrement et de comportement asymptotique sur ces ensembles et générer aléatoirement de façon uniforme des structures de ces ensembles. Les applications concernent le calcul de complexité en moyenne d'algorithmes, et la génération de jeux de tests pour la validation expérimentale ou l'étalonnage d'algorithmes. Nous présentons dans cette thèse deux types de résultats. Les premiers concernent la génération de structures décomposables, les seconds leur représentation graphique. Nous présentons une implantation d'un algorithme classique de génération aléatoire de structures décomposables, et nous proposons des techniques permettant de générer tous les éléments d'un ensemble à partir de sa spécification. Nous proposons également un algorithme de tracé de graphes particuliers, pour lesquels il existe à la fois des relations d'adjacence et d'inclusion entre les nœœœœœoeuds. Ces graphes, que nous appelons les graphes composés, sont en effet bien adaptés à la représentation de la nature générique des structures décomposables. Ce travail est concrétisé par la réalisation de deux logiciels de tracé de structures combinatoires. Leur utilisation n'est cependant pas limitée à ce seule domaine et les apsects liés à leur application à la visualisation de graphes en général sont abordés.

.

Dans ce travail, nous étudions différents invariants de nature algébrique et dynamique définis sur le groupe des difféomorphismes hamiltoniens d'une surface fermée orientée. Occasionnellement, nous considérerons également le groupe des difféomorphismes hamiltoniens de certaines variétés symplectiques de dimension supérieure. Ces invariants peuvent être vus comme des généralisations du nombre de rotation de Poincaré, et des vecteurs de rotations associés aux difféomorphismes des surfaces. D'autre part, tous ces invariants sont reliés à la théorie de la cohomologie bornée. <br /><br />Dans le premier chapitre nous construisons des quasi-morphismes sur le groupe des difféomorphismes hamiltoniens d'une surface de genre strictement positif, qui sont des homomorphismes en restriction au sous-groupe des difféomorphismes à support dans un ouvert difféomorphe à un disque. Ces constructions sont motivées par une question de Entov et Polterovich. Dans le second chapitre nous construisons un quasi-morphisme défini sur le revêtement universel du groupe des difféomorphismes hamiltoniens d'une variété symplectique monotone. <br /><br />Le troisième chapitre contient quelques résultats concernant les actions préservant l'aire sur les surfaces de réseaux dans les groupes de Lie semi-simples. Dans l'esprit du "programme de Zimmer", nous montrons comment l'existence de nombreux quasi-morphismes, combinée avec des théorèmes d'annulation en cohomologie bornée, pourrait être utile pour exclure l'existence d'actions de réseaux de rang supérieur. Le dernier chapitre contient quelques remarques autour de la distance de Hofer.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

La mise au point de descripteurs locaux discriminants est aujourd’hui une priorité dans de nombreuses applications comme la reconnaissance d’objets, le suivi d’objets, la reconstruction 3D ou l’estimation de mouvement. La problématique réside dans le fait que ces descripteurs doivent être invariants aux conditions d’acquisition tout en conservant un pouvoir discriminant important. Dans ce contexte, nous nous sommes intéressés à l’invariance des descripteurs locaux de la littérature. Nous les avons notamment catégorisés en fonction des hypothèses sur lesquelles repose leur invariance. Ensuite, nous avons proposé des descripteurs locaux qui exploitent l’information de couleur dans les images. Nous avons montré que cette information peut être très pertinente lorsqu’elle est combinée à une information spatiale, à condition que son degré d’invariance soit contrôlé et adapté aux applications considérées. Ainsi, nous avons proposé un ensemble de descripteurs locaux couleur avec des degrés d’invariance différents. Ainsi, nous introduisons tout d’abord deux nouveaux descripteurs qui caractérisent les distributions spatiales des couleurs dans les régions analysées. L’idée originale consiste à appliquer des transformations affines entre les coordonnées spatiales des pixels et leurs coordonnées couleur. En effet, chaque pixel étant caractérisé par 5 valeurs, 2 coordonnées spatiales xy dans l’image et 3 composantes couleur RVB, nous proposons de rechercher une transformation affine qui permet de transformer les coordonnées xy de tous les pixels de la région concernée en coordonnées RVB de ces pixels. Nous montrons que l’application de cette transformation aux coordonnées xy fournit des coordonnées dans l’espace RVB qui a un double avantage. D’une part, les coordonnées d’un seul pixel dépendent à la fois de toutes les couleurs présentes dans la région mais aussi de leur répartition spatiale. Quelques coordonnées permettent donc de résumer efficacement le contenu de la région. D’autre part, ces coordonnées présente une invariance totale à toute transformation affine appliquée dans l’espace image 2D(invariance géométrique) et comme elles sont homogènes à des coordonnées couleur, nous pouvons leur procurer une invariance photométrique en leur appliquant des transformations affines particulières. Nous montrons que le degré d’invariance peut être contrôlé en fonction des besoins de l’application. Ces coordonnées nous permettent de définir le descripteur IVC (Image Vers Couleur). De manière similaire, nous évaluons une transformation affine de l’espace couleur à l’espace image et appliquons cette transformation aux coordonnées couleur. Les coordonnées obtenues par cette transformation sont invariantes à toute transformation affine appliquée dans l’espace couleur, elles présentent donc un degré d’invariance élevé aux variations photométriques. Ces coordonnées nous permettent de constituer le descripteur CVI (Couleur Vers Image). Nous montrons que ces deux descripteurs fournissent de très bons résultats dans le cadre de la reconnaissance d’objet et présentent une telle complémentarité que le descripteur obtenu par concaténation de IVC et CVI fournit de meilleurs résultats que la plupart des descripteurs couleur parus dans la littérature. Ensuite, nous proposons un descripteur qui présente un degré d’invariance plus élevé que les deux précédents puisqu’il n’est pas sensible aux transformations non-linéaires des couleurs modélisées par des fonctions croissantes appliquées indépendamment sur chaque composante couleur. Pour cela, nous exploitons les mesures de rang des pixels dans les images. De plus, nous utilisons les corrélations entre mesures de rang obtenues pour différentes composantes couleur. Ceci nous a permis de proposer un descripteur lui aussi très compact qui présente un degré d’invariance photométrique assez élevé. Enfin, nous abordons le problème de la caractérisation locale d’images par auto-similarités / Pas de résumé fourni en anglais

Les code en métrique rang attirent l’attention depuis quelques années en raison de leur application possible au codage réseau linéaire aléatoire (random linear network coding), à la cryptographie à clé publique, au codage espace-temps et aux systèmes de stockage distribué. Une construction de codes algébriques en métrique rang de cardinalité optimale a été introduite par Delsarte, Gabidulin et Roth il y a quelques décennies. Ces codes sont considérés comme l’équivalent des codes de Reed – Solomon et ils sont basés sur l’évaluation de polynômes linéarisés. Ils sont maintenant appelés les codes de Gabidulin. Cette thèse traite des codes en bloc et des codes convolutifs en métrique rang avec l’objectif de développer et d’étudier des algorithmes de décodage efficaces pour ces deux classes de codes. Après une introduction dans le chapitre 1, le chapitre 2 fournit une introduction rapide aux codes en métrique rang et leurs propriétés. Dans le chapitre 3, on considère des approches efficaces pour décoder les codes de Gabidulin. Lapremière partie de ce chapitre traite des algorithmes rapides pour les opérations sur les polynômes linéarisés. La deuxième partie de ce chapitre résume tout d’abord les techniques connues pour le décodage jusqu’à la moitié de la distance rang minimale (bounded minimum distance decoding) des codes de Gabidulin, qui sont basées sur les syndromes et sur la résolution d’une équation clé. Ensuite, nous présentons et nous prouvons un nouvel algorithme efficace pour le décodage jusqu’à la moitié de la distance minimale des codes de Gabidulin. Le chapitre 4 est consacré aux codes de Gabidulin entrelacés et à leur décodage au-delà de la moitié de la distance rang minimale. Dans ce chapitre, nous décrivons d’abord les deux approches connues pour le décodage unique et nous tirons une relation entre eux et leurs probabilités de défaillance. Ensuite, nous présentons un nouvel algorithme de décodage des codes de Gabidulin entrelacés basé sur l’interpolation des polynômes linéarisés. Nous prouvons la justesse de ses deux étapes principales — l’interpolation et la recherche des racines — et montrons que chacune d’elles peut être effectuée en résolvant un système d’équations linéaires. Jusqu’à présent, aucun algorithme de décodage en liste en temps polynomial pour les codes de Gabidulin n’est connu et en fait il n’est même pas clair que cela soit possible. Cela nous a motivé à étudier, dans le chapitre 5, les possibilités du décodage en liste en temps polynomial des codes en métrique rang. Cette analyse est effectuée par le calcul de bornes sur la taille de la liste des codes en métriques rang en général et des codes de Gabidulin en particulier. Étonnamment, les trois nouvelles bornes révèlent toutes un comportement des codes en métrique rang qui est complètement différent de celui des codes en métrique de Hamming. Enfin, dans le chapitre 6, on introduit des codes convolutifs en métrique rang. Ce qui nous motive à considérer ces codes est le codage réseau linéaire aléatoire multi-shot, où le réseau inconnu varie avec le temps et est utilisé plusieurs fois. Les codes convolutifs créent des dépendances entre les utilisations différentes du réseau aun de se adapter aux canaux difficiles. Basé sur des codes en bloc en métrique rang (en particulier les codes de Gabidulin), nous donnons deux constructions explicites des codes convolutifs en métrique rang. Les codes en bloc sous-jacents nous permettent de développer un algorithme de décodage des erreurs et des effacements efficace pour la deuxième construction, qui garantit de corriger toutes les séquences d’erreurs de poids rang jusqu’à la moitié de la distance rang active des lignes. Un résumé et un aperçu des problèmes futurs de recherche sont donnés à la fin de chaque chapitre. Finalement, le chapitre 7 conclut cette thèse. / Rank-metric codes recently attract a lot of attention due to their possible application to network coding, cryptography, space-time coding and distributed storage. An optimal-cardinality algebraic code construction in rank metric was introduced some decades ago by Delsarte, Gabidulin and Roth. This Reed–Solomon-like code class is based on the evaluation of linearized polynomials and is nowadays called Gabidulin codes. This dissertation considers block and convolutional codes in rank metric with the objective of designing and investigating efficient decoding algorithms for both code classes. After giving a brief introduction to codes in rank metric and their properties, we first derive sub-quadratic-time algorithms for operations with linearized polynomials and state a new bounded minimum distance decoding algorithm for Gabidulin codes. This algorithm directly outputs the linearized evaluation polynomial of the estimated codeword by means of the (fast) linearized Euclidean algorithm. Second, we present a new interpolation-based algorithm for unique and (not necessarily polynomial-time) list decoding of interleaved Gabidulin codes. This algorithm decodes most error patterns of rank greater than half the minimum rank distance by efficiently solving two linear systems of equations. As a third topic, we investigate the possibilities of polynomial-time list decoding of rank-metric codes in general and Gabidulin codes in particular. For this purpose, we derive three bounds on the list size. These bounds show that the behavior of the list size for both, Gabidulin and rank-metric block codes in general, is significantly different from the behavior of Reed–Solomon codes and block codes in Hamming metric, respectively. The bounds imply, amongst others, that there exists no polynomial upper bound on the list size in rank metric as the Johnson bound in Hamming metric, which depends only on the length and the minimum rank distance of the code. Finally, we introduce a special class of convolutional codes in rank metric and propose an efficient decoding algorithm for these codes. These convolutional codes are (partial) unit memory codes, built upon rank-metric block codes. This structure is crucial in the decoding process since we exploit the efficient decoders of the underlying block codes in order to decode the convolutional code.

L'ensemble des travaux sur lesquels s'appuie la note de synthèse présente une unité évidente autour du thème de l'algèbre linéaire. Nous dégageons un autre type d'unité portant non pas sur le contenu mathématique étudié mais sur la méthodologie de recherche employée, tout en en soulignant l'originalité. Notre but est de montrer le rôle central joué dans nos travaux didactiques par l'interaction avec nos recherches historiques. Nous abordons cette question sous un angle plus général, en dégageant, au delà du seul exemple de l'algèbre linéaire, la nature des interactions possibles entre recherches historique et didactique et leur apport épistémologique, en dégageant également des questions de méthodologie. Nous nous appuierons sur diverses de nos publications pour construire notre réflexion.

Dans ce travail, nous étudions de manière approfondie les lois $\al$-stables (lois à variance infinie). Dans le premier chapitre, nous rappelons les différentes propriétés des lois $\al$-stables univariées (stabilité, calcul des moments, simulation). Nous introduisons ensuite les lois symétriques $\al$-stables (\SaS) multivariées. Après avoir parlé de la mesure spectrale et de son intérêt pour caractériser l'indépendance, nous nous concentrons sur les mesures de dépendance. Constatant que le coefficient de covariation, largement utilisé actuellement, admet certaines limites, nous construisons dans le deuxième chapitre une nouvelle mesure de dépendance, appelée coefficient de covariation symétrique. Ce dernier nous permet, entre autres, de découvrir quelques spécificités des vecteurs \SaS. En effet, contrairement aux vecteurs gaussiens, on peut obtenir pour certains vecteurs \SaS\ à la fois une dépendance positive et une dépendance négative. Après avoir conclu le chapitre par l'étude de la loi asymptotique de l'estimateur du coefficient de covariation, nous abordons, dans le troisième chapitre, les processus autorégressifs à innovations stables. Nous présentons les différentes méthodes d'identification de l'ordre d'un processus AR: autocorrélation partielle (Brockwell et Davis) et statistiques quadratiques asymptotiquement invariantes basées sur les rangs (Garel et Hallin). De nombreuses simulations, effectuées en Matlab et Fortran, nous permettent de comparer ces méthodes et de constater l'importance du rôle joué par les statistiques de rang dans ce domaine. Pour finir, un problème de test séquentiel, développé dans le cadre d'un contrat industriel, nous permet d'introduire la notion de niveau de confiance après décision.