La finesse de la résolution spectrale des images hyperspectrales en télédétection permet une analyse précise de la scène observée, mais leur résolution spatiale est limitée, et un pixel acquis par le capteur est souvent un mélange des contributions de différents matériaux. Le démélange spectral permet d'estimer les spectres des matériaux purs (endmembers) de la scène, et leurs abondances dans chaque pixel. Les endmembers sont souvent supposés être parfaitement représentés par un seul spectre, une hypothèse fausse en pratique, chaque matériau ayant une variabilité intra-classe non négligeable. Le but de cette thèse est de développer des algorithmes prenant mieux en compte ce phénomène. Nous effectuons le démélange localement, dans des régions bien choisies de l'image où les effets de la variabilité sont moindres, en éliminant automatiquement les endmembers non pertinents grâce à de la parcimonie collaborative. Dans une autre approche, nous raffinons l'estimation des abondances en utilisant la structure de groupe d'un dictionnaire d'endmembers extrait depuis les données. Ensuite, nous proposons un modèle de mélange linéaire étendu, basé sur des considérations physiques, qui modélise la variabilité spectrale par des facteurs d'échelle, et développons des algorithmes d'optimisation pour en estimer les paramètres. Ce modèle donne des résultats facilement interprétables et de meilleures performances que d'autres approches de la littérature. Nous étudions enfin deux applications de ce modèle pour confirmer sa pertinence. / The fine spectral resolution of hyperspectral remote sensing images allows an accurate analysis of the imaged scene, but due to their limited spatial resolution, a pixel acquired by the sensor is often a mixture of the contributions of several materials. Spectral unmixing aims at estimating the spectra of the pure materials (called endmembers) in the scene, and their abundances in each pixel. The endmembers are usually assumed to be perfectly represented by a single spectrum, which is wrong in practice since each material exhibits a significant intra-class variability. This thesis aims at designing unmixing algorithms to better handle this phenomenon. First, we perform the unmixing locally in well chosen regions of the image where variability effects are less important, and automatically discard wrongly estimated local endmembers using collaborative sparsity. In another approach, we refine the abundance estimation of the materials by taking into account the group structure of an image-derived endmember dictionary. Second, we introduce an extended linear mixing model, based on physical considerations, modeling spectral variability in the form of scaling factors, and develop optimization algorithms to estimate its parameters. This model provides easily interpretable results and outperforms other state-of-the-art approaches. We finally investigate two applications of this model to confirm its relevance.

Dans ce travail, nous abordons les problèmes de l'analyse de la stabilité et de la synthèse de contrôleur pour une Equation aux Dérivées Partielles (EDP) parabolique linéaire de dimension 1. Ces problèmes sont résolus avec des méthodologies analogues au cadre des inégalités matricielles linéaires (LMI) pour les équations différentielles ordinaires (EDO). Nous développons une méthode pour EDP paraboliques dans laquelle nous testons la faisabilité de certaines LMIs utilisant la programmation semi-définie (SDP) pour construire des fonctions de Lyapunov quadratiques et des contrôleurs. Le cœur de notre démarche est la construction de fonctions de Lyapunov quadratiques paramétrées par les opérateurs définis positifs sur les espaces de Hilbert de dimension infinie. Contrairement aux matrices positives, il n'y a pas de méthode unique paramétrisant l'ensemble des opérateurs positifs sur un espace de Hilbert. Bien sûr, nous pouvons toujours paramétrer un sous-ensemble des opérateurs positifs en utilisant, par exemple, des scalaires positifs. Cependant, nous devons nous assurer que le paramétrage des opérateurs positifs ne doit pas être conservatif. Notre contribution est de construire une paramétrisation qui a seulement une petite quantité de conservatisme comme indiqué par nos résultats numériques. Nous utilisons des polynômes en somme des carrés (SOS) pour paramétrer l'ensemble des opérateurs positifs, linéaire et bornés sur les espaces de Hilbert. Comme son nom l'indique, un polynôme SOS est celui qui peut être représenté comme une somme de polynômes carrés. La propriété la plus importante d'un polynôme SOS est qu'il peut être représenté au moyen d'une matrice (semi-)définie positive. Cela implique que, même si le problème de polynôme (semi-)positif est NP-difficile, le problème de vérifier si polynôme est SOS (et donc (semi-)positif) peut être résolu en utilisant la SDP. Par conséquent, nous nous efforçons de construire des fonctions de Lyapunov quadratiques paramétrées par les opérateurs positifs. Ces opérateurs positifs sont à leur tour paramétrés par des polynômes SOS. Cette paramétrisation SOS nous permet de formuler le problème de faisabilité pour l'existence d'une fonction de Lyapunov quadratique comme un problème de faisabilité LMI. Le problème de la faisabilité LMI peut alors être adressé à l'aide de SDP. Dans la première partie de la thèse nous considérons analyse de stabilité et la synthèse de contrôleur aux frontières pour une large classe d'EDP paraboliques. Les EDP ont des coefficients de transport distribués spatialement. Ces EDP sont utilisés pour modéliser les processus de diffusion, de convection et de réaction de quantités physiques dans les milieux anisotropes. Nous considérons la synthèse de contrôleurs limite à la fois pour le cas de retour d'état et le cas de retour de sortie (à l'aide d'un observateur). Dans la deuxième partie de la thèse, nous concevons un contrôleur distribué pour la régulation du flux magnétique poloïdal dans un tokamak (procédé de fusion thermonucléaire par confinement magnétique). Tout d'abord, nous concevons un contrôleur régulant la pente des lignes de champ magnétique (le facteur de sécurité). La régulation du profil du facteur de sécurité est importante pour supprimer les instabilités MHD dans un tokamak. Ensuite, nous concevons un contrôleur maximisant la densité de courant bootstrap généré en interne. Une proportion accrue du courant bootstrap conduirait à une réduction des besoins énergétiques exogènes pour l'exploitation d'un tokamak. / In this work we address the problems of stability analysis and controller synthesis for one dimensional linear parabolic Partial Differential Equations (PDEs). To achieve the tasks of stability analysis and controller synthesis we develop methodologies akin to the Linear Matrix Inequality (LMI) framework for Ordinary Differential Equations (ODEs). We develop a method for parabolic PDEs wherein we test the feasibility of certain LMIs using SDP to construct quadratic Lyapunov functions and controllers. The core of our approach is the construction of quadratic Lyapunov functions parametrized by positive definite operators on infinite dimensional Hilbert spaces. Unlike positive matrices, there is no single method of parametrizing the set of all positive operators on a Hilbert space. Of course, we can always parametrize a subset of positive operators, using, for example, positive scalars. However, we must ensure that the parametrization of positive operators should not be conservative. Our contribution is constructing a parametrization which has only a small amount of conservatism as indicated by our numerical results. We use Sum-of-Squares (SOS) polynomials to parametrize the set of positive, linear and bounded operators on Hilbert spaces. As the name indicates, an SOS polynomial is one which can be represented as a sum of squared polynomials. The most important property of an SOS polynomial is that it can be represented using a positive (semi)-definite matrix. This implies that even though the problem of polynomial (semi)-positivity is NP-hard, the problem of checking if polynomial is SOS (and hence (semi)-positive) can be solved using SDP. Therefore, we aim to construct quadratic Lyapunov functions parametrized by positive operators. These positive operators are in turn parametrized by SOS polynomials. This parametrization using SOS allows us to cast the feasibility problem for the existence of a quadratic Lyapunov function as the feasibility problem of LMIs. The feasibility problem of LMIs can then be addressed using SDP. In the first part of the thesis we consider stability analysis and boundary controller synthesis for a large class of parabolic PDEs. The PDEs have spatially distributed coefficients. Such PDEs are used to model processes of diffusion, convection and reaction of physical quantities in anisotropic media. We consider boundary controller synthesis for both the state feedback case and the output feedback case (using and observer design). IN the second part of thesis we design distributed controllers for the regulation of poloidal magnetic flux in a tokamak (a thermonuclear fusion devise). First, we design the controllers to regulate the magnetic field line pitch (the safety factor). The regulation of the safety factor profile is important to suppress the magnetohydrodynamic instabilities in a tokamak. Then, we design controllers to maximize the internally generated bootstrap current density. An increased proportion of bootstrap current would lead to a reduction in the external energy requirements for the operation of a tokamak.

Les réseaux électriques subissent deux changements majeurs : le taux croissant de générateurs d’énergie distribuée (GED) intermittents et la dérégulation du système électrique. Les réseaux de distribution et leurs gestionnaires (GRD) sont plus particulièrement touchés. La planification, construction et exploitation des réseaux de la plupart des GRD doivent évoluer face à ces change- ments. Les réseaux actifs de distribution et la gestion intelligente de associée est une solution potentielle. Les GRD pourront ainsi adopter de nouveaux rôles, interagir avec de nouveaux acteurs et proposer de nouveaux services. Ils pourront aussi utiliser la flexibilité de manière optimale au travers, entre autres, d’outils intelligents pour la gestion prévisionnelle de leurs réseaux de moyenne tension (HTA). Développer ces outils est un défi, car les réseaux de distribution ont des spécificités techniques. Ces spécificités sont la présence d’éléments discrets comme les régleurs en charge et la reconfiguration, les flexibilités exogènes, la non-linéarité des calculs de répartition de charge, et l’incertitude liée aux prévisions des GED intermittents. Dans cette thèse, une analyse économique des flexibilités permet d’établir une référence commune pour une utilisation rentable et sans biais dans la gestion prévisionnelle. Des modèles linéaires des flexibilités sont développés en utilisant des reformulations mathématiques exactes. Le calcul de répartition de charge est “convexifié” à travers des reformulations. L’optimalité globale des solutions obtenues, avec ce modèle d’optimisation exact et convexe de gestion prévisionnelle, sont ainsi garanties. Les tests sur deux réseaux permettent d’en valider la performance. L’incertitude des prévisions de GED peut pourtant remettre en cause les solutions obtenues. Afin de résoudre ce problème, trois formulations différentes pour traiter cette incertitude sont développées. Leurs performances sont testées et comparées à travers des simulations. Une analyse permet d’identifier les formulations les plus adaptées pour la gestion prévisionnelle sous incertitude. / Power systems are faced by the rising shares of distributed renewable energy sources (DRES) and the deregulation of the electricity system. Distribution networks and their operators (DSO) are particularly at the front-line. The passive operational practives of many DSOs today have to evolve to overcome these challenges. Active Distribution Networks (ADN), and Active Network Management (ANM) have been touted as a potential solution. In this context, DSOs will streamline investment and operational decisions, creating a cost-effective framework of operations. They will evolve and take up new roles and optimally use flexibility to perform, for example, short-term op- erational planning of their networks. However, the development of such methods poses particular challenges. They are related to the presence of discrete elements (OLTCs and reconfiguration), the use of exogenous (external) flexibilities in these networks, the non-linear nature of optimal power flow (OPF) calculations, and uncertainties present in forecasts. The work leading to this thesis deals with and overcomes these challenges. First, a short-term economic analysis is done to ascertain the utilisation costs of flexibilities. This provides a common reference for different flexibilities. Then, exact linear flexibility models are developed using mathematical reformulation techniques. The OPF equations in operational planning are then convexified using reformulation techniques as well. The mixed-integer convex optimisation model thus developed, called the novel OP formulation, is exact and can guarantee globally optimal solutions. Simulations on two test networks allow us to evaluate the performance of this formulation. The uncertainty in DRES forecasts is then handled via three different formulations developed in this thesis. The best performing formulations under uncertainty are determined via comparison framework developed to test their performance.

Une approche efficace pour la résolution de problèmes inverses consiste à définir le signal (ou l'image) recherché(e) par minimisation d'un critère pénalisé. Ce dernier s'écrit souvent sous la forme d'une somme de fonctions composées avec des opérateurs linéaires. En pratique, ces fonctions peuvent n'être ni convexes ni différentiables. De plus, les problèmes auxquels on doit faire face sont souvent de grande dimension. L'objectif de cette thèse est de concevoir de nouvelles méthodes pour résoudre de tels problèmes de minimisation, tout en accordant une attention particulière aux coûts de calculs ainsi qu'aux résultats théoriques de convergence. Une première idée pour construire des algorithmes rapides d'optimisation est d'employer une stratégie de préconditionnement, la métrique sous-jacente étant adaptée à chaque itération. Nous appliquons cette technique à l'algorithme explicite-implicite et proposons une méthode, fondée sur le principe de majoration-minimisation, afin de choisir automatiquement les matrices de préconditionnement. L'analyse de la convergence de cet algorithme repose sur l'inégalité de Kurdyka-L ojasiewicz. Une seconde stratégie consiste à découper les données traitées en différents blocs de dimension réduite. Cette approche nous permet de contrôler à la fois le nombre d'opérations s'effectuant à chaque itération de l'algorithme, ainsi que les besoins en mémoire, lors de son implémentation. Nous proposons ainsi des méthodes alternées par bloc dans les contextes de l'optimisation non convexe et convexe. Dans le cadre non convexe, une version alternée par bloc de l'algorithme explicite-implicite préconditionné est proposée. Les blocs sont alors mis à jour suivant une règle déterministe acyclique. Lorsque des hypothèses supplémentaires de convexité peuvent être faites, nous obtenons divers algorithmes proximaux primaux-duaux alternés, permettant l'usage d'une règle aléatoire arbitraire de balayage des blocs. L'analyse théorique de ces algorithmes stochastiques d'optimisation convexe se base sur la théorie des opérateurs monotones. Un élément clé permettant de résoudre des problèmes d'optimisation de grande dimension réside dans la possibilité de mettre en oeuvre en parallèle certaines étapes de calculs. Cette parallélisation est possible pour les algorithmes proximaux primaux-duaux alternés par bloc que nous proposons: les variables primales, ainsi que celles duales, peuvent être mises à jour en parallèle, de manière tout à fait flexible. A partir de ces résultats, nous déduisons de nouvelles méthodes distribuées, où les calculs sont répartis sur différents agents communiquant entre eux suivant une topologie d'hypergraphe. Finalement, nos contributions méthodologiques sont validées sur différentes applications en traitement du signal et des images. Nous nous intéressons dans un premier temps à divers problèmes d'optimisation faisant intervenir des critères non convexes, en particulier en restauration d'images lorsque l'image originale est dégradée par un bruit gaussien dépendant du signal, en démélange spectral, en reconstruction de phase en tomographie, et en déconvolution aveugle pour la reconstruction de signaux sismiques parcimonieux. Puis, dans un second temps, nous abordons des problèmes convexes intervenant dans la reconstruction de maillages 3D et dans l'optimisation de requêtes pour la gestion de bases de données / An efficient approach for solving an inverse problem is to define the recovered signal/image as a minimizer of a penalized criterion which is often split in a sum of simpler functions composed with linear operators. In the situations of practical interest, these functions may be neither convex nor smooth. In addition, large scale optimization problems often have to be faced. This thesis is devoted to the design of new methods to solve such difficult minimization problems, while paying attention to computational issues and theoretical convergence properties. A first idea to build fast minimization algorithms is to make use of a preconditioning strategy by adapting, at each iteration, the underlying metric. We incorporate this technique in the forward-backward algorithm and provide an automatic method for choosing the preconditioning matrices, based on a majorization-minimization principle. The convergence proofs rely on the Kurdyka-L ojasiewicz inequality. A second strategy consists of splitting the involved data in different blocks of reduced dimension. This approach allows us to control the number of operations performed at each iteration of the algorithms, as well as the required memory. For this purpose, block alternating methods are developed in the context of both non-convex and convex optimization problems. In the non-convex case, a block alternating version of the preconditioned forward-backward algorithm is proposed, where the blocks are updated according to an acyclic deterministic rule. When additional convexity assumptions can be made, various alternating proximal primal-dual algorithms are obtained by using an arbitrary random sweeping rule. The theoretical analysis of these stochastic convex optimization algorithms is grounded on the theory of monotone operators. A key ingredient in the solution of high dimensional optimization problems lies in the possibility of performing some of the computation steps in a parallel manner. This parallelization is made possible in the proposed block alternating primal-dual methods where the primal variables, as well as the dual ones, can be updated in a quite flexible way. As an offspring of these results, new distributed algorithms are derived, where the computations are spread over a set of agents connected through a general hyper graph topology. Finally, our methodological contributions are validated on a number of applications in signal and image processing. First, we focus on optimization problems involving non-convex criteria, in particular image restoration when the original image is corrupted with a signal dependent Gaussian noise, spectral unmixing, phase reconstruction in tomography, and blind deconvolution in seismic sparse signal reconstruction. Then, we address convex minimization problems arising in the context of 3D mesh denoising and in query optimization for database management

Dans de nombreux domaines tels que l’apprentissage statistique, la recherche opérationnelle ou encore la conception de circuits, une tâche est modélisée par un jeu de paramètres que l’on cherche à optimiser pour prendre la meilleure décision possible. Mathématiquement, le problème revient à minimiser une fonction de l’objectif recherché par des algorithmes itératifs. Le développement de ces derniers dépend alors de la géométrie de la fonction ou de la structure du problème. Dans une première partie, cette thèse étudie comment l’acuité d’une fonction autour de ses minima peut être exploitée par le redémarrage d’algorithmes classiques. Les schémas optimaux sont présentés pour des problèmes convexes généraux. Ils nécessitent cependant une description complète de la fonction, ce qui est rarement disponible. Des stratégies adaptatives sont donc développées et prouvées être quasi-optimales. Une analyse spécifique est ensuite conduite pour les problèmes parcimonieux qui cherchent des représentations compressées des variables du problème. Leur géométrie conique sous-jacente, qui décrit l’acuité de la fonction de l’objectif, se révèle contrôler à la fois la performance statistique du problème et l’efficacité des procédures d’optimisation par une seule quantité. Une seconde partie est dédiée aux problèmes d’apprentissage statistique. Ceux-ci effectuent une analyse prédictive de données à l’aide d’un large nombre d’exemples. Une approche générique est présentée pour à la fois résoudre le problème de prédiction et le simplifier en groupant soit les variables, les exemples ou les tâches. Des méthodes algorithmiques systématiques sont développées en analysant la géométrie induite par une partition des données. Une analyse théorique est finalement conduite lorsque les variables sont groupées par analogie avec les méthodes parcimonieuses. / In numerous fields such as machine learning, operational research or circuit design, a task is modeled by a set of parameters to be optimized in order to take the best possible decision. Formally, the problem amounts to minimize a function describing the desired objective with iterative algorithms. The development of these latter depends then on the characterization of the geometry of the function or the structure of the problem. In a first part, this thesis studies how sharpness of a function around its minimizers can be exploited by restarting classical algorithms. Optimal schemes are presented for general convex problems. They require however a complete description of the function that is rarely available. Adaptive strategies are therefore developed and shown to achieve nearly optimal rates. A specific analysis is then carried out for sparse problems that seek for compressed representation of the variables of the problem. Their underlying conic geometry, that describes sharpness of the objective, is shown to control both the statistical performance of the problem and the efficiency of dedicated optimization methods by a single quantity. A second part is dedicated to machine learning problems. These perform predictive analysis of data from large set of examples. A generic framework is presented to both solve the prediction problem and simplify it by grouping either features, samples or tasks. Systematic algorithmic approaches are developed by analyzing the geometry induced by partitions of the data. A theoretical analysis is then carried out for grouping features by analogy to sparse methods.

Le but de l’apprentissage supervisé est d’inférer des relations entre un phénomène que l’on souhaite prédire et des variables « explicatives ». À cette fin, on dispose d’observations de multiples réalisations du phénomène, à partir desquelles on propose une règle de prédiction. L’émergence récente de sources de données à très grande échelle, tant par le nombre d’observations effectuées (en analyse d’image, par exemple) que par le grand nombre de variables explicatives (en génétique), a fait émerger deux difficultés : d’une part, il devient difficile d’éviter l’écueil du sur-apprentissage lorsque le nombre de variables explicatives est très supérieur au nombre d’observations; d’autre part, l’aspect algorithmique devient déterminant, car la seule résolution d’un système linéaire dans les espaces en jeupeut devenir une difficulté majeure. Des algorithmes issus des méthodes d’approximation stochastique proposent uneréponse simultanée à ces deux difficultés : l’utilisation d’une méthode stochastique réduit drastiquement le coût algorithmique, sans dégrader la qualité de la règle de prédiction proposée, en évitant naturellement le sur-apprentissage. En particulier, le cœur de cette thèse portera sur les méthodes de gradient stochastique. Les très populaires méthodes paramétriques proposent comme prédictions des fonctions linéaires d’un ensemble choisi de variables explicatives. Cependant, ces méthodes aboutissent souvent à une approximation imprécise de la structure statistique sous-jacente. Dans le cadre non-paramétrique, qui est un des thèmes centraux de cette thèse, la restriction aux prédicteurs linéaires est levée. La classe de fonctions dans laquelle le prédicteur est construit dépend elle-même des observations. En pratique, les méthodes non-paramétriques sont cruciales pour diverses applications, en particulier pour l’analyse de données non vectorielles, qui peuvent être associées à un vecteur dans un espace fonctionnel via l’utilisation d’un noyau défini positif. Cela autorise l’utilisation d’algorithmes associés à des données vectorielles, mais exige une compréhension de ces algorithmes dans l’espace non-paramétrique associé : l’espace à noyau reproduisant. Par ailleurs, l’analyse de l’estimation non-paramétrique fournit également un éclairage révélateur sur le cadre paramétrique, lorsque le nombre de prédicteurs surpasse largement le nombre d’observations. La première contribution de cette thèse consiste en une analyse détaillée de l’approximation stochastique dans le cadre non-paramétrique, en particulier dans le cadre des espaces à noyaux reproduisants. Cette analyse permet d’obtenir des taux de convergence optimaux pour l’algorithme de descente de gradient stochastique moyennée. L’analyse proposée s’applique à de nombreux cadres, et une attention particulière est portée à l’utilisation d’hypothèses minimales, ainsi qu’à l’étude des cadres où le nombre d’observations est connu à l’avance, ou peut évoluer. La seconde contribution est de proposer un algorithme, basé sur un principe d’accélération, qui converge à une vitesse optimale, tant du point de vue de l’optimisation que du point de vue statistique. Cela permet, dans le cadre non-paramétrique, d’améliorer la convergence jusqu’au taux optimal, dans certains régimes pour lesquels le premier algorithme analysé restait sous-optimal. Enfin, la troisième contribution de la thèse consiste en l’extension du cadre étudié au delà de la perte des moindres carrés : l’algorithme de descente de gradient stochastiqueest analysé comme une chaine de Markov. Cette approche résulte en une interprétation intuitive, et souligne les différences entre le cadre quadratique et le cadre général. Une méthode simple permettant d’améliorer substantiellement la convergence est également proposée. / The goal of supervised machine learning is to infer relationships between a phenomenon one seeks to predict and “explanatory” variables. To that end, multiple occurrences of the phenomenon are observed, from which a prediction rule is constructed. The last two decades have witnessed the apparition of very large data-sets, both in terms of the number of observations (e.g., in image analysis) and in terms of the number of explanatory variables (e.g., in genetics). This has raised two challenges: first, avoiding the pitfall of over-fitting, especially when the number of explanatory variables is much higher than the number of observations; and second, dealing with the computational constraints, such as when the mere resolution of a linear system becomes a difficulty of its own. Algorithms that take their roots in stochastic approximation methods tackle both of these difficulties simultaneously: these stochastic methods dramatically reduce the computational cost, without degrading the quality of the proposed prediction rule, and they can naturally avoid over-fitting. As a consequence, the core of this thesis will be the study of stochastic gradient methods. The popular parametric methods give predictors which are linear functions of a set ofexplanatory variables. However, they often result in an imprecise approximation of the underlying statistical structure. In the non-parametric setting, which is paramount in this thesis, this restriction is lifted. The class of functions from which the predictor is proposed depends on the observations. In practice, these methods have multiple purposes, and are essential for learning with non-vectorial data, which can be mapped onto a vector in a functional space using a positive definite kernel. This allows to use algorithms designed for vectorial data, but requires the analysis to be made in the non-parametric associated space: the reproducing kernel Hilbert space. Moreover, the analysis of non-parametric regression also sheds some light on the parametric setting when the number of predictors is much larger than the number of observations. The first contribution of this thesis is to provide a detailed analysis of stochastic approximation in the non-parametric setting, precisely in reproducing kernel Hilbert spaces. This analysis proves optimal convergence rates for the averaged stochastic gradient descent algorithm. As we take special care in using minimal assumptions, it applies to numerous situations, and covers both the settings in which the number of observations is known a priori, and situations in which the learning algorithm works in an on-line fashion. The second contribution is an algorithm based on acceleration, which converges at optimal speed, both from the optimization point of view and from the statistical one. In the non-parametric setting, this can improve the convergence rate up to optimality, even inparticular regimes for which the first algorithm remains sub-optimal. Finally, the third contribution of the thesis consists in an extension of the framework beyond the least-square loss. The stochastic gradient descent algorithm is analyzed as a Markov chain. This point of view leads to an intuitive and insightful interpretation, that outlines the differences between the quadratic setting and the more general setting. A simple method resulting in provable improvements in the convergence is then proposed.

Le présent manuscrit est composé de deux parties relativement indépendantes.La première partie est consacrée au problème de la stéréovision binoculaire, et plus particulièrement au traitement de l'occultation. En partant d'une analyse de ce phénomène, nous en déduisons un modèle de régularité qui inclut une contrainte convexe de visibilité. La fonctionnelle d'énergie qui en résulte est minimisée par relaxation convexe. Les zones occultées sont alors détectées grâce à la pente horizontale de la carte de disparité avant d'être densifiées.Une autre méthode gérant l'occultation est la méthode des graph cuts proposée par Kolmogorov et Zabih. L'efficacité de cette méthode justifie son adaptation à deux problèmes auxiliaires rencontrés en stéréovision, qui sont la densification de cartes éparses et le raffinement subpixellique de cartes pixelliques.La seconde partie de ce manuscrit traite de manière plus générale de deux algorithmes d'optimisation convexe, pour lequels deux variantes accélérées sont proposées. Le premier est la méthode des directions alternées (ADMM). On montre qu'un léger relâchement de contraintes dans les paramètres de cette méthode permet d'obtenir un taux de convergence théorique plus intéressant.Le second est un algorithme de descentes proximales alternées, qui permet de paralléliser la résolution approchée du problème Rudin-Osher-Fatemi (ROF) de débruitage pur dans le cas des images couleurs. Une accélération de type FISTA est également proposée. / This thesis is splitted into two relatively independant parts. The first part is devoted to the binocular stereovision problem, specifically to the occlusion handling. An analysis of this phenomena leads to a regularity model which includes a convex visibility constraint. The resulting energy functional is minimized by convex relaxation. The occluded areas are then detected thanks to the horizontal slope of the disparity map and densified. Another method with occlusion handling was proposed by Kolmogorov and Zabih. Because of its efficiency, we adapted it to two auxiliary problems encountered in stereovision, namely the densification of sparse disparity maps and the subpixel refinement of pixel-accurate maps.The second part of this thesis studies two convex optimization algorithms, for which an acceleration is proposed. The first one is the Alternating Direction Method of Multipliers (ADMM). A slight relaxation in the parameter choice is shown to enhance the convergence rate. The second one is an alternating proximal descent algorithm, which allows a parallel approximate resolution of the Rudin-Osher-Fatemi (ROF) pure denoising model, in color-image case. A FISTA-like acceleration is also proposed.

Cette thèse aborde le sujet de la régression linéaire dans différents cadres, liés notamment à l’apprentissage. Les deux premiers chapitres présentent le contexte des travaux, leurs apports et les outils mathématiques utilisés. Le troisième chapitre est consacré à la construction d’une fonction de régularisation optimale, permettant par exemple d’améliorer sur le plan théorique la régularisation de l’estimateur LASSO. Le quatrième chapitre présente, dans le domaine de l’optimisation convexe séquentielle, des accélérations d’un algorithme récent et prometteur, MetaGrad, et une conversion d’un cadre dit “séquentiel déterministe" vers un cadre dit “batch stochastique" pour cet algorithme. Le cinquième chapitre s’intéresse à des prévisions successives par intervalles, fondées sur l’agrégation de prédicteurs, sans retour d’expérience intermédiaire ni modélisation stochastique. Enfin, le sixième chapitre applique à un jeu de données pétrolières plusieurs méthodes d’agrégation, aboutissant à des prévisions ponctuelles court-terme et des intervalles de prévision long-terme. / This thesis tackles the topic of linear regression, within several frameworks, mainly linked to statistical learning. The first and second chapters present the context, the results and the mathematical tools of the manuscript. In the third chapter, we provide a way of building an optimal regularization function, improving for instance, in a theoretical way, the LASSO estimator. The fourth chapter presents, in the field of online convex optimization, speed-ups for a recent and promising algorithm, MetaGrad, and shows how to transfer its guarantees from a so-called “online deterministic setting" to a “stochastic batch setting". In the fifth chapter, we introduce a new method to forecast successive intervals by aggregating predictors, without intermediate feedback nor stochastic modeling. The sixth chapter applies several aggregation methods to an oil production dataset, forecasting short-term precise values and long-term intervals.

Le traitement massif et automatique des données requiert le développement de techniques de filtration des informations les plus importantes. Parmi ces méthodes, celles présentant des structures parcimonieuses se sont révélées idoines pour améliorer l’efficacité statistique et computationnelle des estimateurs, dans un contexte de grandes dimensions. Elles s’expriment souvent comme solution de la minimisation du risque empirique régularisé s’écrivant comme une somme d’un terme lisse qui mesure la qualité de l’ajustement aux données, et d’un terme non lisse qui pénalise les solutions complexes. Cependant, une telle manière d’inclure des informations a priori, introduit de nombreuses difficultés numériques pour résoudre le problème d’optimisation sous-jacent et pour calibrer le niveau de régularisation. Ces problématiques ont été au coeur des questions que nous avons abordées dans cette thèse.Une technique récente, appelée «Screening Rules», propose d’ignorer certaines variables pendant le processus d’optimisation en tirant bénéfice de la parcimonie attendue des solutions. Ces règles d’élimination sont dites sûres lorsqu’elles garantissent de ne pas rejeter les variables à tort. Nous proposons un cadre unifié pour identifier les structures importantes dans ces problèmes d’optimisation convexes et nous introduisons les règles «Gap Safe Screening Rules». Elles permettent d’obtenir des gains considérables en temps de calcul grâce à la réduction de la dimension induite par cette méthode. De plus, elles s’incorporent facilement aux algorithmes itératifs et s’appliquent à un plus grand nombre de problèmes que les méthodes précédentes.Pour trouver un bon compromis entre minimisation du risque et introduction d’un biais d’apprentissage, les algorithmes d’homotopie offrent la possibilité de tracer la courbe des solutions en fonction du paramètre de régularisation. Toutefois, ils présentent des instabilités numériques dues à plusieurs inversions de matrice, et sont souvent coûteux en grande dimension. Aussi, ils ont des complexités exponentielles en la dimension du modèle dans des cas défavorables. En autorisant des solutions approchées, une approximation de la courbe des solutions permet de contourner les inconvénients susmentionnés. Nous revisitons les techniques d’approximation des chemins de régularisation pour une tolérance prédéfinie, et nous analysons leur complexité en fonction de la régularité des fonctions de perte en jeu. Il s’ensuit une proposition d’algorithmes optimaux ainsi que diverses stratégies d’exploration de l’espace des paramètres. Ceci permet de proposer une méthode de calibration de la régularisation avec une garantie de convergence globale pour la minimisation du risque empirique sur les données de validation.Le Lasso, un des estimateurs parcimonieux les plus célèbres et les plus étudiés, repose sur une théorie statistique qui suggère de choisir la régularisation en fonction de la variance des observations. Ceci est difficilement utilisable en pratique car, la variance du modèle est une quantité souvent inconnue. Dans de tels cas, il est possible d’optimiser conjointement les coefficients de régression et le niveau de bruit. Ces estimations concomitantes, apparues dans la littérature sous les noms de Scaled Lasso, Square-Root Lasso, fournissent des résultats théoriques aussi satisfaisants que celui du Lasso tout en étant indépendant de la variance réelle. Bien que présentant des avancées théoriques et pratiques importantes, ces méthodes sont aussi numériquement instables et les algorithmes actuellement disponibles sont coûteux en temps de calcul. Nous illustrons ces difficultés et nous proposons à la fois des modifications basées sur des techniques de lissage pour accroitre la stabilité numérique de ces estimateurs, ainsi qu’un algorithme plus efficace pour les obtenir. / Massive and automatic data processing requires the development of techniques able to filter the most important information. Among these methods, those with sparse structures have been shown to improve the statistical and computational efficiency of estimators in a context of large dimension. They can often be expressed as a solution of regularized empirical risk minimization and generally lead to non differentiable optimization problems in the form of a sum of a smooth term, measuring the quality of the fit, and a non-smooth term, penalizing complex solutions. Although it has considerable advantages, such a way of including prior information, unfortunately introduces many numerical difficulties both for solving the underlying optimization problem and to calibrate the level of regularization. Solving these issues has been at the heart of this thesis. A recently introduced technique, called "Screening Rules", proposes to ignore some variables during the optimization process by benefiting from the expected sparsity of the solutions. These elimination rules are said to be safe when the procedure guarantees to not reject any variable wrongly. In this work, we propose a unified framework for identifying important structures in these convex optimization problems and we introduce the "Gap Safe Screening Rules". They allows to obtain significant gains in computational time thanks to the dimensionality reduction induced by this method. In addition, they can be easily inserted into iterative algorithms and apply to a large number of problems.To find a good compromise between minimizing risk and introducing a learning bias, (exact) homotopy continuation algorithms offer the possibility of tracking the curve of the solutions as a function of the regularization parameters. However, they exhibit numerical instabilities due to several matrix inversions and are often expensive in large dimension. Another weakness is that a worst-case analysis shows that they have exact complexities that are exponential in the dimension of the model parameter. Allowing approximated solutions makes possible to circumvent the aforementioned drawbacks by approximating the curve of the solutions. In this thesis, we revisit the approximation techniques of the regularization paths given a predefined tolerance and we propose an in-depth analysis of their complexity w.r.t. the regularity of the loss functions involved. Hence, we propose optimal algorithms as well as various strategies for exploring the parameters space. We also provide calibration method (for the regularization parameter) that enjoys globalconvergence guarantees for the minimization of the empirical risk on the validation data.Among sparse regularization methods, the Lasso is one of the most celebrated and studied. Its statistical theory suggests choosing the level of regularization according to the amount of variance in the observations, which is difficult to use in practice because the variance of the model is oftenan unknown quantity. In such case, it is possible to jointly optimize the regression parameter as well as the level of noise. These concomitant estimates, appeared in the literature under the names of Scaled Lasso or Square-Root Lasso, and provide theoretical results as sharp as that of theLasso while being independent of the actual noise level of the observations. Although presenting important advances, these methods are numerically unstable and the currently available algorithms are expensive in computation time. We illustrate these difficulties and we propose modifications based on smoothing techniques to increase stability of these estimators as well as to introduce a faster algorithm.

Cette thèse porte sur la mise en correspondance stéréoscopique ainsi que sur son application à la détection des obstacles routiers à partir d'un système de vision stéréoscopique. La mise en correspondance est une étape cruciale dans la reconstruction de la structure tridimensionnelle de la scène observée. Elle consiste à retrouver les pixels homologues dans deux images prises de deux points de vue différents, et se ramène à un problème d'estimation d'un champ de disparité. La première partie de ma thèse a porté sur l'estimation de la disparité, dans le cadre d'une approche ensembliste, en minimisant une fonction objective convexe sur l'intersection d'ensembles convexes, construits à partir des connaissances a priori et des observations. Dans la plupart des applications de stéréovision, le champ de disparité doit être lisse dans les zones homogènes et les zones faiblement texturées. L'une de nos contributions a consisté à proposer différentes contraintes de régularisation satisfaisant cette propriété. Pour résoudre le problème d'optimisation considéré, nous utilisons un algorithme efficace itératif par bloc. La deuxième partie traite du problème d'estimation de la disparité en présence de changements d'illumination dans la scène observée. Nous considérons pour cela un modèle d'illumination multiplicatif qui permet de compenser les variations spatiales de luminosité de la scène. Enfin, dans la troisième partie, nous appliquons notre méthode d'estimation de la disparité robuste aux variations d'illumination pour la détection des obstacles routiers.