Cette thèse traite de l'étude de méthodes de diagonalisation conjointe de matrices complexes, en vue de la séparation de sources, que ce soit dans le domaine des télécommunications numériques ou de la radioastronomie. Après avoir présenté les motivations qui ont poussé cette étude, nous faisons un bref état de l'art dans le domaine. Le problème de la diagonalisation conjointe, ainsi que celui de la séparation de source sont rappelés, et un lien entre ces deux sujets est établi. Par la suite, plusieurs algorithmes itératifs sont développés. Dans un premier temps, des méthodes utilisant une mise à jour de la matrice de séparation, de type gradient, sont présentées. Elles sont basées sur des approximations judicieuses du critère considéré. Afin d'améliorer la vitesse de convergence, une méthode utilisant un calcul du pas optimal est présentée, et plusieurs variantes de ce calcul, basées sur les approximations faites précédemment, sont développées. Deux autres approches sont ensuite introduites. La première détermine la matrice de séparation de manière analytique, en calculant algébriquement les termes composant la matrice de mise à jour par paire à partir d'un système d'équations linéaire. La deuxième estime récursivement la matrice de mélange, en se basant sur une méthode de moindres carrés alternés. Afin d'améliorer la vitesse de convergence, une recherche de pas d'adaptation linéaire est proposée. Ces méthodes sont alors validées sur un problème de diagonalisation conjointe classique. Puis les algorithmes sont appliqués à la séparation de sources de signaux de télécommunication numérique, en utilisant des statistiques d'ordre deux ou supérieur. Des comparaisons sont également effectuées avec des méthodes standards. La deuxième application concerne l'élimination des interférences terrestres à partir de l'estimation de l'espace associé, afin d'observer au mieux des sources cosmiques, issues de données de station LOFAR. / This thesis deals with the study of joint diagonalization of complex matrices methods for source separation, wether in the field of numerical telecommunications and radioastronomy. After having introduced the motivations that drove this study, we present a brief state-of-the-art in the field. The joint diagonalization and source separation problems are reminded, and a link between these two themes is established. Thereafter, several iterative algorithms are developed. First, methods using a gradient-like update of the separation matrix are introduced. They are based on wise approximations of the considered criterion. In order to improve the convergence speed, a method using a computation of an optimal step size is presented, and variations around this computation, based on the previously introduced approximations are done. Two other approaches are then introduced. The first one analytically determines the separation matrix, by algebraically computing the terms composing the update matrix pairwise from a linear equation system. The second one recursively estimates the mixing matrix, based on an alternating least squares method. In order to enhance the convergence speed, a seek of an enhanced line search algorithm is proposed. These methods are then validated on a classical joint diagonalization problem. Aterwards, these algorithms are applied to the source separation of numerical communication signals, while using second or higher order statistics. Comparisons are also made with well-known methods. The second application relates to elimination of rterrestrial interferences from the estimation of the associated space in order to observe at best cosmic sources from LOFAR station data.

In computer graphics, the complex phenomenon of color appearance, involving the interaction of light, matter and the human visual system, is modeled by the multiplication of RGB triplets assigned to lights and materials. This efficient heuristic produces plausible images because the triplets assigned to materials usually function as color specifications. To predict color, spectral rendering is required, but the O(n) cost of computing reflections with n-dimensional point-sampled spectra is prohibitive for real-time rendering. Typical spectra are well approximated by m-dimensional linear models, where m << n, but computing reflections with this representation requires O(m^2) matrix-vector multiplication. A method by Drew and Finlayson [JOSA A 20, 7 (2003), 1181-1193], reduces this cost to O(m) by “sharpening” an n x m orthonormal basis with a linear transformation, so that the new basis vectors are approximately disjoint. If successful, this transformation allows approximated reflections to be computed as the products of coefficients of lights and materials. Finding the m x m change of basis matrix requires solving m eigenvector problems, each needing a choice of wavelengths in which to sharpen the corresponding basis vector. These choices, however, are themselves an optimization problem left unaddressed by the method's authors. Instead, we pose a single problem, expressing the total approximation error incurred across all wavelengths as the sum of dm^2 squares for some number d, where, depending on the inherent dimensionality of the rendered reflectance spectra, m <= d << n, a number that is independent of the number of approximated reflections. This problem may be solved in real time, or nearly, using standard nonlinear optimization algorithms. Results using a variety of reflectance spectra and three standard illuminants yield errors at or close to the best lower bound attained by projection onto the leading m characteristic vectors of the approximated reflections. Measured as CIEDE2000 color differences, a heuristic proxy for image difference, these errors can be made small enough to be likely imperceptible using values of 4 <= m <= 9. An examination of this problem reveals a hierarchy of simpler, more quickly solved subproblems whose solutions yield, in the typical case, increasingly inaccurate approximations. Analysis of this hierarchy explains why, in general, the lowest approximation error is not attained by simple spectral sharpening, the smallest of these subproblems, unless the spectral power distributions of all light sources in a scene are sufficiently close to constant functions. Using the methods described in this dissertation, spectra can be rendered in real time as the products of m-dimensional vectors of sharp basis coefficients at a cost that is, in a typical application, a negligible fraction above the cost of RGB rendering. / Graduate

Cette thèse présente de nouveaux algorithmes de diagonalisation conjointe par similitude. Cesalgorithmes permettent, entre autres, de résoudre le problème de décomposition canonique polyadiquede tenseurs. Cette décomposition est particulièrement utilisée dans les problèmes deséparation de sources. L’utilisation de la diagonalisation conjointe par similitude permet de paliercertains problèmes dont les autres types de méthode de décomposition canonique polyadiquesouffrent, tels que le taux de convergence, la sensibilité à la surestimation du nombre de facteurset la sensibilité aux facteurs corrélés. Les algorithmes de diagonalisation conjointe par similitudetraitant des données complexes donnent soit de bons résultats lorsque le niveau de bruit est faible,soit sont plus robustes au bruit mais ont un coût calcul élevé. Nous proposons donc en premierlieu des algorithmes de diagonalisation conjointe par similitude traitant les données réelles etcomplexes de la même manière. Par ailleurs, dans plusieurs applications, les matrices facteursde la décomposition canonique polyadique contiennent des éléments exclusivement non-négatifs.Prendre en compte cette contrainte de non-négativité permet de rendre les algorithmes de décompositioncanonique polyadique plus robustes à la surestimation du nombre de facteurs ou lorsqueces derniers ont un haut degré de corrélation. Nous proposons donc aussi des algorithmes dediagonalisation conjointe par similitude exploitant cette contrainte. Les simulations numériquesproposées montrent que le premier type d’algorithmes développés améliore l’estimation des paramètresinconnus et diminue le coût de calcul. Les simulations numériques montrent aussi queles algorithmes avec contrainte de non-négativité améliorent l’estimation des matrices facteurslorsque leurs colonnes ont un haut degré de corrélation. Enfin, nos résultats sont validés à traversdeux applications de séparation de sources en télécommunications numériques et en spectroscopiede fluorescence. / This thesis introduces new joint eigenvalue decomposition algorithms. These algorithms allowamongst others to solve the canonical polyadic decomposition problem. This decomposition iswidely used for blind source separation. Using the joint eigenvalue decomposition to solve thecanonical polyadic decomposition problem allows to avoid some problems whose the others canonicalpolyadic decomposition algorithms generally suffer, such as the convergence rate, theoverfactoring sensibility and the correlated factors sensibility. The joint eigenvalue decompositionalgorithms dealing with complex data give either good results when the noise power is low, orthey are robust to the noise power but have a high numerical cost. Therefore, we first proposealgorithms equally dealing with real and complex. Moreover, in some applications, factor matricesof the canonical polyadic decomposition contain only nonnegative values. Taking this constraintinto account makes the algorithms more robust to the overfactoring and to the correlated factors.Therefore, we also offer joint eigenvalue decomposition algorithms taking advantage of thisnonnegativity constraint. Suggested numerical simulations show that the first developed algorithmsimprove the estimation accuracy and reduce the numerical cost in the case of complexdata. Our numerical simulations also highlight the fact that our nonnegative joint eigenvaluedecomposition algorithms improve the factor matrices estimation when their columns have ahigh correlation degree. Eventually, we successfully applied our algorithms to two blind sourceseparation problems : one concerning numerical telecommunications and the other concerningfluorescence spectroscopy.

La diagonalisation conjointe approximée d’un ensemble de matrices permet de résoudre le problème de séparation aveugle de sources et trouve de nombreuses applications, notamment pour l’électroencéphalographie, une technique de mesure de l’activité cérébrale.La diagonalisation conjointe se formule comme un problème d’optimisation avec trois composantes : le choix du critère à minimiser, la contrainte de non-dégénérescence de la solution et l’algorithme de résolution.Les approches existantes considèrent principalement deux critères, les moindres carrés et la log-vraissemblance.Elles sont spécifiques à une contrainte et se restreignent à un seul type d’algorithme de résolution.Dans ce travail de thèse, nous proposons de formuler le problème de diagonalisation conjointe selon un modèle géométrique, qui généralise les travaux précédents et permet de définir des critères inédits, notamment liés à la théorie de l’information.Nous proposons également d’exploiter l’optimisation riemannienne et nousdéfinissons un ensemble d’outils qui permet de faire varier les trois composantes indépendamment, créant ainsi de nouvelles méthodes et révélant l’influence des choix de modélisation.Des expériences numériques sur des données simulées et sur des enregistrements électroencéphalographiques montrent que notre approche par optimisation riemannienne donne des résultats compétitifs par rapport aux méthodes existantes.Elles indiquent aussi que les deux critères traditionnels ne sont pas les meilleurs dans toutes les situations. / The approximate joint diagonalisation of a set of matrices allows the solution of the blind source separation problem and finds several applications, for instance in electroencephalography, a technique for measuring brain activity.The approximate joint diagonalisation is formulated as an optimization problem with three components: the choice of the criterion to be minimized, the non-degeneracy constraint on the solution and the solving algorithm.Existing approaches mainly consider two criteria, the least-squares and the log-likelihood.They are specific to a constraint and are limited to only one type of solving algorithms.In this thesis, we propose to formulate the approximate joint diagonalisation problem in a geometrical fashion, which generalizes previous works and allows the definition of new criteria, particularly those linked to information theory.We also propose to exploit Riemannian optimisation and we define tools that allow to have the three components varying independently, creating in this way new methods and revealing the influence of the choice of the model.Numerical experiments on simulated data as well as on electroencephalographic recordings show that our approach by means of Riemannian optimisation gives results that are competitive as compared to existing methods.They also indicate that the two traditional criteria do not perform best in all situations.

Cette thèse développe des méthodes de diagonalisation conjointe de matrices et de tenseurs d’ordre trois, et son application à la séparation MIMO de sources de télécommunications numériques. Après un état, les motivations et objectifs de la thèse sont présentés. Les problèmes de la diagonalisation conjointe et de la séparation de sources sont définis et un lien entre ces deux domaines est établi. Par la suite, plusieurs algorithmes itératifs de type Jacobi reposant sur une paramétrisation LU sont développés. Pour chacun des algorithmes, on propose de déterminer les matrices permettant de diagonaliser l’ensemble considéré par l’optimisation d’un critère inverse. On envisage la minimisation du critère selon deux approches : la première, de manière directe, et la seconde, en supposant que les éléments de l’ensemble considéré sont quasiment diagonaux. En ce qui concerne l’estimation des différents paramètres du problème, deux stratégies sont mises en œuvre : l’une consistant à estimer tous les paramètres indépendamment et l’autre reposant sur l’estimation indépendante de couples de paramètres spécifiquement choisis. Ainsi, nous proposons trois algorithmes pour la diagonalisation conjointe de matrices complexes symétriques ou hermitiennes et deux algorithmes pour la diagonalisation conjointe d’ensembles de tenseurs symétriques ou non-symétriques ou admettant une décomposition INDSCAL. Nous montrons aussi le lien existant entre la diagonalisation conjointe de tenseurs d’ordre trois et la décomposition canonique polyadique d’un tenseur d’ordre quatre, puis nous comparons les algorithmes développés à différentes méthodes de la littérature. Le bon comportement des algorithmes proposés est illustré au moyen de simulations numériques. Puis, ils sont validés dans le cadre de la séparation de sources de télécommunications numériques. / This thesis develops joint diagonalization of matrices and third-order tensors methods for MIMO source separation in the field of digital telecommunications. After a state of the art, the motivations and the objectives are presented. Then the joint diagonalisation and the blind source separation issues are defined and a link between both fields is established. Thereafter, five Jacobi-like iterative algorithms based on an LU parameterization are developed. For each of them, we propose to derive the diagonalization matrix by optimizing an inverse criterion. Two ways are investigated : minimizing the criterion in a direct way or assuming that the elements from the considered set are almost diagonal. Regarding the parameters derivation, two strategies are implemented : one consists in estimating each parameter independently, the other consists in the independent derivation of couple of well-chosen parameters. Hence, we propose three algorithms for the joint diagonalization of symmetric complex matrices or hermitian ones. The first one relies on searching for the roots of the criterion derivative, the second one relies on a minor eigenvector research and the last one relies on a gradient descent method enhanced by computation of the optimal adaptation step. In the framework of joint diagonalization of symmetric, INDSCAL or non symmetric third-order tensors, we have developed two algorithms. For each of them, the parameters derivation is done by computing the roots of the considered criterion derivative. We also show the link between the joint diagonalization of a third-order tensor set and the canonical polyadic decomposition of a fourth-order tensor. We confront both methods through numerical simulations. The good behavior of the proposed algorithms is illustrated by means of computing simulations. Finally, they are applied to the source separation of digital telecommunication signals.

<p>This thesis is concerned with the solution of the blind source separation problem (BSS). The BSS problem occurs frequently in various scientific and technical applications. In essence, it consists in separating meaningful underlying components out of a mixture of a multitude of superimposed signals.</p> <P> In the recent research literature there are two related approaches to the BSS problem: The first is known as Independent Component Analysis (ICA), where the goal is to transform the data such that the components become as independent as possible. The second is based on the notion of diagonality of certain characteristic matrices derived from the data. Here the goal is to transform the matrices such that they become as diagonal as possible. In this thesis we study the latter method of approximate joint diagonalization (AJD) to achieve a solution of the BSS problem. After an introduction to the general setting, the thesis provides an overview on particular choices for the set of target matrices that can be used for BSS by joint diagonalization.</p> <P> As the main contribution of the thesis, new algorithms for approximate joint diagonalization of several matrices with non-orthogonal transformations are developed.</p> <P> These newly developed algorithms will be tested on synthetic benchmark datasets and compared to other previous diagonalization algorithms.</p> <P> Applications of the BSS methods to biomedical signal processing are discussed and exemplified with real-life data sets of multi-channel biomagnetic recordings.</p> / <p>Diese Arbeit befasst sich mit der Lösung des Problems der blinden Signalquellentrennung (BSS). Das BSS Problem tritt häufig in vielen wissenschaftlichen und technischen Anwendungen auf. Im Kern besteht das Problem darin, aus einem Gemisch von überlagerten Signalen die zugrundeliegenden Quellsignale zu extrahieren.</p> <P> In wissenschaftlichen Publikationen zu diesem Thema werden hauptsächlich zwei Lösungsansätze verfolgt:</p> <P> Ein Ansatz ist die sogenannte "Analyse der unabhängigen Komponenten", die zum Ziel hat, eine lineare Transformation <B>V</B> der Daten <B>X</B> zu finden, sodass die Komponenten U_n der transformierten Daten <B>U</B> = <B> V X</B> (die sogenannten "independent components") so unabhängig wie möglich sind. Ein anderer Ansatz beruht auf einer simultanen Diagonalisierung mehrerer spezieller Matrizen, die aus den Daten gebildet werden. Diese Möglichkeit der Lösung des Problems der blinden Signalquellentrennung bildet den Schwerpunkt dieser Arbeit.</p> <P> Als Hauptbeitrag der vorliegenden Arbeit präsentieren wir neue Algorithmen zur simultanen Diagonalisierung mehrerer Matrizen mit Hilfe einer nicht-orthogonalen Transformation.</p> <P> Die neu entwickelten Algorithmen werden anhand von numerischen Simulationen getestet und mit bereits bestehenden Diagonalisierungsalgorithmen verglichen. Es zeigt sich, dass unser neues Verfahren sehr effizient und leistungsfähig ist. Schließlich werden Anwendungen der BSS Methoden auf Probleme der biomedizinischen Signalverarbeitung erläutert und anhand von realistischen biomagnetischen Messdaten wird die Nützlichkeit in der explorativen Datenanalyse unter Beweis gestellt.</p>

Electroencephalographic data recorded on the human scalp can be modeled as a linear mixture of underlying dipolar source generators. The characterization of such generators is the aim of several families of signal processing methods. In this HDR we consider in several details three of such families, namely 1) EEG distributed inverse solutions, 2) diagonalization methods, including spatial filtering and blind source separation and 3) Riemannian geometry. We highlight our contributions in each of this family, we describe algorithms reporting all necessary information to make purposeful use of these methods and we give numerous examples with real data pertaining to our published studies. Traditionally only the single-subject scenario is considered; here we consider in addition the extension of some methods to the simultaneous multi-subject recording scenario. This HDR can be seen as an handbook for EEG source analysis. It will be particularly useful to students and other colleagues approaching the field.