Academic literature on the topic 'Algorithme des directions alternées'

Cet entretien avec Dr Francine Shapiro, inventrice et conceptrice de la thérapie EMDR (Eye Movement Desensitization and Reprocessing : thérapie d’intégration neuro-émotionnelle par des stimulations bilatérales alternées) apporte un aperçu de l’histoire et de l’évolution de l’EMDR depuis ses origines jusqu’aux résultats actuels et à leur utilisation, ainsi que les directions futures pour la recherche et le développement de la clinique. Dr Shapiro examine les traditions psychologiques qui ont guidé le développement de l’EMDR et le modèle de l’information adaptative, ainsi que les implications pour les traitements actuels. La logique qui sous-tend l’application de l’EMDR à un large éventail de troubles est envisagée, tout comme son intégration avec d’autres approches thérapeutiques. Les sujets évoqués comprennent la recherche sur le rôle des mouvements oculaires, l’utilisation de l’EMDR avec les vétérans de guerre, les troubles somatoformes, les questions de l’attachement et les caractéristiques uniques de l’EMDR qui ont permis son utilisation lors d’interventions de crise à travers le monde.

We introduce a new optimization strategy to compute numerical approximations of minimizers for optimal control problems governed by scalar conservation laws in the presence of shocks. We focus on the 1 - d inviscid Burgers equation. We first prove the existence of minimizers and, by a Γ-convergence argument, the convergence of discrete minima obtained by means of numerical approximation schemes satisfying the so-called one-sided Lipschitz condition (OSLC). Then we address the problem of developing efficient descent algorithms. We first consider and compare the existing two possible approaches: the so-called discrete approach, based on a direct computation of gradients in the discrete problem and the so-called continuous one, where the discrete descent direction is obtained as a discrete copy of the continuous one. When optimal solutions have shock discontinuities, both approaches produce highly oscillating minimizing sequences and the effective descent rate is very weak. As a solution we propose a new method, that we shall call alternating descent method, that uses the recent developments of generalized tangent vectors and the linearization around discontinuous solutions. This method distinguishes and alternates the descent directions that move the shock and those that perturb the profile of the solution away of it producing very efficient and fast descent algorithms.

We combine ideas from uni-directional and bi-directional heuristic search, and approximation algorithms for the Traveling Salesman Problem, to develop a novel framework for a Multi-Goal Path Finding (MGPF) problem that provides a 2-approximation guarantee. MGPF aims to find a least-cost path from an origin to a destination such that each node in a given set of goals is visited at least once along the path. We present numerical results to illustrate the advantages of our framework over conventional alternates in terms of the number of expanded nodes and run time.

Hierarchical metric-space clustering methods have been commonly used to organize proteomes into taxonomies. Consequently, it is often anticipated that hierarchical clustering can be leveraged as a basis for scalable database index structures capable of managing the hyper-exponential growth of sequence data. M-tree is one such data structure specialized for the management of large data sets on disk. We explore the application of M-trees to the storage and retrieval of peptide sequence data. Exploiting a technique first suggested by Myers, we organize the database as records of fixed length substrings. Empirical results are promising. However, metric-space indexes are subject to "the curse of dimensionality" and the ultimate performance of an index is sensitive to the quality of the initial construction of the index. We introduce new hierarchical bulk-load algorithm that alternates between top-down and bottom-up clustering to initialize the index. Using the Yeast Proteomes, the bi-directional bulk load produces a more effective index than the existing M-tree initialization algorithms.

Single sensor scanning (hereafter SSS) used to inspect cracks on paramagnetic materials can measure the distribution of the root mean squared value (RMS) of the magnetic field around crack tips quantitatively when sheet type current is induced on the specimen. The vertical direction magnetic field alternates to the surface of the crack tips because the sheet type induced current on the specimen is distorted by the existence of the crack in an SSS system. The RMS distribution of the magnetic field, which can be measured by using SSS, depends on the crack size and shape, so it can be used to evaluate a crack size quantitatively. An algorithm of quantitative nondestructive testing and evaluation of cracks of various shapes and sizes on the aluminum alloy, Al7075 is proposed in this paper.

Fire spread information on a large scale is still a missing key layer for a complete description of fire regimes. We developed a novel multilevel object-based methodology that extracts valuable information about fire dynamics from Moderate Resolution Imaging Spectroradiometer (MODIS) burned area data. Besides the large area capabilities, this approach also derives very detailed information for every single fire regarding timing and location of its ignition, as well as detailed directional multitemporal spread information. The approach is a top–down approach and a multilevel segmentation strategy is used to gradually refine the individual object membership. The multitemporal segmentation alternates between recursive seed point identification and queue-based fire tracking. The algorithm relies on only a few input parameters that control the segmentation with spatial and temporal distance thresholds. We present exemplary results that indicate the potential for further use of the derived parameters.

Face recognition using a single reference image per subject is challenging, above all when referring to a large gallery of subjects. Furthermore, the problem hardness seriously increases when the images are acquired in unconstrained conditions. In this paper we address the challenging Single Sample Per Person (SSPP) problem considering large datasets of images acquired in the wild, thus possibly featuring illumination, pose, face expression, partial occlusions, and low-resolution hurdles. The proposed technique alternates a sparse dictionary learning technique based on the method of optimal direction and the iterative ℓ 0 -norm minimization algorithm called k-LiMapS. It works on robust deep-learned features, provided that the image variability is extended by standard augmentation techniques. Experiments show the effectiveness of our method against the hardness introduced above: first, we report extensive experiments on the unconstrained LFW dataset when referring to large galleries up to 1680 subjects; second, we present experiments on very low-resolution test images up to 8 × 8 pixels; third, tests on the AR dataset are analyzed against specific disguises such as partial occlusions, facial expressions, and illumination problems. In all the three scenarios our method outperforms the state-of-the-art approaches adopting similar configurations.

Component-based synthesis seeks to build programs using the APIs provided by a set of libraries. Oftentimes, these APIs have effects, which make it challenging to reason about the correctness of potential synthesis candidates. This is because changes to global state made by effectful library procedures affect how they may be composed together, yielding an intractably large search space that can confound typical enumerative synthesis techniques. If the nature of these effects are exposed as part of their specification, however, deductive synthesis approaches can be used to help guide the search for components. In this paper, we present a new specification-guided synthesis procedure that uses Hoare-style pre- and post-conditions to express fine-grained effects of potential library component candidates to drive a bi-directional synthesis search strategy. The procedure alternates between a forward search process that seeks to build larger terms given an existing context but which is otherwise unaware of the actual goal, alongside a backward search mechanism that seeks terms consistent with the desired goal but which is otherwise unaware of the context from which these terms must be synthesized. To further improve efficiency and scalability, we integrate a conflict-driven learning procedure into the synthesis algorithm that provides a semantic characterization of previously encountered unsuccessful search paths that is used to prune the space of possible candidates as synthesis proceeds. We have implemented our ideas in a tool called and demonstrate its effectiveness on a number of challenging synthesis problems defined over OCaml libraries equipped with effectful specifications.

Label Propagation is not only a well-known machine learning algorithm for classification, but it is also an effective method for discovering communities and connected components in networks. We propose a new Direction-Optimizing Label Propagation Algorithm (DOLPA) framework that enhances the performance of the standard Label Propagation Algorithm (LPA), increases its scalability, and extends its versatility and application scope. As a central feature, the DOLPA framework relies on the use of frontiers and alternates between label push and label pull operations to attain high performance. It is formulated in such a way that the same basic algorithm can be used for finding communities or connected components in graphs by only changing the objective function used. Additionally, DOLPA has parameters for tuning the processing order of vertices in a graph to reduce the number of edges visited and improve the quality of solution obtained. We present the design and implementation of the enhanced algorithm as well as our shared-memory parallelization of it using OpenMP. We also present an extensive experimental evaluation of our implementations using the LFR benchmark and real-world networks drawn from various domains. Compared with an implementation of LPA for community detection available in a widely used network analysis software, we achieve at most five times the F-Score while maintaining similar runtime for graphs with overlapping communities. We also compare DOLPA against an implementation of the Louvain method for community detection using the same LFR-graphs and show that DOLPA achieves about three times the F-Score at just 10% of the runtime. For connected component decomposition, our algorithm achieves orders of magnitude speedups over the basic LP-based algorithm on large diameter graphs, up to 13.2 × speedup over the Shiloach-Vishkin algorithm, and up to 1.6 × speedup over Afforest on an Intel Xeon processor using 40 threads.

Soit l'equation d'evolution ecrite formellement sous la forme (1) du/dt=cu + f(t). Decomposons l'operateur c en une somme de deux operations lineaires a et b. Cette decomposition correspond soit a une decomposition en directions de differentiation differentes, soit a une decomposition de domaine. Notons e#t#a (resp e#t#b) l'exponentielle formelle de a (resp b). L'objet de ce travail est l'etude theorique et numerique de certaines formules d'ordre eleve en temps, construites a partir de formules du type directions alternees, bien que les idees essentielles soient assez independantes du type precis de decomposition en une somme a + b. Plus precisement ces formules sont des extrapolations de produits d'exponentielles et des extrapolations de la formule de peaceman rachford (donnee en (1. 7), chapitre 5). Cette etude est repartie sur cinq chapitres. Dans le premier chapitre, des commutateurs de semi-groupes holomorphes permettent d'etablir, pour des operateurs de diffusion a et b particuliers et dans le cas periodique, la stabilite des formules m#1(t) = 4/3e#t#a#/#4e#t#b#/#2e#t#a#/#2e#t#b#/#2e#t#a#/#4 1/3e#t#a#/#2e#t#be#t#a#/#2 (2) m#2(t) = 2/3 (e#t#a#/#2e#t#be#t#a#/#2 + e#t#b#/#2e#t#ae#t#b#/#2) 1/6 (e#t#ae#t#b + e#t#be#t#a) d'ordre respectivement 4 et 3. Le second chapitre etablit l'estimation e#-#t#ve#2#t#e#-#t#v e#-#2#t#(#-##+#v#) = o(t#2) avec des hypotheses relativement faibles sur le potentiel v. Dans le troisieme chapitre, on discretise par la methode des differences finies des operateurs de diffusion a et b particuliers, et montre, dans le cas periodique, qu'il existe une constante c independante du pas de discretisation h telle que (3) e#t#a#he#2#t#b#he#t#a#h e#2#t#(#a#h#+#b#h#) ct. Enfin les quatrieme et cinquieme chapitres sont consacres a l'implementation de toutes les formules proposees et aux tests numeriques

L'intérêt de l'échantillonnage compressé dans l'imagerie ultrasonore a été récemment évalué largement par plusieurs équipes de recherche. Suite aux différentes configurations d'application, il a été démontré que les données RF peuvent être reconstituées à partir d'un faible nombre de mesures et / ou en utilisant un nombre réduit d'émission d'impulsions ultrasonores. Selon le modèle de l'échantillonnage compressé, la résolution des images ultrasonores reconstruites à partir des mesures compressées dépend principalement de trois aspects: la configuration d'acquisition, c.à.d. l'incohérence de la matrice d'échantillonnage, la régularisation de l'image, c.à.d. l'a priori de parcimonie et la technique d'optimisation. Nous nous sommes concentrés principalement sur les deux derniers aspects dans cette thèse. Néanmoins, la résolution spatiale d'image RF, le contraste et le rapport signal sur bruit dépendent de la bande passante limitée du transducteur d'imagerie et du phénomène physique lié à la propagation des ondes ultrasonores. Pour surmonter ces limitations, plusieurs techniques de traitement d'image en fonction de déconvolution ont été proposées pour améliorer les images ultrasonores. Dans cette thèse, nous proposons d'abord un nouveau cadre de travail pour l'imagerie ultrasonore, nommé déconvolution compressée, pour combiner l'échantillonnage compressé et la déconvolution. Exploitant une formulation unifiée du modèle d'acquisition directe, combinant des projections aléatoires et une convolution 2D avec une réponse impulsionnelle spatialement invariante, l'avantage de ce cadre de travail est la réduction du volume de données et l'amélioration de la qualité de l'image. Une méthode d'optimisation basée sur l'algorithme des directions alternées est ensuite proposée pour inverser le modèle linéaire, en incluant deux termes de régularisation exprimant la parcimonie des images RF dans une base donnée et l'hypothèse statistique gaussienne généralisée sur les fonctions de réflectivité des tissus. Nous améliorons les résultats ensuite par la méthode basée sur l'algorithme des directions simultanées. Les deux algorithmes sont évalués sur des données simulées et des données in vivo. Avec les techniques de régularisation, une nouvelle approche basée sur la minimisation alternée est finalement développée pour estimer conjointement les fonctions de réflectivité des tissus et la réponse impulsionnelle. Une investigation préliminaire est effectuée sur des données simulées
The interest of compressive sampling in ultrasound imaging has been recently extensively evaluated by several research teams. Following the different application setups, it has been shown that the RF data may be reconstructed from a small number of measurements and/or using a reduced number of ultrasound pulse emissions. According to the model of compressive sampling, the resolution of reconstructed ultrasound images from compressed measurements mainly depends on three aspects: the acquisition setup, i.e. the incoherence of the sampling matrix, the image regularization, i.e. the sparsity prior, and the optimization technique. We mainly focused on the last two aspects in this thesis. Nevertheless, RF image spatial resolution, contrast and signal to noise ratio are affected by the limited bandwidth of the imaging transducer and the physical phenomenon related to Ultrasound wave propagation. To overcome these limitations, several deconvolution-based image processing techniques have been proposed to enhance the ultrasound images. In this thesis, we first propose a novel framework for Ultrasound imaging, named compressive deconvolution, to combine the compressive sampling and deconvolution. Exploiting an unified formulation of the direct acquisition model, combining random projections and 2D convolution with a spatially invariant point spread function, the benefit of this framework is the joint data volume reduction and image quality improvement. An optimization method based on the Alternating Direction Method of Multipliers is then proposed to invert the linear model, including two regularization terms expressing the sparsity of the RF images in a given basis and the generalized Gaussian statistical assumption on tissue reflectivity functions. It is improved afterwards by the method based on the Simultaneous Direction Method of Multipliers. Both algorithms are evaluated on simulated and in vivo data. With regularization techniques, a novel approach based on Alternating Minimization is finally developed to jointly estimate the tissue reflectivity function and the point spread function. A preliminary investigation is made on simulated data

Nous considérons la simulation numérique des écoulements de fluides viscoélatiques. Développant une approximation en temps par la méthode des directions alternées, nous proposons un algorithme entièrement nouveau permettant de découpler le calcul des contraintes de celui des vitesses. D'ordre deux en temps, cette méthode permet de plus le calcul rapide des solutions stationnaires. L'éléments à divergence nulle de Thomas-Raviart est utilisé pour les vitesses, et celui de Lesaint-Raviart pour les contraintes. La méthode est appliquée au problème de l'écoulement de fluides du type Oldroyd dans une contraction brusque (problème de la marche).

Cette thèse est consacrée à la résolution d'inclusions monotones et en particulier de problèmes d'optimisation convexe. D'une part, nous proposons une nouvelle méthode fondée sur une relaxation de l'étape proximale de la méthode de l'inverse partiel ; les tests numériques ont confirmé une amélioration très nette de la vitesse de convergence dans certains cas par rapport aux algorithmes connus. D'autre part, nous proposons une version diagonale de la méthode de Lions-Mercier, ce qui permet notamment en optimisation convexe, de combiner la méthode des directions alternées des multiplicateurs avec une classe importante de méthodes de pénalité.

La FWI (Full Waveform Inversion) est un problème d'optimisation sous contraintes dédié à l'estimation des paramètres constitutifs du sous-sol à partir de mesures parcimonieuses des champs d'ondes sismiques. La FWI est fondée sur des approches locales d'optimisation et sur un espace de recherche réduit obtenu par projection de variables. La non linéarité et le caractère mal posé de la FWI sont deux difficultés majeures. Une source de non linéarité est liée au repliement de la phase, qui conduit à un minimum local dès que le modèle initial n'est pas suffisamment précis. Le caractère mal posé résulte de l'éclairage incomplet du sous-sol depuis la surface, le bruit et les couplages inter-paramètres. L'objectif de cette thèse est de réduire ces deux pathologies par de nouvelles approches d'optimisation et de régularisation. J'améliore tout d'abord la méthode d'inversion par reconstruction des champs d'onde (WRI : Wavefield Reconstruction Inversion). WRI étend l'espace de recherche en calculant les champs d'onde avec une relaxation de l'équation d'onde afin d'ajuster les données avec des modèles imprécis avant d'estimer les paramètres en minimisant les erreurs générées par cette relaxation. Quand ces deux estimations sont effectuées de manière alternée, WRI décompose l'inversion non linéaire en deux sous-problèmes linéaires en vertu de la bilinéarité de l'équation d'onde. WRI a été implémentée avec une méthode de pénalité, nécessitant une adaptation du paramètre de pénalité lors des itérations. Je remédie à cela avec ADMM (Alternating-Direction Method of Multipliers), qui concilie l'extension de l'espace de recherche et la précision de la solution au point de convergence avec un paramètre de pénalité fixe grâce à la mise à jour itérative des multiplicateurs de Lagrange. Une seconde contribution est l'implémentation de contraintes de bornes et de régularisation par variation totale (TV) dans WRI. Suivant la méthode de Split Bregman, des variables auxiliaires permettent de découpler les termes impliquant des normes ℓ2 et ℓ1 et de traiter les seconds efficacement avec des opérateurs de proximité. Ensuite, j'ai combiné une régularisation de Tikhonov et de TV par convolution infimale pour prendre en compte les différentes propriétés statistiques du milieu (constantes par morceau et lisses). Ma thèse aborde ensuite des reconstructions multi-paramètres. Je montre dans un premier temps que la bilinéarité de l'équation d'onde est vérifiée pour les équations de l'elastodynamique. Ensuite, je traite le cas de milieux acoustique VTI où je reconstruis conjointement la vitesse verticale et epsilon pour un modèle synthétique représentatif d'un champ pétrolier en mer du Nord. Je m'intéresse ensuite à l'imagerie de l'atténuation qui est introduite en domaine harmonique sous forme d'une vitesse complexe. J'étends WRI à la reconstruction de paramètres complexes tout en développant une régularisation adaptable à la vitesse réelle et au facteur de qualité. Durant les premières itérations, les champs d'onde reconstruits sont précis uniquement au voisinage des récepteurs. Les imprécisions de la phase pourraient avoir un rôle préjudiciable sur la solution de l'inversion. Afin de réduire cette empreinte, j'estime les paramètres par "phase retrieval", un processus qui vise la reconstruction d'un signal complexe à partir de l'amplitude de sa mesure linéaire. Une fois un premier modèle obtenu, je réinjecte l'information de la phase pour converger vers la solution finale. Je montre la pertinence de cette stratégie lorsque le modèle initial est homogène. WRI a été initialement développée dans le domaine fréquentiel car la reconstruction des champs d'onde y est raisonnablement aisée avec des méthodes d'algèbre linéaire. En domaine temporel, une approche fondée sur un schéma explicite d'intégration temporelle a été proposée mais repose sur une linéarisation autour des sources supposées connues
Full Waveform Inversion (FWI) is a PDE-constrained optimization which reconstructs subsurface parameters from sparse measurements of seismic wavefields. FWI generally relies on local optimization techniques and a reduced-space approach where the wavefields are eliminated from the variables. In this setting, two bottlenecks of FWI are nonlinearity and ill-posedness. One source of nonlinearity is cycle skipping, which drives the inversion to spurious minima when the starting subsurface model is not kinematically accurate enough. Ill-posedness can result from incomplete subsurface illumination, noise and parameter cross-talks. This thesis aims to mitigate these pathologies with new optimization and regularization strategies. I first improve the wavefield reconstruction method (WRI). WRI extends the FWI search space by computing wavefields with a relaxation of the wave equation to match the data from inaccurate parameters. Then, the parameters are updated by minimizing wave equation errors with either alternating optimization or variable projection. In the former case, WRI breaks down FWI into to linear subproblems thanks to wave equation bilinearity. WRI was initially implemented with a penalty method, which requires a tedious adaptation of the penalty parameter in iterations. Here, I replace the penalty method by the alternating-direction method of multipliers (ADMM). I show with numerical examples how ADMM conciliates the search space extension and the accuracy of the solution at the convergence point with fixed penalty parameters thanks to the dual ascent update of the Lagrange multipliers. The second contribution is the implementation of bound constraints and non smooth Total Variation (TV) regularization in ADMM-based WRI. Following the Split Bregman method, suitable auxiliary variables allow for the de-coupling of the ℓ1 and ℓ2 subproblems, the former being solved efficiently with proximity operators. Then, I combine Tikhonov and TV regularizations by infimal convolution to account for the different statistical properties of the subsurface (smoothness and blockiness). At the next step, I show the ability of sparse promoting regularization in reconstruction the model when ultralong offset sparse fixed-spread acquisition such as those carried out with OBN are used. This thesis continues with the extension of the ADMM-based WRI to multiparameter reconstruction in vertical transversely isotropic (VTI) acoustic media. I first show that the bilinearity of the wave equation is satisfied for the elastodynamic equations. I discuss the joint reconstruction of the vertical wavespeed and epsilon in VTI media. Second, I develop ADMM-based WRI for attenuation imaging, where I update wavefield, squared-slowness, and attenuation in an alternating mode since viscoacoustic wave equation can be approximated, with a high degree of accuracy, as a multilinear equation. This alternating solving provides the necessary flexibility to taylor the regularization to each parameter class and invert large data sets. Then, I overcome some limitations of ADMM-based WRI when a crude initial model is used. In this case, the reconstructed wavefields are accurate only near the receivers. The inaccuracy of phase of the wavefields may be the leading factor which drives the inversion towards spurious minimizers. To mitigate the role of the phase during the early iterations, I update the parameters with phase retrieval, a process which reconstructs a signal from magnitude of linear mesurements. This approach combined with efficient regularizations leads to more accurate reconstruction of the shallow structure, which is decisive to drive ADMM-based WRI toward good solutions at higher frequencies. The last part of this PhD is devoted to time-domain WRI, where a challenge is to perform accurate wavefield reconstruction with acceptable computational cost

Les calculs de réactivité constituent une brique fondamentale dans la simulation des coeurs des réacteurs nucléaires. Ceux-ci conduisent à la résolution de problèmes aux valeurs propres généralisées via l'algorithme de la puissance inverse. A chaque itération, on est amené à résoudre un système linéaire de manière approchée via un algorithme d'itérations imbriquées. Il est difficile de traiter les modélisations très fines avec le solveur développé à EDF, au sein de la plate-forme Cocagne, en raison de la consommation mémoire et du temps de calcul. Au cours de cette thèse, on étudie une méthode de décomposition de domaine de type Schur dual. Plusieurs placements de l'algorithme de décomposition de domaine au sein du système d'itérations imbriquées sont envisageables. Deux d'entre eux ont été implémentés et les résultats analysés. Le deuxième placement, utilisant les spécificités des éléments finis de Raviart-Thomas et de l'algorithme des directions alternées, conduit à des résultats très encourageants. Ces résultats permettent d'envisager l'industrialisation de la méthodologie associée.

Cette thèse présente nos contributions àl’inférence et l’apprentissage des modèles graphiquesen vision artificielle. Tout d’abord, nous proposons unenouvelle classe d’algorithmes de décomposition pour résoudrele problème d’appariement de graphes et d’hypergraphes,s’appuyant sur l’algorithme des directionsalternées (ADMM) non convexe. Ces algorithmes sontefficaces en terme de calcul et sont hautement parallélisables.En outre, ils sont également très générauxet peuvent être appliqués à des fonctionnelles d’énergiearbitraires ainsi qu’à des contraintes de correspondancearbitraires. Les expériences montrent qu’ils surpassentles méthodes de pointe existantes sur des benchmarkspopulaires. Ensuite, nous proposons une relaxationcontinue non convexe pour le problème d’estimationdu maximum a posteriori (MAP) dans les champsaléatoires de Markov (MRFs). Nous démontrons quecette relaxation est serrée, c’est-à-dire qu’elle est équivalenteau problème original. Cela nous permet d’appliquerdes méthodes d’optimisation continue pour résoudrele problème initial discret sans perte de précisionaprès arrondissement. Nous étudions deux méthodes degradient populaires, et proposons en outre une solutionplus efficace utilisant l’ADMM non convexe. Les expériencessur plusieurs problèmes réels démontrent quenotre algorithme prend l’avantage sur ceux de pointe,dans différentes configurations. Finalement, nous proposonsune méthode d’apprentissage des paramètres deces modèles graphiques avec des données d’entraînement,basée sur l’ADMM non convexe. Cette méthodeconsiste à visualiser les itérations de l’ADMM commeune séquence d’opérations différenciables, ce qui permetde calculer efficacement le gradient de la perted’apprentissage par rapport aux paramètres du modèle.L’apprentissage peut alors utiliser une descente de gradientstochastique. Nous obtenons donc un frameworkunifié pour l’inférence et l’apprentissage avec l’ADMMnon-convexe. Grâce à sa flexibilité, ce framework permetégalement d’entraîner conjointement de-bout-en-boutun modèle graphique avec un autre modèle, telqu’un réseau de neurones, combinant ainsi les avantagesdes deux. Nous présentons des expériences sur un jeude données de segmentation sémantique populaire, démontrantl’efficacité de notre méthode
This thesis presents our contributions toinference and learning of graph-based models in computervision. First, we propose a novel class of decompositionalgorithms for solving graph and hypergraphmatching based on the nonconvex alternating directionmethod of multipliers (ADMM). These algorithms arecomputationally efficient and highly parallelizable. Furthermore,they are also very general and can be appliedto arbitrary energy functions as well as arbitraryassignment constraints. Experiments show that theyoutperform existing state-of-the-art methods on popularbenchmarks. Second, we propose a nonconvex continuousrelaxation of maximum a posteriori (MAP) inferencein discrete Markov random fields (MRFs). Weshow that this relaxation is tight for arbitrary MRFs.This allows us to apply continuous optimization techniquesto solve the original discrete problem withoutloss in accuracy after rounding. We study two populargradient-based methods, and further propose a more effectivesolution using nonconvex ADMM. Experimentson different real-world problems demonstrate that theproposed ADMM compares favorably with state-of-theartalgorithms in different settings. Finally, we proposea method for learning the parameters of these graphbasedmodels from training data, based on nonconvexADMM. This method consists of viewing ADMM iterationsas a sequence of differentiable operations, whichallows efficient computation of the gradient of the trainingloss with respect to the model parameters, enablingefficient training using stochastic gradient descent. Atthe end we obtain a unified framework for inference andlearning with nonconvex ADMM. Thanks to its flexibility,this framework also allows training jointly endto-end a graph-based model with another model suchas a neural network, thus combining the strengths ofboth. We present experiments on a popular semanticsegmentation dataset, demonstrating the effectivenessof our method

Le démélange spectral est l’un des problèmes centraux pour l’exploitation des images hyperspectrales. En raison de la faible résolution spatiale des imageurs hyperspectraux en télédetection, la surface représentée par un pixel peut contenir plusieurs matériaux. Dans ce contexte, le démélange consiste à estimer les spectres purs (les end members) ainsi que leurs fractions (les abondances) pour chaque pixel de l’image. Le but de cette thèse estde proposer de nouveaux algorithmes de démélange qui visent à améliorer l’estimation des spectres purs et des abondances. En particulier, les algorithmes de démélange proposés s’inscrivent dans le cadre du démélange non-supervisé et non-linéaire. Dans un premier temps, on propose un algorithme de démelange non-supervisé dans lequel une régularisation favorisant la parcimonie des groupes est utilisée pour identifier les spectres purs parmi les observations. Une extension de ce premier algorithme permet de prendre en compte la présence du bruit parmi les observations choisies comme étant les plus pures. Dans un second temps, les connaissances a priori des ressemblances entre les spectres à l’échelle localeet non-locale ainsi que leurs positions dans l’image sont exploitées pour construire un graphe adapté à l’image. Ce graphe est ensuite incorporé dans le problème de démélange non supervisé par le biais d’une régularisation basée sur le Laplacian du graphe. Enfin, deux algorithmes de démélange non-linéaires sont proposés dans le cas supervisé. Les modèles de mélanges non-linéaires correspondants incorporent des fonctions à valeurs vectorielles appartenant à un espace de Hilbert à noyaux reproduisants. L’intérêt de ces fonctions par rapport aux fonctions à valeurs scalaires est qu’elles permettent d’incorporer un a priori sur la ressemblance entre les différentes fonctions. En particulier, un a priori spectral, dans un premier temps, et un a priori spatial, dans un second temps, sont incorporés pour améliorer la caractérisation du mélange non-linéaire. La validation expérimentale des modèles et des algorithmes proposés sur des données synthétiques et réelles montre une amélioration des performances par rapport aux méthodes de l’état de l’art. Cette amélioration se traduit par une meilleure erreur de reconstruction des données
Spectral unmixing has been an active field of research since the earliest days of hyperspectralremote sensing. It is concerned with the case where various materials are found inthe spatial extent of a pixel, resulting in a spectrum that is a mixture of the signatures ofthose materials. Unmixing then reduces to estimating the pure spectral signatures and theircorresponding proportions in every pixel. In the hyperspectral unmixing jargon, the puresignatures are known as the endmembers and their proportions as the abundances. Thisthesis focuses on spectral unmixing of remotely sensed hyperspectral data. In particular,it is aimed at improving the accuracy of the extraction of compositional information fromhyperspectral data. This is done through the development of new unmixing techniques intwo main contexts, namely in the unsupervised and nonlinear case. In particular, we proposea new technique for blind unmixing, we incorporate spatial information in (linear and nonlinear)unmixing, and we finally propose a new nonlinear mixing model. More precisely, first,an unsupervised unmixing approach based on collaborative sparse regularization is proposedwhere the library of endmembers candidates is built from the observations themselves. Thisapproach is then extended in order to take into account the presence of noise among theendmembers candidates. Second, within the unsupervised unmixing framework, two graphbasedregularizations are used in order to incorporate prior local and nonlocal contextualinformation. Next, within a supervised nonlinear unmixing framework, a new nonlinearmixing model based on vector-valued functions in reproducing kernel Hilbert space (RKHS)is proposed. The aforementioned model allows to consider different nonlinear functions atdifferent bands, regularize the discrepancies between these functions, and account for neighboringnonlinear contributions. Finally, the vector-valued kernel framework is used in orderto promote spatial smoothness of the nonlinear part in a kernel-based nonlinear mixingmodel. Simulations on synthetic and real data show the effectiveness of all the proposedtechniques