.

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

Une approche classique pour traiter les problèmes d’optimisation avec incertitude à deux- et multi-étapes est d’utiliser l’analyse par scénario. Pour ce faire, l’incertitude de certaines données du problème est modélisée par vecteurs aléatoires avec des supports finis spécifiques aux étapes. Chacune de ces réalisations représente un scénario. En utilisant des scénarios, il est possible d’étudier des versions plus simples (sous-problèmes) du problème original. Comme technique de décomposition par scénario, l’algorithme de recouvrement progressif est une des méthodes les plus populaires pour résoudre les problèmes de programmation stochastique multi-étapes. Malgré la décomposition complète par scénario, l’efficacité de la méthode du recouvrement progressif est très sensible à certains aspects pratiques, tels que le choix du paramètre de pénalisation et la manipulation du terme quadratique dans la fonction objectif du lagrangien augmenté. Pour le choix du paramètre de pénalisation, nous examinons quelques-unes des méthodes populaires, et nous proposons une nouvelle stratégie adaptive qui vise à mieux suivre le processus de l’algorithme. Des expériences numériques sur des exemples de problèmes stochastiques linéaires multi-étapes suggèrent que la plupart des techniques existantes peuvent présenter une convergence prématurée à une solution sous-optimale ou converger vers la solution optimale, mais avec un taux très lent. En revanche, la nouvelle stratégie paraît robuste et efficace. Elle a convergé vers l’optimalité dans toutes nos expériences et a été la plus rapide dans la plupart des cas. Pour la question de la manipulation du terme quadratique, nous faisons une revue des techniques existantes et nous proposons l’idée de remplacer le terme quadratique par un terme linéaire. Bien que qu’il nous reste encore à tester notre méthode, nous avons l’intuition qu’elle réduira certaines difficultés numériques et théoriques de la méthode de recouvrement progressif. / In the literature of optimization problems under uncertainty a common approach of dealing with two- and multi-stage problems is to use scenario analysis. To do so, the uncertainty of some data in the problem is modeled by stage specific random vectors with finite supports. Each realization is called a scenario. By using scenarios, it is possible to study smaller versions (subproblems) of the underlying problem. As a scenario decomposition technique, the progressive hedging algorithm is one of the most popular methods in multi-stage stochastic programming problems. In spite of full decomposition over scenarios, progressive hedging efficiency is greatly sensitive to some practical aspects, such as the choice of the penalty parameter and handling the quadratic term in the augmented Lagrangian objective function. For the choice of the penalty parameter, we review some of the popular methods, and design a novel adaptive strategy that aims to better follow the algorithm process. Numerical experiments on linear multistage stochastic test problems suggest that most of the existing techniques may exhibit premature convergence to a sub-optimal solution or converge to the optimal solution, but at a very slow rate. In contrast, the new strategy appears to be robust and efficient, converging to optimality in all our experiments and being the fastest in most of them. For the question of handling the quadratic term, we review some existing techniques and we suggest to replace the quadratic term with a linear one. Although this method has yet to be tested, we have the intuition that it will reduce some numerical and theoretical difficulties of progressive hedging in linear problems.

Cette thèse étudie deux modèles paramétriques et non paramétriques pour le changement de représentation. L'objectif des deux modèles diffère. Le premier cherche une représentation en plus grande dimension pour gagner en robustesse. L'objectif est de répartir uniformément l’information d’un signal sur toutes les composantes de sa représentation en plus grande dimension. La recherche d'un tel code s'exprime comme un problème inverse impliquant une régularisation de type norme infinie. Nous proposons une formulation bayésienne du problème impliquant une nouvelle loi de probabilité baptisée démocratique, qui pénalise les fortes amplitudes. Deux algorithmes MCMC proximaux sont présentés pour approcher des estimateurs bayésiens. La méthode non supervisée présentée est appelée BAC-1. Des expériences numériques illustrent les performances de l’approche pour la réduction de facteur de crête. Le second modèle identifie un sous-espace pertinent de dimension réduite à des fins de modélisation. Mais les méthodes probabilistes proposées nécessitent généralement de fixer à l'avance la dimension du sous-espace. Ce travail introduit BNP-PCA, une version bayésienne non paramétrique de l'analyse en composantes principales. La méthode couple une loi uniforme sur les bases orthonormales à un a priori non paramétrique de type buffet indien pour favoriser une utilisation parcimonieuse des composantes principales et aucun réglage n'est nécessaire. L'inférence est réalisée à l'aide des méthodes MCMC. L'estimation de la dimension du sous-espace et le comportement numérique de BNP-PCA sont étudiés. Nous montrons la flexibilité de BNP-PCA sur deux applications / This thesis proposes Bayesian parametric and nonparametric models for signal representation. The first model infers a higher dimensional representation of a signal for sake of robustness by enforcing the information to be spread uniformly. These so called anti-sparse representations are obtained by solving a linear inverse problem with an infinite-norm penalty. We propose in this thesis a Bayesian formulation of anti-sparse coding involving a new probability distribution, referred to as the democratic prior. A Gibbs and two proximal samplers are proposed to approximate Bayesian estimators. The algorithm is called BAC-1. Simulations on synthetic data illustrate the performances of the two proposed samplers and the results are compared with state-of-the art methods. The second model identifies a lower dimensional representation of a signal for modelisation and model selection. Principal component analysis is very popular to perform dimension reduction. The selection of the number of significant components is essential but often based on some practical heuristics depending on the application. Few works have proposed a probabilistic approach to infer the number of significant components. We propose a Bayesian nonparametric principal component analysis called BNP-PCA. The proposed model involves an Indian buffet process to promote a parsimonious use of principal components, which is assigned a prior distribution defined on the manifold of orthonormal basis. Inference is done using MCMC methods. The estimators of the latent dimension are theoretically and empirically studied. The relevance of the approach is assessed on two applications

L'étude et l'introduction de nouveaux systèmes dynamiques<br /> de type gradient sont l'objet central de cette thèse. Le<br /> caractère dissipatif de telles dynamiques est au coeur de<br /> nombreux domaines en mathématiques : optimisation,<br /> mécanique, équations d'évolutions en dimension infinie.<br /><br />Dans une première partie, les champs de gradients (ou de sous-différentiels<br /> de fonction convexe) sont contrôlés à l'aide d'opérateurs-barrières. <br />La motivation essentielle est d'obtenir<br /> des méthodes intérieures de descente en vue d'optimiser<br /> une fonction sous des contraintes convexes. Le cadre<br /> d'étude proposé permet d'unifier dans un même formalisme de nombreuses<br /> méthodes continues : gradient projeté, plus grande pente riemannienne,<br /> méthode continue de Newton... Parmi les conséquences de <br />la généralisation proposée, on peut, par exemple, évoquer des <br /> résultats abstraits de viabilité et de convergence globale. Toujours <br />dans cette <br />perspective, les fonctions de Legendre jouent un rôle crucial~:<br /> elles permettent d'une part de donner lieu à des structures<br /> riemanniennes possédant de nombreuses propriétés - parmi lesquelles une<br /> propriété d'intégration caractéristique remarquable -, et d'autre part, <br /> elles fournissent en dimension infinie un cadre intéressant<br /> pour l'étude de certaines équations d'évolution de type<br /> parabolique.<br /><br />La deuxième partie est consacrée à l'étude de systèmes<br /> dynamiques du second ordre en temps avec une dissipation géométrique<br /> de type hessien. Outre leur intérêt en optimisation<br /> et leurs liens avec les méthodes de type Newton, ces systèmes<br /> sont d'une grande souplesse et permettent d'approcher certains <br />phénomènes non-lisses en mécanique unilatérale. En guise d'application,<br /> il est en effet prouvé que les systèmes considérés permettent <br />d'obtenir à la limite des dynamiques <br />satisfaisant des lois de chocs inélastiques. Les<br /> perspectives de cette étude ouvrent en particulier la voie à une approche <br />alternative de certains systèmes d'inégalités variationnelles de type <br />hyperbolique.<br /><br /><br />L'une des préoccupations majeures de cette thèse est la question<br /> de la convergence des orbites des systèmes étudiés. Dans le <br /> cadre de la minimisation convexe, quasi-convexe, ou analytique, de nombreux<br /> résultats sont proposés : convergence globale, , <br />vitesse de convergence, contrôle asymptotique, attractivité des <br /> minima sous contraintes en dimension infinie.