Normes Parcimonieuses Structurées : Propriétés Statistiques et Algorithmiques avec Applications à l'Imagerie Cérébrale

Numerous fields of applied sciences and industries have been witnessing a process of digitisation over the past few years. This trend has come with a steady increase in the amount of available digital data whose processing was become a challenging task. For instance, it is nowadays common to take thousands of pictures of several millions of pixels, which makes any subsequent image-processing/computer-vision task a computationally demanding exercise. In this context, parsimony--also known as sparsity--has emerged as a key concept in machine learning, statistics and signal processing. It is indeed appealing to represent, analyze, and exploit data through a reduced number of parameters, e.g., performing object recognition over high-resolution images based only on some relevant subsets of pixels. While general sparsity-inducing approaches have already been well-studied--with elegant theoretical foundations, efficient algorithmic tools and successful applications, this thesis focuses on a particular and more recent form of sparsity, referred to as structured sparsity. As its name indicates, we shall consider situations where we are not only interested in sparsity, but where some structural prior knowledge is also available. Continuing the example of object recognition, we know that neighbouring pixels on images tend to share similar properties--e.g., the label of the object class to which they belong--so that sparsity-inducing approaches should take advantage of this spatial information. The goal of this thesis is to understand and analyze the concept of structured sparsity, based on statistical, algorithmic and applied considerations. To begin with, we introduce a family of structured sparsity-inducing norms whose properties are closely studied. In particular, we show what type of structural prior knowledge they correspond to, and we present the statistical conditions under which these norms are capable of consistently performing structured variable selection. We then turn to the study of sparse structured dictionary learning, where we use the aforementioned norms within the framework of matrix factorization. The resulting approach is flexible and versatile, and it is shown to learn representations whose structured sparsity patterns are adapted to the considered class of signals. From an optimization viewpoint, we derive several efficient and scalable algorithmic tools, such as, working-set strategies and proximal-gradient techniques. With these methods in place, we illustrate on numerous real-world applications from various fields, when and why structured sparsity is useful. This includes, for instance, restoration tasks in image processing, the modelling of text documents as hierarchy of topics, the inter-subject prediction of sizes of objects from fMRI signals, and background-subtraction problems in computer vision.De nombreux domaines issus de l'industrie et des sciences appliquées ont été, au cours des dernières années, les témoins d'une révolution numérique. Cette tendance s'est accompagnée d'une croissance continue du volume des données--vidéos, musiques et images, dont le traitement est devenu un véritable défi technique. Par exemple, il est aujourd'hui fréquent de prendre des centaines de photographies de plusieurs millions de pixels, la moindre application de méthodes du traitement de l'image devenant alors une opération difficile. Dans ce contexte, la parcimonie est apparue comme un concept central en apprentissage statistique et traitement du signal. Il est en effet naturel de représenter, analyser et exploiter les données disponibles à travers un nombre réduit de paramètres. Par exemple, on peut imaginer effectuer de la reconnaissance d'objets sur des images de hautes résolutions en n'utilisant qu'un petit sous-ensemble pertinent de pixels. Alors que les approches générales favorisant la parcimonie ont déjà été l'objet de nombreux travaux--débouchant sur d'élégantes fondations théoriques, des outils algorithmiques efficaces et plusieurs succès pratiques--cette thèse se concentre sur une forme particulière et plus récente de parcimonie, nommée parcimonie structurée. Comme son nom l'indique, nous considérerons des situations où nous ne serons pas simplement intéréssés par la parcimonie, mais où nous aurons également à disposition des connaissances a priori nous renseignant sur certaines propriétés structurelles. En continuant d'exploiter l'exemple de la reconnaissance d'objets mentioné ci-dessus, nous savons que des pixels voisins sur une image ont tendance à partager des propriétés similaires, telles que la classe de l'objet à laquelle ils appartiennent. Ainsi, une approche encourageant la parcimonie devrait tirer partie de cette information spatiale. L'objectif de cette thèse est de comprendre et analyser le concept de parcimonie structurée, en se basant sur des considérations statistiques, algorithmiques et appliquées. Nous commencerons par introduire une famille de normes structurées parcimonieuses dont les propriétés sont étudiées en détail. En particulier, nous montrerons à quel type d'information structurelle ces normes correspondent, et nous présenterons sous quelles conditions statistiques elles sont capables de produire une séléction consistente de variables. Nous étudierons ensuite l'apprentissage de dictionnaires parcimonieux et structurés, où nous exploiterons les normes introduites précédemment dans un cadre de factorisation de matrices. L'approche qui en résulte est fléxible et versatile, et nous montrerons que les éléments de dictionnaire appris exhibent une structure parcimonieuse adaptée à la classe de signaux considérée. Concernant l'optimisation, nous proposerons différents outils algorithmiques efficaces et capables de passer à l'échelle, tels que des stratégies à ensemble de variables actives ou encore des méthodes proximales. Grâce à ces outils algorithmiques, nous illustrerons sur de nombreuses applications issues de domaines variés, quand et pourquoi la parcimonie structurée peut être bénéfique. Ces illustrations contiennent par exemple, des tâches de restauration en traitement de l'image, la modélisation de documents textuels sous la forme d'une hiérarchie de thèmes, la prédiction de la taille d'objets à partir de signaux d'imagerie par résonance magnétique fonctionnelle, ou encore des problèmes de segmentation d'images en vision par ordinateur