La thèse porte sur le développement d'algorithmes d'estimation rapides pour l'analyse modale de signaux multidimensionnels (R-D) présentant des problèmes de résolution et de complexité numérique. Un signal multidimensionnel de dimension R est la superposition de produits de R sinusoïdes. L'application visée est la spectroscopie RMN.Dans un premier temps, après un état de l'art des méthodes d'estimation dites « algébriques », nous proposons une méthode paramétrique basée sur les tenseurs. Celle-ci utilise le treillis multidimensionnel du tenseur du signal R-D et exploite la structure des vecteurs propres du sous-espace signal obtenus en utilisant la décomposition en valeurs singulières d'ordre supérieur. Contrairement à la plupart des approches tensorielles, la méthode proposée permet d'éviter la phase d'appariement des coordonnées des modes dans chacune des dimensions ou d'une diagonalisation conjointe. Dans un deuxième temps, le problème d'estimation modale multidimensionnelle est présenté comme un problème d'approximation parcimonieuse dans lequel le dictionnaire est obtenu par la discrétisation de fonctions exponentielles complexes. Afin d'atteindre une bonne résolution spectrale, il est nécessaire de choisir une grille très fine, ce qui conduit à la manipulation d'un dictionnaire de grande taille avec tous les problèmes calculatoires sous-jacents. Nous proposons alors une méthode originale qui consiste à combiner une approximation parcimonieuse et une approche multigrille sur plusieurs niveaux de résolution. L'approche est validée au travers de plusieurs exemples 1-D et 2-D. En outre, une étude sur l'influence du choix du dictionnaire initial sur la convergence est également menée. Les méthodes développées sont ensuite appliquées à l'estimation des paramètres de signaux de spectroscopie RMN 1-D et 2-D. Afin de réduire le coût de calcul dans le cas de signaux bidimensionnels de grande taille, nous proposons également une approche exploitant la notion de parcimonie simultanée, pour estimer les coordonnées des modes sur chacune des dimensions. La procédure consiste à effectuer deux approximations parcimonieuses 1-D suivies d'une phase de reformation des paires de modes 2-D / This thesis aims at the developpement of modal analysis algorithms for multidimensional signals (R-D) presenting resolution and numerical complexity problems. A multidimensional signal of dimension R is the superimposition of products of R monodimensional sinusoids. The intended application is NMR spectroscopy. Firstly, after a state-of-the-art on the so-called ''algebraic'' estimation methods, we propose a parametric method based on tensors. It uses the multidimensional tensor lattice of the R-D modal signal and exploits the eigenvectors structure of the signal subspace obtained using a higher-order singular value decomposition (HOSVD). Unlike most tensor-based eigenvalue approaches, modes estimated by the proposed method are automatically paired, thus it avoids a separate pairing step and joint diagonalization. Secondly, the multidimensional modal estimation problem is formulated as a sparse approximation problem in which the dictionary is obtained by the discretization of complex exponential functions. To achieve good spectral resolution, it is necessary to choose a very fine grid, which leads to handling a large dictionary with all the underlying computational problems. Hence, we propose a novel method that consists in combining a sparse approximation and a multigrid approach on several levels of resolution. The approach is demonstrated using several 1-D and 2-D examples. In addition, the influence of the initial dictionary on the algorithm convergence is also studied. The developed methods are then applied to estimate 1-D and 2-D NMR signal parameters. To reduce the computation cost in the case of large bidimensional signals, we also propose an approach exploiting the simultaneous sparsity principle to estimate the coordinates of the modes on each dimension. The procedure involves two 1-D sparse approximations followed by a 2-D modes painring step.

Deux approches pour la décomposition parcimonieuse des signaux sont étudiées.<br /> L'une utilise des méthodes variationnelles avec une attache aux données l2 pénalisée par une norme mixte permettant de structurer la parcimonie. Les fonctionnelles sont minimisées par des algorithmes itératifs dont la convergence est prouvée. Les normes mixtes donnent des estimations par des opérateurs de seuillage généralisés, qui ont été modifiés pour les localiser ou introduire de la persistance.<br />L'autre modélise les signaux comme combinaisons linéaires parcimonieuses d'atomes temps-fréquence choisis dans l'union de deux bases orthonormées, à coefficients aléatoires. La distribution de ces coefficients fait intervenir deux niveaux d'aléa : leur valeur et leur position dans leur espace temps-fréquence. L'étude des coefficients d'analyse permet une estimation des cartes temps-fréquence. La projection du signal sur ces cartes donne une décomposition en deux couches plus un résidu.

La thèse porte sur le développement d'algorithmes d'estimation rapides pour l'analyse modale de signaux multidimensionnels (R-D) présentant des problèmes de résolution et de complexité numérique. Un signal multidimensionnel de dimension R est la superposition de produits de R sinusoïdes. L'application visée est la spectroscopie RMN. Dans un premier temps, après un état de l'art des méthodes d'estimation dites " algébriques ", nous proposons une méthode paramétrique basée sur les tenseurs. Celle-ci utilise le treillis multidimensionnel du tenseur du signal R-D et exploite la structure des vecteurs propres du sous-espace signal obtenus en utilisant la décomposition en valeurs singulières d'ordre supérieur. Contrairement à la plupart des approches tensorielles, la méthode proposée permet d'éviter la phase d'appariement des coordonnées des modes dans chacune des dimensions ou d'une diagonalisation conjointe. Dans un deuxième temps, le problème d'estimation modale multidimensionnelle est présenté comme un problème d'approximation parcimonieuse dans lequel le dictionnaire est obtenu par la discrétisation de fonctions exponentielles complexes. Afin d'atteindre une bonne résolution spectrale, il est nécessaire de choisir une grille très fine, ce qui conduit à la manipulation d'un dictionnaire de grande taille avec tous les problèmes calculatoires sous-jacents. Nous proposons alors une méthode originale qui consiste à combiner une approximation parcimonieuse et une approche multigrille sur plusieurs niveaux de résolution. L'approche est validée au travers de plusieurs exemples 1-D et 2-D. En outre, une étude sur l'influence du choix du dictionnaire initial sur la convergence est également menée. Les méthodes développées sont ensuite appliquées à l'estimation des paramètres de signaux de spectroscopie RMN 1-D et 2-D. Afin de réduire le coût de calcul dans le cas de signaux bidimensionnels de grande taille, nous proposons également une approche exploitant la notion de parcimonie simultanée, pour estimer les coordonnées des modes sur chacune des dimensions. La procédure consiste à effectuer deux approximations parcimonieuses 1-D suivies d'une phase de reformation des paires de modes 2-D.

Ce travail est motivé par la spectroscopie de photoélectrons et l'étude de la cinématique des galaxies où les données correspondent respectivement à une séquence temporelle de spectres et à une image multispectrale. L'objectif est d'estimer les caractéristiques (amplitude, position spectrale et paramètre de forme) des raies présentes dans les spectres, ainsi que leur évolution au sein des données. Dans les applications considérées, cette évolution est lente puisque deux spectres voisins sont souvent très similaires : c'est une connaissance a priori qui sera prise en compte dans les méthodes développées. Ce problème inverse est abordé sous l'angle de la séparation de sources retardées, où les spectres et les raies sont attribués respectivement aux mélanges et aux sources. Les méthodes de l'état de l'art sont inadéquates car elles supposent la décorrélation ou l'indépendance des sources, ce qui n'est pas le cas. Nous tirons parti de la connaissance des sources pour les modéliser par une fonction paramétrique. Nous proposons une première méthode de moindres carrés alternés : les paramètres de formes sont estimés avec l'algorithme de Levenberg-Marquardt, tandis que les amplitudes et les positions sont estimées avec un algorithme inspiré d'Orthogonal Matching Pursuit. Une deuxième méthode introduit un terme de régularisation pour prendre en compte l'évolution lente des positions; un nouvel algorithme d'approximation parcimonieuse conjointe est alors proposée. Enfin, une troisième méthode contraint l'évolution des amplitudes, positions et paramètres de forme par des fonctions B-splines afin de garantir une évolution lente conforme au physique des phénomènes observés. Les points de contrôle des B-splines sont estimés par un algorithme de moindre carrés non-linéaires. Les résultats sur des données synthétiques et réelles montrent que les méthodes proposées sont plus efficaces que les méthodes de l'état de l'art et aussi efficaces qu'une méthode bayésienne adaptée au problème mais avec un temps de calcul sensiblement réduit. / This work is motivated by photoelectron spectroscopy and the study of galaxy kinematics where data respectively correspond to a temporal sequence of spectra and a multispectral image. The objective is to estimate the characteristics (amplitude, spectral position and shape) of peaks embedded in the spectra, but also their evolution within the data. In the considered applications, this evolution is slow since two neighbor spectra are often very similar: this a priori knowledge that will be taken into account in the developed methods. This inverse problem is approached as a delayed source separation problem where spectra and peaks are respectively associated with mixtures and sources. The state-of-the-art methods are inadequate because they suppose the source decorrelation and independence, which is not the case. We take advantage of the source knowledge in order to model them by a parameterized function. We first propose an alternating least squares method: the shape parameters are estimated with the Levenberg-Marquardt algorithm, whilst the amplitudes and positions are estimated with an algorithm inspired from Orthogonal Matching Pursuit. A second method introduces a regularization term to consider the delay slow evolution; a new joint sparse approximation algorithm is thus proposed. Finally, a third method constrains the evolution of the amplitudes, positions and shape parameters by B-spline functions to guarantee their slow evolution. The B-spline control points are estimated with a non-linear least squares algorithm. The results on synthetic and real data show that the proposed methods are more effective than state-of-the-art methods and as effective as a Bayesian method which is adapted to the problem. Moreover, the proposed methods are significantly faster.

Cette thèse s'inscrit dans le domaine des problèmes inverses en traitement du signal. Elle est consacrée à la conception d'algorithmes de restauration et de séparation de signaux parcimonieux et à leur application à l'approximation de courbes de forces en microscopie de force atomique (AFM), où la notion de parcimonie est liée au nombre de points de discontinuité dans le signal (sauts, changements de pente, changements de courbure). Du point de vue méthodologique, des algorithmes sous-optimaux sont proposés pour le problème de l'approximation parcimonieuse basée sur la pseudo-norme ℓ0 : l'algorithme Single Best Replacement (SBR) est un algorithme itératif de type « ajout-retrait » inspiré d'algorithmes existants pour la restauration de signaux Bernoulli-Gaussiens. L'algorithme Continuation Single Best Replacement (CSBR) est un algorithme permettant de fournir des approximations à des degrés de parcimonie variables. Nous proposons aussi un algorithme de séparation de sources parcimonieuses à partir de mélanges avec retards, basé sur l'application préalable de l'algorithme CSBR sur chacun des mélanges, puis sur une procédure d'appariement des pics présents dans les différents mélanges. La microscopie de force atomique est une technologie récente permettant de mesurer des forces d'interaction entre nano-objets. L'analyse de courbes de forces repose sur des modèles paramétriques par morceaux. Nous proposons un algorithme permettant de détecter les régions d'intérêt (les morceaux) où chaque modèle s'applique puis d'estimer par moindres carrés les paramètres physiques (élasticité, force d'adhésion, topographie, etc.) dans chaque région. Nous proposons finalement une autre approche qui modélise une courbe de force comme un mélange de signaux sources parcimonieux retardées. La recherche des signaux sources dans une image force-volume s'effectue à partir d'un grand nombre de mélanges car il y autant de mélanges que de pixels dans l'image.

Ce manuscrit synthétise mon activité de recherche au CRAN entre 2005 et 2013. Les projets menés s'inscrivent dans les domaines des problèmes inverses en traitement du signal et des images, de l'approximation parcimonieuse, de l'analyse d'images hyperspectrales et de la reconstruction d'images 3D. Je détaille plus particulièrement les travaux concernant la conception, l'analyse et l'utilisation d'algorithmes d'approximation parcimonieuse pour des problèmes inverses caractérisés par un dictionnaire mal conditionné. Dans un premier chapitre, je présente les algorithmes heuristiques conçus pour minimiser des critères mixtes L2-L0. Ce sont des algorithmes gloutons << bidirectionnels >> définis en tant qu'extension de l'algorithme Orthogonal Least Squares (OLS). Leur développement est motivé par le bon comportement empirique d'OLS et de ses versions dérivées lorsque le dictionnaire est une matrice mal conditionnée. Le deuxième chapitre est une partie applicative en microscopie de force atomique, où les algorithmes du premier chapitre sont utilisés avec un dictionnaire particulier dans le but de segmenter automatiquement des signaux. Cette segmentation permet finalement de fournir une cartographie 2D de différents paramètres électrostatiques et bio-mécaniques. Le troisième chapitre est une partie théorique visant à analyser les algorithmes gloutons OMP (Orthogonal Matching Pursuit) et OLS. Une première analyse de reconstruction exacte par OLS en k itérations est proposée. De plus, une comparaison poussée des conditions de reconstruction exacte lorsqu'un certain nombre d'itérations ont déjà été effectuées fournit un éclairage sur le meilleur comportement d'OLS (par rapport à OMP) pour les problèmes mal conditionnés. Dans un quatrième chapitre, je dresse quelques perspectives méthodologiques et appliquées dans le domaine de l'analyse parcimonieuse en lien avec les chapitres précédents.

Cette thèse s'inscrit dans le domaine des problèmes inverses en traitement du signal. Elle est consacrée à la conception d'algorithmes de restauration et de séparation de signaux parcimonieux et à leur application à l'approximation de courbes de forces en microscopie de force atomique (AFM), où la notion de parcimonie est liée au nombre de points de discontinuité dans le signal (sauts, changements de pente, changements de courbure). Du point de vue méthodologique, des algorithmes sous-optimaux sont proposés pour le problème de l'approximation parcimonieuse basée sur la pseudo-norme l0 : l'algorithme Single Best Replacement (SBR) est un algorithme itératif de type « ajout-retrait » inspiré d'algorithmes existants pour la restauration de signaux Bernoulli-Gaussiens. L'algorithme Continuation Single Best Replacement (CSBR) est un algorithme permettant de fournir des approximations à des degrés de parcimonie variables. Nous proposons aussi un algorithme de séparation de sources parcimonieuses à partir de mélanges avec retards, basé sur l'application préalable de l'algorithme CSBR sur chacun des mélanges, puis sur une procédure d'appariement des pics présents dans les différents mélanges. La microscopie de force atomique est une technologie récente permettant de mesurer des forces d'interaction entre nano-objets. L'analyse de courbes de forces repose sur des modèles paramétriques par morceaux. Nous proposons un algorithme permettant de détecter les régions d'intérêt (les morceaux) où chaque modèle s'applique puis d'estimer par moindres carrés les paramètres physiques (élasticité, force d'adhésion, topographie, etc.) dans chaque région. Nous proposons finalement une autre approche qui modélise une courbe de force comme un mélange de signaux sources parcimonieux retardées. La recherche des signaux sources dans une image force-volume s'effectue à partir d'un grand nombre de mélanges car il y autant de mélanges que de pixels dans l'image / This thesis handles several inverse problems occurring in sparse signal processing. The main contributions include the conception of algorithms dedicated to the restoration and the separation of sparse signals, and their application to force curve approximation in Atomic Force Microscopy (AFM), where the notion of sparsity is related to the number of discontinuity points in the signal (jumps, change of slope, change of curvature).In the signal processing viewpoint, we propose sub-optimal algorithms dedicated to the sparse signal approximation problem based on the l0 pseudo-norm : the Single Best Replacement algorithm (SBR) is an iterative "forward-backward" algorithm inspired from existing Bernoulli-Gaussian signal restoration algorithms. The Continuation Single Best Replacement algorithm (CSBR) is an extension providing approximations at various sparsity levels. We also address the problem of sparse source separation from delayed mixtures. The proposed algorithm is based on the prior application of CSBR on every mixture followed by a matching procedure which attributes a label for each peak occurring in each mixture.Atomic Force Microscopy (AFM) is a recent technology enabling to measure interaction forces between nano-objects. The force-curve analysis relies on piecewise parametric models. We address the detection of the regions of interest (the pieces) where each model holds and the subsequent estimation of physical parameters (elasticity, adhesion forces, topography, etc.) in each region by least-squares optimization. We finally propose an alternative approach in which a force curve is modeled as a mixture of delayed sparse sources. The research of the source signals and the delays from a force-volume image is done based on a large number of mixtures since there are as many mixtures as the number of image pixels