Cette thèse traite d’une routine d’algèbre linéaire largement utilisée pour la résolution des systèmes li- néaires, il s’agit de la factorisation LU. Habituellement, pour calculer une telle décomposition, on utilise l’élimination de Gauss avec pivotage partiel (GEPP). La stabilité numérique de l’élimination de Gauss avec pivotage partiel est caractérisée par un facteur de croissance qui est reste assez petit en pratique. Toutefois, la version parallèle de cet algorithme ne permet pas d’atteindre les bornes inférieures qui ca- ractérisent le coût de communication pour un algorithme donné. En effet, la factorisation d’un bloc de colonnes constitue un goulot d’étranglement en termes de communication. Pour remédier à ce problème, Grigori et al [60] ont développé une factorisation LU qui minimise la communication(CALU) au prix de quelques calculs redondants. En théorie la borne supérieure du facteur de croissance de CALU est plus grande que celle de l’élimination de Gauss avec pivotage partiel, cependant CALU est stable en pratique. Pour améliorer la borne supérieure du facteur de croissance, nous étudions une nouvelle stra- tégie de pivotage utilisant la factorisation QR avec forte révélation de rang. Ainsi nous développons un nouvel algorithme pour la factorisation LU par blocs. La borne supérieure du facteur de croissance de cet algorithme est plus petite que celle de l’élimination de Gauss avec pivotage partiel. Cette stratégie de pivotage est ensuite combinée avec le pivotage basé sur un tournoi pour produire une factorisation LU qui minimise la communication et qui est plus stable que CALU. Pour les systèmes hiérarchiques, plusieurs niveaux de parallélisme sont disponibles. Cependant, aucune des méthodes précédemment ci- tées n’exploite pleinement ces ressources. Nous proposons et étudions alors deux algorithmes récursifs qui utilisent les mêmes principes que CALU mais qui sont plus appropriés pour des architectures à plu- sieurs niveaux de parallélisme. Pour analyser d’une façon précise et réaliste / This dissertation focuses on a widely used linear algebra kernel to solve linear systems, that is the LU decomposition. Usually, to perform such a computation one uses the Gaussian elimination with partial pivoting (GEPP). The backward stability of GEPP depends on a quantity which is referred to as the growth factor, it is known that in general GEPP leads to modest element growth in practice. However its parallel version does not attain the communication lower bounds. Indeed the panel factorization rep- resents a bottleneck in terms of communication. To overcome this communication bottleneck, Grigori et al [60] have developed a communication avoiding LU factorization (CALU), which is asymptotically optimal in terms of communication cost at the cost of some redundant computation. In theory, the upper bound of the growth factor is larger than that of Gaussian elimination with partial pivoting, however CALU is stable in practice. To improve the upper bound of the growth factor, we study a new pivoting strategy based on strong rank revealing QR factorization. Thus we develop a new block algorithm for the LU factorization. This algorithm has a smaller growth factor upper bound compared to Gaussian elimination with partial pivoting. The strong rank revealing pivoting is then combined with tournament pivoting strategy to produce a communication avoiding LU factorization that is more stable than CALU. For hierarchical systems, multiple levels of parallelism are available. However, none of the previously cited methods fully exploit these hierarchical systems. We propose and study two recursive algorithms based on the communication avoiding LU algorithm, which are more suitable for architectures with multiple levels of parallelism. For an accurate and realistic cost analysis of these hierarchical algo- rithms, we introduce a hierarchical parallel performance model that takes into account processor and network hierarchies. This analysis enables us to accurately predict the performance of the hierarchical LU factorization on an exascale platform.

Cette thèse présente une méthode de résolution parallèle de systèmes linéaires creux qui combine efficacement les techniques de résolutions directes et itératives en utilisant une approche de type complément de Schur. Nous construisons une décomposition de domaine. L'intérieur des sous-domaines est éliminé de manière directe pour se ramener à un problème sur l'interface. Ce problème est résolu grâce à une méthode itérative préconditionnée par une factorisation incomplète. Un réordonnancement de l'interface permet la construction d'un préconditionneur global du complément de Schur. Des algorithmes minimisant le pic mémoire de la construction du préconditionneur sont proposés. Nous exploitons un schéma d'équilibrage de charge utilisant une répartition de multiples sous-domaines sur les processeurs. Les méthodes sont implémentées dans le solveur HIPS et des résultats expérimentaux parallèles sont présentés sur de grands cas tests industriels. / This thesis presents a parallel resolution method for sparse linear systems which combines effectively techniques of direct and iterative solvers using a Schur complement approach. A domain decomposition is built ; the interiors of the subdomains are eliminated by a direct method in order to use an iterative method only on the interface unknowns. The system on the interface (Schur complement) is solved thanks to an iterative method preconditioned by a global incomplete factorization. A special ordering on the Schur complement allows to build a scalable preconditioner. Algorithms minimizing the memory peak that appears during the construction of the preconditioner are presented. The memory is balanced thanks to a multiple domains per processors parallelization scheme. The methods are implemented in the HIPS solver and parallel experimental results are presented on large industrial test cases.

Dans cette thèse, nous étudions les problèmes de la factorisation d'entier et de calcul de logarithme discret dans les corps finis. Dans un premier temps, nous nous intéressons à l'algorithme de factorisation d'entier ECM et présentons une méthode pour analyser les courbes elliptiques utilisées dans cet algorithme en étudiant les propriétés galoisiennes des polynômes de division. Ensuite, nous présentons en détail l'algorithme de factorisation d'entier NFS, et nous nous intéressons en particulier à l'étape de sélection polynomiale pour laquelle des améliorations d'algorithmes existants sont proposées. Puis, nous présentons les algorithmes NFS-DL et FFS pour le calcul de logarithme discret dans les corps finis. Nous donnons aussi des détails sur deux calculs de logarithme discret effectués durant cette thèse, l'un avec NFS-DL et l'autre avec FFS. Enfin, nous étudions une étape commune à l'algorithme NFS pour la factorisation et aux algorithmes NFS-DL et FFS pour le calcul de logarithme discret: l'étape de filtrage. Nous l'étudions en détail et nous présentons une amélioration dont nous validons l'impact en utilisant des données provenant de plusieurs calculs de factorisation et de logarithme discret / In this thesis, we study the problems of integer factorization and discrete logarithm computation in finite fields. First, we study the ECM algorithm for integer factorization and present a method to analyze the elliptic curves used in this algorithm by studying the Galois properties of division polynomials. Then, we present in detail the NFS algorithm for integer factorization and we study in particular the polynomial selection step for which we propose improvements of existing algorithms. Next, we present two algorithms for computing discrete logarithms in finite fields: NFS-DL and FFS. We also give some details of two computations of discrete logarithms carried out during this thesis, one with NFS-DL and the other with FFS. Finally, we study a common step of the NFS algorithm for integer factorization and the NFS-DL and FFS algorithms for discrete logarithm computations: the filtering step. We study this step thoroughly and present an improvement for which we study the impact using data from several computations of discrete logarithms and factorizations

L'évolution rapide des besoins dus entre autres à l'innovation technique, la concurrence ou la réglementation conduit souvent à décrire le cadre d'étude des systèmes d'information dans des modèles conceptuels, pour faciliter l'évolution du fonctionnement des systèmes. La mise au point de ces modèles s'effectue en plusieurs phase au cours desquelles collaborent plusieurs équipes de nature différente, chaque intervenant apportant sa perception du système à construire en se limitant à la partie de son domaine de spécialisation. Il faut alors concilier les différentes perceptions. L'objectif essentiel de la thèse est de concevoir les mécanismes permettant d'une part d'obtenir le modèle factorisant les concepts communs à plusieurs modèles et, d'autre part, de proposer aux concepteurs une méthodologie de suivi de l'évolution de la factorisation. Pour réaliser la factorisation, nous avons mis en œuvre l'Analyse Formelle de Concepts et l'Analyse Relationnelle de Concepts (ARC) qui sont des méthodes d'analyse de données basées sur la théorie des treillis. Dans un ensemble d'entités décrites par des caractéristiques, les deux méthodes extraient des concepts formels qui associent un ensemble maximal d'entités à un ensemble maximal de caractéristiques partagées. Ces concepts formels sont structurés dans un ordre partiel de spécialisation qui les munit d'une structure de treillis. L'ARC permet de compléter la description des entités par des relations entre entités. La première contribution de la thèse est une méthode d'analyse de l'évolution de la factorisation d'un modèle basée sur l'AFC et l'ARC. Cette méthode s'appuie la capacité de l'AFC et de l'ARC à faire émerger au sein d'un modèle des abstractions thématiques de niveau supérieur, améliorant ainsi la sémantique des modèles. Nous montrons que ces méthodes peuvent aussi être employées pour suivre l'évolution du processus d'analyse avec des acteurs. Nous introduisons des métriques sur les éléments de modélisation et sur les treillis de concepts qui servent de base à l'élaboration de recommandations. Nous effectuons une expérimentation dans laquelle nous étudions l'évolution des 15 versions du modèle de classes du système d'information SIE-Pesticides. La seconde contribution de la thèse est une étude approfondie du comportement de l'ARC sur des modèles UML. Nous montrons l'influence de la structure des modèles sur différentes variables étudiées (comme les temps d'exécution et la mémoire occupée) au travers de plusieurs expérimentations sur les 15 versions du modèle SIE-Pesticides. Pour cela, nous étudions plusieurs configurations (choix d'éléments et de relations dans le méta-modèle) et plusieurs paramètres (choix d'utiliser les éléments non nommés, choix d'utiliser la navigabilité). Des métriques sont introduites pour guider le concepteur dans le pilotage du processus de factorisation et des recommandations sur les configurations et paramétrages à privilégier sont faites. La dernière contribution est une approche de factorisation inter-modèles afin de regrouper au sein d'un modèle l'ensemble des concepts communs à différents modèles sources conçus par différents experts. Outre le regroupement des concepts communs, cette analyse produit de nouvelles abstractions généralisant des concepts thématiques existants. Nous appliquons notre approche sur les 15 versions du modèle du SIE-Pesticides. L'ensemble de ces travaux s'inscrit dans un cadre de recherche dont l'objectif est de factoriser des concepts thématiques au sein d'un même modèle et de contrôler par des métriques la profusion de concepts produits par l'AFC et surtout par l'ARC. / The rapidly changing needs among other things due to technical innovation, competition and regulation often leads to describe the context for the study of conceptual models in information systems to facilitate the evolution of operating systems. The development of these models is carried out in several phases during which several working teams of different nature, providing each participant's perception of the system to be built is limited to the part of his area of specialization. It must then reconcile the different perceptions.The main objective of the thesis is to design mechanisms to obtain a share of the model factoring concepts common to several models and, secondly, to provide designers with a methodology for monitoring the evolution of factorization.To perform the factorization, we have implemented the Formal Concept Analysis and Relational Concepts Analysis (RCA), which are methods of analysis based on the theory of lattice data. In a set of entities described by features, both methods extract formal concepts that combine a maximum of entities to a maximum set of shared characteristics together. These formal concepts are structured in a partial order of specialization that provides with a lattice structure.The CRA can complement the description of the entities by relationships between entities.The first contribution of the thesis is a textbf {method a model for analyzing the evolution of the factorization based on the FCA and the RCA}. This method builds the capacity of the AFC and the CRA to emerge in a model of thematic abstractions higher level, improving semantic models. We show that these methods can also be used to monitor the analytical process with stakeholders. We introduce metrics on the design elements and the concept lattices which are the basis for the development of recommendations. We conduct an experiment in which we study the evolution of the 15 versions of the model class of information-Pesticides EIS system.The second contribution of this thesis is a textbf {depth study of the behavior of the RCA on UML models.} We show the influence of model structure on different variables studied (such as execution time and memory used) through several experiments on 15 versions of the EIS-Pesticides model. For this, we study several configurations (choice of elements and relations in the meta-model) and several parameters (choice of using unnamed elements, choice of using airworthiness). Metrics are introduced to guide the designer in managing the process of factoring and recommendations on the preferred configurations and settings are made.The last contribution is a textbf {approach to inter-model factorization} to group in a model all the concepts common to different source models designed by different experts. In addition to the consolidation of common concepts, this analysis produces new abstractions generalizing existing thematic concepts. We apply our approach on 15 versions of the model EIS-Pesticides.All this work is part of a research framework which aims to factor thematic concepts within a model and control metrics by the profusion of concepts produced by the FCA and especially by RCA.

Cette thèse considère l'apprentissage de motifs récurrents dans la perception multimodale. Elle s'attache à développer des modèles robotiques de ces facultés telles qu'observées chez l'enfant, et elle s'inscrit en cela dans le domaine de la robotique développementale.Elle s'articule plus précisément autour de deux thèmes principaux qui sont d'une part la capacité d'enfants ou de robots à imiter et à comprendre le comportement d'humains, et d'autre part l'acquisition du langage. A leur intersection, nous examinons la question de la découverte par un agent en développement d'un répertoire de motifs primitifs dans son flux perceptuel. Nous spécifions ce problème et établissons son lien avec ceux de l'indétermination de la traduction décrit par Quine et de la séparation aveugle de source tels qu'étudiés en acoustique.Nous en étudions successivement quatre sous-problèmes et formulons une définition expérimentale de chacun. Des modèles d'agents résolvant ces problèmes sont également décrits et testés. Ils s'appuient particulièrement sur des techniques dites de sacs de mots, de factorisation de matrices et d'apprentissage par renforcement inverse. Nous approfondissons séparément les trois problèmes de l'apprentissage de sons élémentaires tels les phonèmes ou les mots, de mouvements basiques de danse et d'objectifs primaires composant des tâches motrices complexes. Pour finir nous étudions le problème de l'apprentissage d'éléments primitifs multimodaux, ce qui revient à résoudre simultanément plusieurs des problèmes précédents. Nous expliquons notamment en quoi cela fournit un modèle de l'ancrage de mots acoustiques / This thesis focuses on learning recurring patterns in multimodal perception. For that purpose it develops cognitive systems that model the mechanisms providing such capabilities to infants; a methodology that fits into thefield of developmental robotics.More precisely, this thesis revolves around two main topics that are, on the one hand the ability of infants or robots to imitate and understand human behaviors, and on the other the acquisition of language. At the crossing of these topics, we study the question of the how a developmental cognitive agent can discover a dictionary of primitive patterns from its multimodal perceptual flow. We specify this problem and formulate its links with Quine's indetermination of translation and blind source separation, as studied in acoustics.We sequentially study four sub-problems and provide an experimental formulation of each of them. We then describe and test computational models of agents solving these problems. They are particularly based on bag-of-words techniques, matrix factorization algorithms, and inverse reinforcement learning approaches. We first go in depth into the three separate problems of learning primitive sounds, such as phonemes or words, learning primitive dance motions, and learning primitive objective that compose complex tasks. Finally we study the problem of learning multimodal primitive patterns, which corresponds to solve simultaneously several of the aforementioned problems. We also details how the last problems models acoustic words grounding.

在處理具遺失值之類別資料時，傳統的方法是將資料捨棄，但是這通常不是明智之舉，這些遺失某些分類訊息的資料通常還是可以提供其它重要的訊息，尤其當這類型資料的個數佔大多數時，將其捨棄可能使得估計的變異數增加，甚至影響最後的決策。如何將這些遺失某些訊息的資料納入考慮，作出完整的分析是最近幾十年間頗為重要的課題。本文主要整理了五種分析這類型資料的方法，分別為單樣本方法、多樣本方法、概似方程式因式分解法、EM演算法，以上四種方法可使用在資料遺失呈隨機分佈的條件成立下來進行分析。第五種則為樣本遺失不呈隨機分佈之分析方法。 / Traditionally, the simple way to deal with observations for which some of the variables are missing so that they cannot cross-classified into a contingency table simply excludes them from any analysis. However, it is generally agreed that such a practice would usually affect both the accuracy and the precision of the results. The purpose of the study is to bring together some of the sound alternatives available in the literature, and provide a comprehensive review. Four methods for handling data missing at random are discussed, they are single-sample method, multiple-sample method, factorization of the likelihood method, and EM algorithm. In addition, one way of handling data missing not at random is also reviewed.

In the studies underlying this thesis, various source tracing techniques were applied to environmental samples from the Baltic region. Comprehensive sampling and analysis of polychlorinated dibenzo-p-dioxins (PCDDs) and polychlorinated dibenzofurans (PCDFs) in surface sediments in Swedish coastal and offshore areas resulted in a unique data set for this region. Nearly 150 samples of surface sediments were analyzed for all tetra- to octa-chlorinated PCDD/Fs. The levels showed large spatial variability with hotspots in several coastal regions. Neither Sweden nor the EU has introduced guideline values for PCDD/Fs in sediment, but comparisons to available guidelines and quality standards from other countries indicate that large areas of primarily coastal sediments may constitute a risk to marine organisms. Multivariate pattern analysis techniques and receptor models, such as Principal Component Analysis (PCA) and Positive Matrix Factorization (PMF), were used to trace sources. These analyses suggested that three to six source types can explain most of the observed pattern variations found in the sediment samples. Atmospheric deposition was suggested as the most important source to offshore areas, thus confirming earlier estimates. However, spatial differences indicated a larger fraction of local/regional atmospheric sources, characterized by PCDFs, in the south. This was indicated by the identification of several patterns of atmospheric origin. In coastal areas, the influence of direct emission sources was larger, and among these, chlorophenol used for wood preservation and emissions from pulp/paper production and other wood related industry appeared to be most important. The historic emissions connected to processes involving chemical reactions with chlorine (e.g. pulp bleaching) were found to be of less importance except at some coastal sites. The analysis of PCDD/Fs in Baltic herring also revealed spatial variations in the levels and pollution patterns along the coast. The geographical match against areas with elevated sediment levels indicated that transfer from sediments via water to organisms was one possible explanation. Fugacity, a concept used to predict the net transport direction between environmental matrices, was used to explore the gas exchange of hexachlorocyclohexanes (HCHs) and polychlorinated biphenyls (PCBs) between air and water. These estimates suggested that, in the Kattegat Sea, the gaseous exchange of HCHs primarily resulted in net deposition while PCBs were net volatilized under certain environmental conditions. The study also indicated that, while the air concentrations of both PCBs and γ-HCH are mostly dependent upon the origin of the air mass, the fluctuations in α-HCH were primarily influenced by seasonal changes.

Τα τελευταία χρόνια χαρακτηρίζονται από μια αλματώδη ανάπτυξη των προϊόντων και υπηρεσιών που βασίζονται στα δίκτυα ασύρματης επικοινωνίας, ενώ προκύπτουν σημαντικές ερευνητικές προκλήσεις. Τα συστήματα πολλαπλών κεραιών στον πομπό και στο δέκτη, γνωστά και ως συστήματα MIMO (multi-input multi-output), καθώς και η τεχνολογία πολλαπλής προσπέλασης με χρήση κωδικών (code division multiple access, CDMA) αποτελούν δύο από τα βασικά μέτωπα ανάπτυξης των ασύρματων τηλεπικοινωνιών. Στα πλαίσια της παρούσας διδακτορικής διατριβής, ασχοληθήκαμε με την ανάπτυξη και μελέτη αλγορίθμων επεξεργασίας σήματος για τα δύο παραπάνω συστήματα, όπως περιγράφεται αναλυτικά παρακάτω. Σχετικά με τα συστήματα MIMO, η πρωτοποριακή έρευνα που πραγματοποιήθηκε στα Bell Labs γύρω στα 1996, όπου αναπτύχθηκε η αρχιτεκτονική BLAST (Bell Labs Layered Space-Time), απέδειξε ότι η χρήση πολλαπλών κεραιών μπορεί να οδηγήσει σε σημαντική αύξηση της χωρητικότητας των ασύρματων συστημάτων. Προκειμένου να αξιοποιηθούν οι παραπάνω δυνατότητες, απαιτείται η σχεδίαση σύνθετων δεκτών MIMO. Προς αυτήν την κατεύθυνση, έχει προταθεί ένας μεγάλος αριθμός μεθόδων ισοστάθμισης του καναλιού. Ωστόσο, οι περισσότερες από αυτές υποθέτουν ότι το ασύρματο κανάλι είναι: 1) χρονικά σταθερό, 2) συχνοτικά επίπεδο (δεν εισάγει διασυμβολική παρεμβολή), και κυρίως 3) ότι είναι γνωστό στο δέκτη. Δεδομένου ότι σε ευρυζωνικά συστήματα μονής φέρουσας οι παραπάνω υποθέσεις είναι δύσκολο να ικανοποιηθούν, στραφήκαμε προς τις προσαρμοστικές μεθόδους ισοστάθμισης. Συγκεκριμένα, αναπτύξαμε τρεις βασικούς αλγορίθμους. Ο πρώτος αλγόριθμος αποτελεί έναν προσαρμοστικό ισοσταθμιστή ανάδρασης αποφάσεων (decision feedback equalizer, DFE) για συχνοτικά επίπεδα κανάλια ΜΙΜΟ. Ο προτεινόμενος MIMO DFE ακολουθεί την αρχιτεκτονική BLAST, και ανανεώνεται με βάση τον αλγόριθμο αναδρομικών ελαχίστων τετραγώνων (RLS) τετραγωνικής ρίζας. Ο ισοσταθμιστής μπορεί να παρακολουθήσει ένα χρονικά μεταβαλλόμενο κανάλι, και, από όσο γνωρίζουμε, έχει τη χαμηλότερη πολυπλοκότητα από όλους τους δέκτες BLAST που έχουν προταθεί έως σήμερα. Ο δεύτερος αλγόριθμος αποτελεί την επέκταση του προηγούμενου σε συχνοτικά επιλεκτικά κανάλια. Μέσω κατάλληλης μοντελοποίησης του προβλήματος ισοστάθμισης, οδηγηθήκαμε σε έναν αποδοτικό DFE για ευρυζωνικά κανάλια MIMO. Τότε, η διαδικασία της ισοστάθμισης εμφανίζει προβλήματα αριθμητικής ευστάθειας, που λόγω της υλοποίησης RLS τετραγωνικής ρίζας αντιμετωπίστηκαν επιτυχώς. Κινούμενοι προς την κατεύθυνση περαιτέρω μείωσης της πολυπλοκότητας, προτείναμε έναν προσαρμοστικό MIMO DFE που ανανεώνεται με βάση τον αλγόριθμο ελαχίστων μέσων τετραγώνων (LMS) υλοποιημένο εξ ολοκλήρου στο πεδίο της συχνότητας. Με χρήση του ταχύ μετασχηματισμού Fourier (FFT), μειώνεται η απαιτούμενη πολυπλοκότητα. Παράλληλα, η μετάβαση στο πεδίο των συχνοτήτων έχει ως αποτέλεσμα την προσεγγιστική διαγωνοποίηση του συστήματος, προσφέροντας ανεξάρτητη ανανέωση των φίλτρων ανά συχνοτική συνιστώσα και επιτάχυνση της σύγκλισης του αλγορίθμου. Ο προτεινόμενος ισοσταθμιστής πετυχαίνει μια καλή ανταλλαγή μεταξύ απόδοσης και πολυπλοκότητας. Παράλληλα με τα παραπάνω, ασχοληθήκαμε με την εκτίμηση του ασύρματου καναλιού σε ένα ασύγχρονο σύστημα CDMA. Το βασικό σενάριο είναι ότι ο σταθμός βάσης γνωρίζει ήδη τους ενεργούς χρήστες, και καλείται να εκτιμήσει τις παραμέτρους του καναλιού ανερχόμενης ζεύξης ενός νέου χρήστη που εισέρχεται στο σύστημα. Το πρόβλημα περιγράφεται από μια συνάρτηση ελαχίστων τετραγώνων, η οποία είναι γραμμική ως προς τα κέρδη του καναλιού, και μη γραμμική ως προς τις καθυστερήσεις του. Αποδείξαμε ότι το πρόβλημα έχει μια προσεγγιστικά διαχωρίσιμη μορφή, και προτείναμε μια επαναληπτική μέθοδο υπολογισμού των παραμέτρων. Ο προτεινόμενος αλγόριθμος δεν απαιτεί κάποια ειδική ακολουθία διάχυσης και λειτουργεί αποδοτικά ακόμη και για περιορισμένη ακολουθία εκπαίδευσης. Είναι εύρωστος στην παρεμβολή πολλαπλών χρηστών και περισσότερο ακριβής από μια υπάρχουσα μέθοδο εις βάρος μιας ασήμαντης αύξησης στην υπολογιστική πολυπλοκότητα. / Over the last decades, a dramatic progress in the products and services based on wireless communication networks has been observed, while, at the same time, new research challenges arise. The systems employing multiple antennas at the transmitter and the receiver, known as MIMO (multi-input multi-output) systems, as well as code division multiple access (CDMA) systems, are two of the main technologies employed for the evolution of wireless communications. During this PhD thesis, we worked on the design and analysis of signal processing algorithms for the two above systems, as it is described in detail next. Concerning the MIMO systems, the pioneering work performed at Bell Labs around 1996, where the BLAST (Bell Labs Layered Space-Time) architecture has been developed, proved that by using multiple antennas can lead to a significant increase in wireless systems capacity. To exploit this potential, sophisticated MIMO receivers should be designed. To this end, a large amount of channel equalizers has been proposed. However, most of these methods assume that the wireless channel is: 1) static, 2) frequency flat (no intersymbol interference is introduced), and mainly 3) it is perfectly known at the receiver. Provided that in high rate single carrier systems these assumptions are difficult to be met, we focused our attention on adaptive equalization methods. More specifically, three basic algorithms have been developed. The first algorithm is an adaptive decision feedback equalizer (DFE) for frequency flat MIMO channels. The proposed MIMO DFE implements the BLAST architecture, and it is updated by the recursive least squares (RLS) algorithm in its square root form. The new equalizer can track time varying channels, and, to the best of our knowledge, it has the lowest computational complexity among the BLAST receivers that have been proposed up to now. The second algorithm is an extension of the previous one to the frequency selective channel case. By proper modeling of the equalization problem, we arrived at an efficient DFE for wideband MIMO channels. In this case, the equalization process encounters numerical instability problems, which were successfully treated by the square root RLS implementation employed. To further reduce complexity, we proposed an adaptive MIMO DFE that is updated by the least mean square (LMS) algorithm, fully implemented in the frequency domain. By using the fast Fourier transform (FFT), the complexity required is considerably reduced. Moreover, the frequency domain implementation leads to an approximate decoupling of the equalization problem at each frequency bin. Thus, an independent update of the filters at each frequency bin allows for a faster convergence of the algorithm. The proposed equalizer offers a good performance - complexity tradeoff. Furthermore, we worked on channel estimation for an asynchronous CDMA system. The assumed scenario is that the base station has already acquired all the active users, while the uplink channel parameters of a new user entering the system should be estimated. The problem can be described via a least squares cost function, which is linear with respect to the channel gains, and non linear to its delays. We proved that the problem is approximately decoupled, and a new iterative parameter estimation method has been proposed. The suggested method does not require any specific pilot sequence and performs well even for a short training interval. It is robust to multiple access interference and more accurate compared to an existing method, at the expense of an insignificant increase in computational complexity.

On étudie l’application des algorithmes de décomposition matricielles tel que la Factorisation Matricielle Non-négative (FMN), aux représentations fréquentielles de signaux audio musicaux. Ces algorithmes, dirigés par une fonction d’erreur de reconstruction, apprennent un ensemble de fonctions de base et un ensemble de coef- ficients correspondants qui approximent le signal d’entrée. On compare l’utilisation de trois fonctions d’erreur de reconstruction quand la FMN est appliquée à des gammes monophoniques et harmonisées: moindre carré, divergence Kullback-Leibler, et une mesure de divergence dépendente de la phase, introduite récemment. Des nouvelles méthodes pour interpréter les décompositions résultantes sont présentées et sont comparées aux méthodes utilisées précédemment qui nécessitent des connaissances du domaine acoustique. Finalement, on analyse la capacité de généralisation des fonctions de bases apprises par rapport à trois paramètres musicaux: l’amplitude, la durée et le type d’instrument. Pour ce faire, on introduit deux algorithmes d’étiquetage des fonctions de bases qui performent mieux que l’approche précédente dans la majorité de nos tests, la tâche d’instrument avec audio monophonique étant la seule exception importante. / We study the application of unsupervised matrix decomposition algorithms such as Non-negative Matrix Factorization (NMF) to frequency domain representations of music audio signals. These algorithms, driven by a given reconstruction error function, learn a set of basis functions and a set of corresponding coefficients that approximate the input signal. We compare the use of three reconstruction error functions when NMF is applied to monophonic and harmonized musical scales: least squares, Kullback-Leibler divergence, and a recently introduced “phase-aware” divergence measure. Novel supervised methods for interpreting the resulting decompositions are presented and compared to previously used methods that rely on domain knowledge. Finally, the ability of the learned basis functions to generalize across musical parameter values including note amplitude, note duration and instrument type, are analyzed. To do so, we introduce two basis function labeling algorithms that outperform the previous labeling approach in the majority of our tests, instrument type with monophonic audio being the only notable exception.

For noiseless sampled data, we describe the close connections between Prony--like methods, namely the classical Prony method, the matrix pencil method and the ESPRIT method. Further we present a new efficient algorithm of matrix pencil factorization based on QR decomposition of a rectangular Hankel matrix. The algorithms of parameter estimation are also applied to sparse Fourier approximation and nonlinear approximation.