Nous abordons dans cette thèse les approches de la Programmation DC et DCAen Data Mining (fouille de données). Plus particulièrement, nous nous intéressons aux problèmes de parcimonie en modélisation parcimonieuse de données. Le travail porte sur des recherches théoriques et algorithmiques et la principale approche utilisée est la programmation DC et DCA.Nous avons établi des propriétés intéressantes, des reformulations DC, voire quadratiques,équivalentes pour ces problèmes grâce à de nouvelles techniques de pénalité exacte développées durant cette thèse. Ces résultats donnent une nouvelle facette et une nouvelle manière de voir ces problèmes de parcimonie afin de permettre une meilleure compréhension et prise en main de ces problèmes. Ces nouvelles techniques ont été appliquées dans le cadre de la modélisation parcimonieuse pour le problème de la valeur propre maximale et dans le cadre de la modélisation parcimonieuse dans les modèles de régression linéaire.La structure simple des reformulations obtenues se prête bien à la programmation DC et DCA pour la résolution. Les simulations numériques, obtenues avec DCA et un algorithme combiné DCA et la procédure Séparation et Evaluation pour l’optimisation globale, sont très intéressantes et très prometteuses et illustrent bien le potentiel de cette nouvelle approche. / In this thesis, we investigate the DC Programming and DCA approaches in DataMining. More precisely, we are interested in the sparse approximation problems in sparse modelling. The work focuses on theoretical and algorithmic studies, mainly based on DC Programming and DCA. We established interesting properties concerning DC and quadratic reformulations for these problems with the help of new exact penalty techniques in DC programming. These results give new insights on these sparse approximation problems and so allow a better understanding and a better handling of these problems. These novel techniques were applied in both contexts of sparse eigenvalue problem and sparse approximation in linear models.The simple and nice structure of the obtained reformulations are suitably adapted to DC programming and DCA. Computational experiments are very interesting and promising, illustrating the potential of the novel approach.

Cette thèse porte sur la localisation de sources spatialement distribuées. Premièrement, des résultats théoriques ont été établis concernant les performances des méthodes à haute résolution en présence d'erreurs de modèle dues à la distribution angulaire de source. Ainsi, le biais d'estimation et l'erreur quadratique moyenne sont exprimées en fonction des paramètres liés à l'erreur de modèle. De plus, les performances ont été étudiées en fonction de la géométrie de l'antenne afin de déterminer les configurations les plus robustes aux sources dispersées.Les résultats théoriques ont été validés par des simulations numériques. Dans un deuxième temps, une nouvelle approche non paramétrique a été proposée pour la localisation de sources distribuées : cette approche exploite les propriétés de parcimonie et de rang-faible de la matrice de covariance spatiale des sources. Cette méthode permet en outre d'estimer la forme de la distribution spatiale des sources. Les résultats de simulations ont permis de mettre en avant l'intérêt de l'hypothèse rang faible par rapport aux critères exploitant uniquement la parcimonie / This thesis focuses on the distributed source localization problem. In a first step, performance of high resolution methods in the presence of model errors due to the angular distribution of source has been studied. Theoretical expressions of the estimation bias and the mean square error of the direction of arrival of sources have been established in terms of model error. The impacts of the array geometry on the performances have studied in order to optimize the robustness of the array to the model error due to distributed sources.Theoretical results have been validated by numerical simulations.In a second step, a new approach for the localization of spatially distributed source has been proposed: the approach is based on the sparsity and low-rank property of the spatial covariance matrix of the sources. The proposed method provides also an estimation of the distribution shapes of the sources. Simulation results exhibit the advantages of exploiting the sparsity and the low rank properties.

Les décompositions parcimonieuses décrivent un signal comme une combinaison d'un petit nombre de formes de base, appelées atomes. Le dictionnaire d'atomes, crucial pour l'efficacité de la décomposition, peut résulter d'un choix a priori (ondelettes, Gabor, ...) qui fixe la structure du dictionnaire, ou d'un apprentissage à partir d'exemples représentatifs du signal. Nous proposons ici un cadre hybride combinant des contraites structurelles et une approche par apprentissage. Les dictionnaires ainsi structurés apportent une meilleure adaptation aux propriétés du signal et permettent de traiter des volumes importants de données. Nous exposons les concepts et les outils qui étayent cette approche, notamment l'adaptation des algorithmes Matching Pursuit et K-SVD à des dictionnaires d'atomes constitués de motifs linéairement déformables, via une propriété d'adjonction. Nous présentons également des résultats de séparation de signaux monocanaux dans le cadre proposé.

Cette thèse a pour but d‘estimer la position et la puissance de sources sonores ponctuelles à l'aide d‘une antenne acoustique. Nous nous intéressons d‘abord à la directivité des antennes acoustiques pondérées. On montre qu‘une telle antenne, appelée antenne conventionnelle, même si elle est à directivité optimale, est inutilisable pour localiser plusieurs sources sonores. Des traitements adaptatifs d‘antenne sont donc exigés et les méthodes dites à haute résolution sont introduites. Elles sont basées sur l‘estimation de la matrice de covariance des signaux issus des capteurs et présentent l‘avantage de s‘affranchir des limitations naturelles du traitement d‘antenne conventionnel. Cependant, ces méthodes nécessitent l‘emploi d‘un modèle de propagation et sont donc par nature peu robustes aux erreurs de modèle, ce qui peut être parfois un handicap et dégrader leurs performances. Par la suite, nous présentons une nouvelle méthode de séparation des sources utilisant une représentation parcimonieuse des signaux. Nous montrons que ses performances sont meilleures que celles obtenues par les méthodes à haute résolution et notre algorithme parvient à une bonne résolution spatiale, même sous des conditions défavorables. Cette méthode est appliquée aux sources corrélées et décorrélées, à bande étroite et à large bande, en champ proche et en champ lointain. Pour finir, nous présentons des méthodes pour estimer la puissance des sources sonores. Des simulations numériques et des expérimentations en chambre anéchoïque sont effectuées afin de vérifier et de valider les analyses et les résultats théoriques / This thesis concerns the problem of sensor array source localization and power estimation by an acoustical array of sensors. In first the acoustical array directivity is treated. It is shown that such array is not useful for the localization of multiple sources. Adaptive arrays and high resolution methods are then introduced. They are based on the estimation of the sensor output covariance matrix and their performances overcome the natural limitations of the weighted beamforming processing. However, these methods require the use of a propagation model and are not robust to model errors. We present a new method which is an application of sparse regularization methodology to acoustical source localization using an acoustical array. Its performances are better than high-resolution methods and this method works very well in the case of correlated or uncorrelated signals, narrow band or wideband signals, near field or far field environments. Finally, a power estimation of sound sources by an acoustical array is presented. Numerical and experimental results in an anechoic room are presented showing the effectiveness of theoretical results

La SER (Surface Équivalente Radar) est une grandeur caractérisant le pouvoir rétrodiffuseurd’une cible soumise à un champ électromagnétique. Dans de nombreuses applications,il est capital d’analyser et de contrôler la SER. L’imagerie 3D est l’outil adapté pourlocaliser et caractériser en trois dimensions les principaux contributeurs à la SER. Cependant,ce traitement est un problème de synthèse de Fourier qui n’est pas inversible car il y aplus d’inconnues que de données. Les méthodes conventionnelles telles que le Polar FormatAlgorithm, consistant en un reformatage des données avec complétion de zéro suivi d’unetransformée de Fourier inverse rapide, fournissent des résultats de qualité limitée.Dans ce travail, nous proposons une nouvelle méthode haute résolution. Elle est dénomméeSPRITE (pour SParse Radar Imaging TEchnique) et permet d’accroître considérablementla qualité des cartes de rétro-diffusion estimées. Elle repose sur une régularisation duproblème consistant en la prise en compte d’informations a priori de parcimonie et d’uneinformation de support. La solution est alors définie comme le minimiseur d’un critère pénaliséet contraint. L’optimisation est assurée par l’algorithme primal-dual ADMM (AlternatingDirection Method of Multiplier) dont une adaptation aux spécificités du problème mène à descalculs efficaces à l’aide de transformées de Fourier rapides.Finalement, la méthode est évaluée sur des données synthétiques et réelles. Comparativementà la méthode conventionnelle, la résolution est drastiquement accrue. Les images 3Dproduites sont alors un outil particulièrement adapté à l’analyse et au contrôle de SER. / The RCS (Radar Cross Section) is a quantity which characterizes the scattering power ofa target exposed to an electromagnetic field. Its analysis and control are important in manyapplications. 3D imaging is a suitable tool to accurately locate and characterize in 3D themain contributors to the RCS. However, this is a non-invertible Fourier synthesis problembecause the number of unknowns is larger than the number of data. Conventional methodssuch as the Polar Format Algorithm, which consists of data reformatting including zeropaddingfollowed by a fast inverse Fourier transform, provide results of limited quality.In this work, we propose a new high resolution method, named SPRITE (for SParse RadarImaging TEchnique), which considerably increases the quality of the estimated RCS maps. Itis based on a regularization scheme that accounts for information of sparsity and support. Thesolution is then defined as the minimizer of a penalized and constrained criterion. Optimizationis ensured by an appropriate adaptation of the ADMM (Alternating Direction Methodof Multiplier) algorithm that is able to quickly perform calculations using fast Fourier transforms.Finally, the method is evaluated on both simulated and real data. Compared to the conventionalmethod, the resolution is significantly increased and the images can support a betterRCS analysis and control.

Les réseaux de capteurs corporels représentent un enjeu sociétal important en permettant des soins de meilleure qualité avec un coût réduit. Ces derniers sont utilisés pour détecter des anomalies dès leur apparition et ainsi intervenir au plus vite. Les capteurs sont soumis à de nombreuses contraintes de fiabilité, robustesse, taille et consommation. Dans cette thèse, les différentes opérations réalisées par les réseaux de capteurs corporels sont analysées. La consommation de chacune d'elles est évaluée afin de guider les axes de recherche pour améliorer l'autonomie énergétique des capteurs. Un capteur pour la détection d'arythmie sur des signaux cardiaques est proposé. Il intègre un traitement du signal via l'utilisation d'un réseau de neurone à cliques. Le système proposé est simulé et offre une exactitude de classification de 95 % pour la détection de trois types d'arythmie. Le prototypage du système via la fabrication d'un circuit mixte analogique/numérique en CMOS 65 nm montre une consommation du capteur de l'ordre de 1,4 μJ. Pour réduire encore plus l'énergie, une nouvelle méthode d'acquisition est utilisée. Une architecture de convertisseur est proposée pour l'acquisition et le traitement de signaux cardiaques. Cette dernière laisse espérer une consommation de l'ordre de 1,18 nJ pour acquérir les paramètres tout en offrant une exactitude de classification proche de 98 %. Cette étude permet d'ouvrir la voie vers la mise en place de capteurs très basse consommation pouvant durer toute une vie avec une simple pile. / Body area sensor networks gained great focused through the promiseof better quality and cheaper medical care system. They are used todetect anomalies and treat them as soon as they arise. Sensors are under heavy constraints such as reliability, sturdiness, size and power consumption. This thesis analyzes the operations perform by a body area sensor network. The different energy requirements are evaluated in order to choose the focus of the research to improve the battery life of the sensors. A sensor for arrhythmia detection is proposed. It includes some signal processing through a clique-based neural network. The system simulations allow a classification between three types of arrhythmia with 95 % accuracy. The prototype, based on a 65 nm CMOS mixed signal circuit, requires only 1.4 μJ. To further reduce energy consumption, a new sensing method is used. A converter architecture is proposed for heart beat acquisition. Simulations and estimation show a 1.18 nJ energy requirement for parameter acquisition while offering 98 % classification accuracy. This work leads the way to the development of low energy sensor with a lifetime battery life.

Cette thèse traite du développement d'algorithmes d'estimation en haute dimension. Ces algorithmes visent à résoudre des problèmes de discrimination et de classification, notamment, en incorporant un mécanisme de sélection des variables pertinentes. Les contributions de cette thèse se concrétisent par deux algorithmes, GLOSS pour la discrimination et Mix-GLOSS pour la classification. Tous les deux sont basés sur le résolution d'une régression régularisée de type "optimal scoring" avec une formulation quadratique de la pénalité group-Lasso qui encourage l'élimination des descripteurs non-significatifs. Les fondements théoriques montrant que la régression de type "optimal scoring" pénalisée avec un terme "group-Lasso" permet de résoudre un problème d'analyse discriminante linéaire ont été développés ici pour la première fois. L'adaptation de cette théorie pour la classification avec l'algorithme EM n'est pas nouvelle, mais elle n'a jamais été détaillée précisément pour les pénalités qui induisent la parcimonie. Cette thèse démontre solidement que l'utilisation d'une régression de type "optimal scoring" pénalisée avec un terme "group-Lasso" à l'intérieur d'une boucle EM est possible. Nos algorithmes ont été testés avec des bases de données réelles et artificielles en haute dimension avec des résultats probants en terme de parcimonie, et ce, sans compromettre la performance du classifieur. / This thesis deals with the development of estimation algorithms with embedded feature selection the context of high dimensional data, in the supervised and unsupervised frameworks. The contributions of this work are materialized by two algorithms, GLOSS for the supervised domain and Mix-GLOSS for unsupervised counterpart. Both algorithms are based on the resolution of optimal scoring regression regularized with a quadratic formulation of the group-Lasso penalty which encourages the removal of uninformative features. The theoretical foundations that prove that a group-Lasso penalized optimal scoring regression can be used to solve a linear discriminant analysis bave been firstly developed in this work. The theory that adapts this technique to the unsupervised domain by means of the EM algorithm is not new, but it has never been clearly exposed for a sparsity-inducing penalty. This thesis solidly demonstrates that the utilization of group-Lasso penalized optimal scoring regression inside an EM algorithm is possible. Our algorithms have been tested with real and artificial high dimensional databases with impressive resuits from the point of view of the parsimony without compromising prediction performances.

Cette thèse s'inscrit dans le contexte de la vidéo surveillance et s'intéresse à la ré-identification de personnes dans un réseau de caméras à champs disjoints. La ré-identification consiste à déterminer si une personne quitte le champ d'une caméra et réapparait dans une autre. Elle est particulièrement difficile car l'apparence de la personne change de manière significative à cause de différents facteurs. Nous proposons d'exploiter la complémentarité de l'apparence de la personne et son style de mouvement pour la décrire d'une manière appropriée aux facteurs de complexité. C'est une nouvelle approche car la ré-identification a été traitée par des approches d'apparence. Les contributions majeures proposées concernent: la description de la personne et l'appariement des primitives. Nous étudions deux scénarios de ré-identification : simple et complexe. Dans le scénario simple, nous étudions la faisabilité de deux approches : approche biométrique basée sur la démarche et approche d'apparence fondée sur des points d'intérêt (PI) spatiaux et des primitives de couleur. Dans le scénario complexe, nous proposons de fusionner des primitives d'apparence et de mouvement. Nous décrivons le mouvement par des Pis spatio-temporels et l'apparence par des PIs spatiaux. Pour l'appariement, nous utilisons la représentation parcimonieuse comme méthode d'appariement local entre les PIs. Le schéma de fusion est fondé sur le calcul de la somme pondérée des votes des PIs et ensuite l'application de la règle de vote majoritaire. Nous proposons également une analyse d'erreurs permettant d'identifier les sources d'erreurs de notre système pour dégager les pistes d'amélioration les plus prometteuses / This thesis focuses on the problem of hu man re-identification through a network of cameras with non overlapping fields of view. Human re-identification is defined as the task of determining if a persan leaving the field of one camera reappears in another. It is particularly difficult because of persons' significant appearance change within different cameras vision fields due to various factors. In this work, we propose to exploit the complementarity of the person's appearance and style of movement that leads to a description that is more robust with respect to various complexity factors. This is a new approach for the re-identification problem that is usually treated by appearance methods only. The major contributions proposed in this work include: person's description and features matching. First we study the re-identification problem and classify it into two scenarios: simple and complex. In the simple scenario, we study the feasibility of two approaches: a biometric approach based on gait and an appearance approach based on spatial Interest Points (IPs) and color features. In the complex scenario, we propose to exploit a fusion strategy of two complementary features provided by appearance and motion descriptions. We describe motion using spatiotemporal IPs, and use the spatial IPs for describing the appearance. For feature matching, we use sparse representation as a local matching method between IPs. The fusion strategy is based on the weighted sum of matched IPs votes and then applying the rule of majority vote. Moreover, we have carried out an error analysis to identify the sources of errors in our proposed system to identify the most promising areas for improvement

Cette thèse est consacrée à l'étude des signaux mesurés par Electroencéphalographie (EEG) et Magnétoencéphalographie (MEG) afin d'améliorer notre compréhension du cerveau humain. La MEG et l'EEG sont des modalités d'imagerie cérébrale non invasives. Elles permettent de mesurer, hors de la tête, respectivement le potentiel électrique et le champ magnétique induits par l'activité neuronale. Le principal objectif lié à l'exploitation de ces données est la localisation dans l'espace et dans le temps des sources de courant ayant généré les mesures. Pour ce faire, il est nécessaire de résoudre un certain nombre de problèmes mathématiques et informatiques difficiles. La première partie de cette thèse part de la présentation des fondements biologiques à l'origine des données M/EEG, jusqu'à la résolution du problème direct. Le problème direct permet de prédire les mesures générées pour une configuration de sources de courant donnée. La résolution de ce problème à l'aide des équations de Maxwell dans l'approximation quasi-statique passe par la modélisation des générateurs de courants, ainsi que de la géométrie du milieu conducteur, dans notre cas la tête. Cette modélisation aboutit à un problème direct linéaire qui n'admet pas de solution analytique lorsque l'on considère des modèles de tête réalistes. Notre première contribution porte sur l'implémentation d'une résolution numérique à base d'éléments finis surfaciques dont nous montrons l'excellente précision comparativement aux autres implémentations disponibles. Une fois le problème direct calculé, l'étape suivante consiste à estimer les positions et les amplitudes des sources ayant généré les mesures. Il s'agit de résoudre le problème inverse. Pour ce faire, trois méthodes existent: les méthodes paramétriques, les méthodes dites de "scanning", et les méthodes distribuées. Cette dernière approche fournit un cadre rigoureux à la résolution de problème inverse tout en évitant de faire de trop importantes approximations dans la modélisation. Toutefois, elle impose de résoudre un problème fortement sous-contraint qui nécessite de fait d'imposer des a priori sur les solutions. Ainsi la deuxième partie de cette thèse est consacrée aux différents types d'a priori pouvant être utilisés dans le problème inverse. Leur présentation part des méthodes de résolution mathématiques jusqu'aux détails d'implémentation et à leur utilisation en pratique sur des tailles de problèmes réalistes. Un intérêt particulier est porté aux a priori induisant de la parcimonie et conduisant à l'optimisation de problèmes convexes non différentiables pour lesquels sont présentées des méthodes d'optimisation efficaces à base d'itérations proximales. La troisième partie porte sur l'utilisation des méthodes exposées précédemment afin d'estimer des cartes rétinotopiques dans le système visuel à l'aide de données MEG. La présentation porte à la fois sur les aspects expérimentaux liés au protocole d'acquisition jusqu'à la mise en oeuvre du problème inverse en exploitant des propriétés sur le spectre du signal mesuré. La contribution suivante ambitionne d'aller plus loin que la simple localisation d'activités par le problème inverse afin de donner accès à la dynamique de l'activité corticale. Partant des estimations de sources sur le maillage cortical, la méthode proposée utilise des méthodes d'optimisation combinatoires à base de coupes de graphes afin d'effectuer de façon robuste le suivi de l'activité au cours du temps. La dernière contribution de cette thèse porte sur l'estimation de paramètres sur des données M/EEG brutes non moyennées. Compte tenu du faible rapport signal à bruit, l'analyse de données M/EEG dites "simple essai" est un problème particulièrement difficile dont l'intérêt est fondamental afin d'aller plus loin que l'analyse de données moyennées en explorant la variabilité inter-essais. La méthode proposée utilise des outils récents à base de graphes. Elle garantit des optimisations globales et s'affranchit de problèmes classiques tels que l'initialisation des paramètres ou l'utilisation du signal moyenné dans l'estimation. L'ensemble des méthodes développées durant cette thèse ont été utilisées sur des données M/EEG réels afin de garantir leur pertinence dans le contexte expérimental parfois complexe des signaux réelles M/EEG. Les implémentations et les données nécessaires à la reproductibilité des résultats sont disponibles. Le projet de rétinotopie par l'exploitation de données de MEG a été mené en collaboration avec l'équipe du LENA au sein de l'hôpital de La Pitié-Salpêtrière (Paris).

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.