Student Number : 9807515F - MSc Dissertation - School of Computational and Applied Mathematics - Faculty of Science / Statistical and algebraic techniques of subspace tracking were tested for filtering the earth’s response from airborne magnetic field gradients in order to discriminate the relatively small response (dipole) of objects on the earth’s surface, such as UXO. Filtering the data was not very effective with these methods but a subspace was found in the data for the magnitude of the magnetic moment of the dipole. This subspace is easily obtained using the singular value decomposition and can be used for an approximate location, without depth estimation, as well as the relative size of the dipole.

The proposed research is devoted to devising system identification and fault detection approaches and algorithms for a system characterized by nonlinear dynamics. Mathematical models of dynamical systems and fault models are built based on observed data from systems. In particular, we will focus on statistical subspace instrumental variable methods which allow the consideration of an appealing mathematical model in many control applications consisting of a nonlinear feedback system with nonlinearities at both inputs and outputs. Different solutions within the proposed framework are presented to solve the system identification and fault detection problems. Specifically, Augmented Subspace Instrumental Variable Identification (ASIVID) approaches are proposed to identify the closed-loop nonlinear Hammerstein systems. Then fast approaches are presented to determine the system order. Hard-over failures are detected by order determination approaches when failures manifest themselves as rank deficiencies of the dynamical systems. Geometric interpretations of subspace tracking theorems are presented in this dissertation in order to propose a fault tolerance strategy. Possible fields of application considered in this research include manufacturing systems, autonomous vehicle systems, space systems and burgeoning bio-mechanical systems.

Η εργασία αυτή ασχολείται με το πρόβλημα της εκτίμησης καναλιού σε συστήματα μετάδοσης OFDM. Το πρόβλημα αυτό συγκεντρώνει έντονο ερευνητικό ενδιαφέρον τα τελευταία χρόνια, καθώς συναντάται σε ένα ευρύ πεδίο εφαρμογών. Η άγνωστη συνάρτηση μεταφοράς του καναλιού στα ασύρματα συστήματα μετάδοσης, καθιστά απαραίτητη την εκτίμησή του πριν από οποιαδήποτε διαδικασία μετάδοσης. Στη συγκεκριμένη μεταπτυχιακή εργασία, αντικείμενο εξέτασης αποτελεί η επίδραση καναλιού με μη γραμμικά χαρακτηριστικά σε συστήματα μετάδοσης OFDM. Αρχικά, παρουσιάζεται ένας βελτιωμένος αλγόριθμος εκτίμησης καναλιού, ο οποίος βασίζεται σε ένα παραμετρικό μοντέλο. Η απόκριση συχνότητας του καναλιού εκτιμάται χρησιμοποιώντας ένα μοντέλο με L μονοπάτια. Γίνεται χρήση της μεθόδου ESPRIT για την αρχική εκτίμηση των πολυδρομικών καθυστερήσεων, ενώ η διαδικασία παρακολούθησης γίνεται με την τεχνική IPIC DLL. Με γνωστή την πληροφορία για τις πολυδρομικές καθυστερήσεις, εκτιμάται η απόκριση του καναλιού στο πεδίο της συχνότητας με τη μέθοδο του ελαχίστου μέσου τετραγωνικού σφάλματος. Ιδιαίτερης μνείας χρήζει το κριτήριο MDL (Minimum Description Length) που χρησιμοποιείται για την εύρεση των ενεργών μονοπατιών του καναλιού. Σύμφωνα με το κριτήριο, υπολογίζεται ο ιδιοχώρος, δηλαδή οι ιδιοτιμές και τα ιδιοδιανύσματα, του πίνακα αυτοσυσχέτισης του καναλιού. Ο ιδιοχώρος αυτός εμφανίζει ιδιαίτερη δομή και μπορεί να αναλυθεί σε κάθετους μεταξύ τους υποχώρους: τον υποχώρο του σήματος (signal subspace) και αυτόν του θορύβου (noise subspace). Έχει αποδειχθεί ότι η χρήση παραμετρικού μοντέλου καναλιού μπορεί να μειώσει δραστικά τις διαστάσεις του υποχώρου του σήματος και κατά συνέπεια να βελτιώσει την απόδοση της εκτίμησης του καναλιού. Στη συνέχεια εξετάζεται η δυνατότητα εφαρμογής του αλγόριθμου PAST κατά τη διαδικασία παρακολούθησης των πολυδρομικών καθυστερήσεων και η σύγκρισή του με την απόδοση του IPIC DLL. Ο αλγόριθμος PAST έχει χαμηλή υπολογιστική πολυπλοκότητα καθώς στηρίζεται σε αναδρομικές τεχνικές παρακολούθησης του ιδιοχώρου. Στα πλαίσια της μεταπτυχιακής εργασίας έγινε συγκριτική μελέτη των τεχνικών εκτίμησης καναλιού σε συστήματα μετάδοσης OFDM. Περιγράφονται τα βασικά χαρακτηριστικά των κυριότερων αλγορίθμων της βιβλιογραφίας και στη συνέχεια παρουσιάζονται τα αποτελέσματα των προσομοιώσεων σε περιβάλλον MATLAB. Με βάση τη θεωρητική μελέτη των μεθόδων εκτίμησης και τα αποτελέσματα των προσομοιώσεων, εξάγονται συμπεράσματα για τη βελτίωση της απόδοσης που παρουσιάζουν σε σχέση με τις μη παραμετρικές τεχνικές. Τέλος, υλοποιήθηκε ένας νέος αλγόριθμος για την εύρεση του υποχώρου του σήματος, ο οποίος βελτιώνει σημαντικά την απόδοση του κριτηρίου MDL. / The basic concept in this thesis is the problem of Channel Estimation in multipath fading chanels. The method we use is based on parametric channel modeling. Firstly, we use the MDL (Minimum Descreption Length) criterium in order to estimate the number of paths in the channel. Next the ESPRIT method calculates the Time Delays for every estimated path. The second part of the algorithm is used for tracking of time delays. We firstly use an IPIC DLL (InterPath Interference Cancellation Delay Locked Loop) technique and then the path gains are calculated via a MMSE estimator. There is also a study in Subspace Tracking problem. We use the PAST and PASTd algorithms to calculate the signal subspace for every OFDM symbol transmited. The two techniques we described increase the SER performance of the non parametric channel estimator by 2dB and the MSE performance by 5dB. We also describe a new algorithm which has better performance than the MDL criterium.

Abstract Localization and tracking of multiple targets is becoming an essential feature of modern communication services and systems. Although necessary in many contexts, such as surveillance and monitoring applications, low-complexity and reliable solutions capable of coping with different degrees of information are not yet available. This thesis deals with different problems that are encountered in localization and tracking applications and aims to establish a broad understanding of multitarget systems ranging from complete active to incomplete passive solutions in dynamic scenarios. Thereby we start by investigating a fully algebraic framework which is proved to be advantageous in dynamic contexts characterized by no a-priori knowledge. Subsequently we extend the approach to improve its robustness versus corrupted observations. Finally we focus on a Bayesian formulation of the passive multitarget tracking (MTT) problem. The Thesis is based on three parts. The first part focuses on a low complexity mathematical representation of the active problem (i.e manifold-based solution). In particular, the spectrum of the matrices used to represent target locations within an algebraic, multidimensional scaling (MDS) based, solution is characterized statistically. In so doing we propose a novel Jacobi-based eigenspace tracking algorithms for Gramian matrices which is shown to be particularly convenient in a multidimensional scaling formulation of the multitarget tracking problem. The second part deals with incomplete-active multitarget scenarios as well as eventual disturbances on the ranging measurements such as bias due to non-line-of-sight conditions. In particular the aforementioned algebraic solution is extended to cope with heterogeneous information and to incorporate eventual knowledge on the confidence of the measurement information. To do so we solve the classical multidimensional scaling (C-MDS) over a novel kernel matrix and show how the intrinsic nature of this formulation allows to deal with heterogeneous information, specifically angle and distance measurements. Finally, the third part focuses on the random finite sets formulation of Bayesian multisensor MTT problem for passive scenarios. In this area a new gating strategy is proposed to lower the computational complexity of the algorithms without compromising their performance. / Tiivistelmä Useiden kohteiden yhtäaikaisesta paikannuksesta ja seurannasta on tulossa olennainen osa nykyaikaisia viestinnän palveluita ja järjestelmiä. Huolimatta siitä, että yhtäaikainen paikannus on erittäin tarpeellinen osa monissa yhteyksissä, kuten valvonnan ja kontrolloinnin sovelluksissa, siihen ei ole olemassa kompleksisuudeltaan alhaista ratkaisua, joka ottaisi huomioon kaiken saatavilla olevan informaation. Väitöskirja käsittelee useiden kohteiden paikannukseen ja seurantaan liittyviä ongelmia, ja se keskittyy antamaan laajan ymmärryksen aktiivisista täydellisistä menetelmistä passiivisiin epätäydellisiin menetelmiin dynaamisissa ympäristöissä. Saavuttaakseen tavoitteen väitöskirjassa esitetään algebrallinen kehys, jonka todistetaan olevan edistyksellinen dynaamisissa ympäristöissä, joissa ei ole ennakkoinformaatiota saatavilla. Seuraavaksi väitöskirja laajentaa esitettyä lähestymistapaa parantamalla sen vakautta vääriä havaintoja vastaan. Lopuksi esitetään bayesialainen formulointi passiiviselle usean kohteen seuranta -ongelmalle (MTT). Väitöskirja on jaettu kolmeen on osaan. Ensimmäinen osa käsittelee aktiivisen ongelman kuvaamista matemaattisesti säilyttäen alhaisen kompleksisuuden. Erityisesti tässä osassa karakterisoidaan tilastollisesti matriisien spektrin käyttäminen kohteiden paikan esittämiseen moniulotteiseen skaalaukseen (MDS) pohjautuvassa menetelmässä. Saavuttaakseen tämän väitöskirja esittää Jacobin ominaisavaruuksiin perustuvan seuranta-algoritmin Gramian matriiseille, joiden osoitetaan olevan erityisen soveltuvia usean kohteen seuraamisongelman kuvaamiseen MDS-menetelmän avulla. Toinen osa käsittelee epätäydellistä aktiivista usean kohteen skenaariota, kuten myös mittausten lopullisia häiriötä, esim. ei-näköyhteyskanavasta johtuvaa harhaa. Edellä mainittu algebrallinen ratkaisu on laajennettu ottamaan huomioon heterogeeninen informaatio sekä tieto mittausdatan luotettavuudesta. Lisäksi tässä osassa esitetään ratkaisu klassiseen moniulotteiseen skaalausongelmaan (C-MDS) esittelemällä uudenlainen ydinmatriisi ja osoitetaan, kuinka tämä mahdollistaa heterogeenisen informaation, tässä tapauksessa kulma-ja etäisyysmittauksien, huomioon ottamisen. Viimeisessä osassa käsitellään äärellisten satunnaisten joukkojen soveltuvuutta bayesialaisen MTT-ongelman ratkaisuun passiivisissa skenaarioissa. Väitöskirja esittää uuden porttistrategian algoritmien kompleksisuuksien pienentämiseksi säilyttäen kuitenkin samalla niiden suorituskyvyn.

[pt] A técnica de análise de sinais corrompidos por ruído baseada no comportamento de subespaços vetoriais foi tema de alguns trabalhos publicados desde o início da década de 80. Esta nova técnica passou a ter grande importância no processamento de sinais digitais devido a fatores como robustez e precisão.Porém, o maior problema associado a este novo método é o seu elevado custo computacional. Esta característica limitou o emprego da técnica em sistemas - offline - . A preocupação então passou a ser rastrear a variação do comportamento dos subespaços vetoriais de modo eficiente. O objetivo deste rastreamento seria o emprego da técnica em alguns sistemas que operam em tempo real. Este trabalho de tese propõe um novo algoritmo de rastreamento de subespaços vetoriais. O objetivo é apresentar um algoritmo que demonstre um bom desempenho, com relação aos demais já existentes, permitindo eventual aplicação em sistemas que atuem em tempo real. Como contribuição adicional, são apresentadas uma nova análise e caracterização de sistemas que se assemelham aos circulantes, sendo para isto reinterpretada a decomposição de matrizes circulantes. O conjunto de contribuições é aplicado a um novo sistema automático de classificação de sinais comunicação, quanto ao tipo de modulação. / [en] The signal subspace analysis technique, usually applied to signals corrupted by noise, is theme of some papers since the beginning of the 80s decade. This new technique has presented important features, as robustness and precision, and became widely employed in digital signal processing. However, the main problem associated to this new method is the high computational cost. This characteristic has restricted the use of signal subspace analysis to some off-line systems. A possible way to overcome this burden was to track the signal and noise subspace behavior in the time-domain. The main objective of these methods is to allow the signal subspace analysis technique application to real time systems, sometimes at the expense of limiting analysis precision or scope. This work proposes a new subspace tracking procedure. The goal is to describe a new algorithm with good performance (precision-speed), allowing some real time systems applications. A new analysis and characterization of almost circulant systems is introduced by reinterpreting the circulating matrix decomposition scheme. The set of contributions is applied to a new analogue modulation communication signals automatic recognition structure.

De nos jours, les grandes masses de données se retrouvent dans de nombreux domaines relatifs aux applications multimédia, sociologiques, biomédicales, radio astronomiques, etc. On parle alors du phénomène ‘Big Data’ qui nécessite le développement d’outils appropriés pour la manipulation et l’analyse appropriée de telles masses de données. Ce travail de thèse est dédié au développement de méthodes efficaces pour la décomposition rapide et adaptative de tenseurs ou matrices de grandes tailles et ce pour l’analyse de données multidimensionnelles. Nous proposons en premier une méthode d’estimation de sous espaces qui s’appuie sur la technique dite ‘divide and conquer’ permettant une estimation distribuée ou parallèle des sous-espaces désirés. Après avoir démontré l’efficacité numérique de cette solution, nous introduisons différentes variantes de celle-ci pour la poursuite adaptative ou bloc des sous espaces principaux ou mineurs ainsi que des vecteurs propres de la matrice de covariance des données. Une application à la suppression d’interférences radiofréquences en radioastronomie a été traitée. La seconde partie du travail a été consacrée aux décompositions rapides de type PARAFAC ou Tucker de tenseurs multidimensionnels. Nous commençons par généraliser l’approche ‘divide and conquer’ précédente au contexte tensoriel et ce en vue de la décomposition PARAFAC parallélisable des tenseurs. Ensuite nous adaptons une technique d’optimisation de type ‘all-at-once’ pour la décomposition robuste (à la méconnaissance des ordres) de tenseurs parcimonieux et non négatifs. Finalement, nous considérons le cas de flux de données continu et proposons deux algorithmes adaptatifs pour la décomposition rapide (à complexité linéaire) de tenseurs en dimension 3. Malgré leurs faibles complexités, ces algorithmes ont des performances similaires (voire parfois supérieures) à celles des méthodes existantes de la littérature. Au final, ce travail aboutit à un ensemble d’outils algorithmiques et algébriques efficaces pour la manipulation et l’analyse de données multidimensionnelles de grandes tailles. / Large volumes of data are being generated at any given time, especially from transactional databases, multimedia content, social media, and applications of sensor networks. When the size of datasets is beyond the ability of typical database software tools to capture, store, manage, and analyze, we face the phenomenon of big data for which new and smarter data analytic tools are required. Big data provides opportunities for new form of data analytics, resulting in substantial productivity. In this thesis, we will explore fast matrix and tensor decompositions as computational tools to process and analyze multidimensional massive-data. We first aim to study fast subspace estimation, a specific technique used in matrix decomposition. Traditional subspace estimation yields high performance but suffers from processing large-scale data. We thus propose distributed/parallel subspace estimation following a divide-and-conquer approach in both batch and adaptive settings. Based on this technique, we further consider its important variants such as principal component analysis, minor and principal subspace tracking and principal eigenvector tracking. We demonstrate the potential of our proposed algorithms by solving the challenging radio frequency interference (RFI) mitigation problem in radio astronomy. In the second part, we concentrate on fast tensor decomposition, a natural extension of the matrix one. We generalize the results for the matrix case to make PARAFAC tensor decomposition parallelizable in batch setting. Then we adapt all-at-once optimization approach to consider sparse non-negative PARAFAC and Tucker decomposition with unknown tensor rank. Finally, we propose two PARAFAC decomposition algorithms for a classof third-order tensors that have one dimension growing linearly with time. The proposed algorithms have linear complexity, good convergence rate and good estimation accuracy. The results in a standard setting show that the performance of our proposed algorithms is comparable or even superior to the state-of-the-art algorithms. We also introduce an adaptive nonnegative PARAFAC problem and refine the solution of adaptive PARAFAC to tackle it. The main contributions of this thesis, as new tools to allow fast handling large-scale multidimensional data, thus bring a step forward real-time applications.

Au cours de la dernière décennie, l’étude mathématique et statistique des représentations parcimonieuses de signaux et de leurs applications en traitement du signal audio, en traitement d’image, en vidéo et en séparation de sources a connu une activité intensive. Cependant, l'exploitation de la parcimonie dans des contextes de traitement multidimensionnel comme les communications numériques reste largement ouverte. Au même temps, les méthodes aveugles semblent être la réponse à énormément de problèmes rencontrés récemment par la communauté du traitement du signal et des communications numériques tels que l'efficacité spectrale. Aussi, dans un contexte de mobilité et de non-stationnarité, il est important de pouvoir mettre en oeuvre des solutions de traitement adaptatives de faible complexité algorithmique en vue d'assurer une consommation réduite des appareils. L'objectif de cette thèse est d'aborder ces challenges de traitement multidimensionnel en proposant des solutions aveugles de faible coût de calcul en utilisant l'à priori de parcimonie. Notre travail s'articule autour de trois axes principaux : la poursuite de sous-espace principal parcimonieux, la séparation adaptative aveugle de sources parcimonieuses et l'identification aveugle des systèmes parcimonieux. Dans chaque problème, nous avons proposé de nouvelles solutions adaptatives en intégrant l'information de parcimonie aux méthodes classiques de manière à améliorer leurs performances. Des simulations numériques ont été effectuées pour confirmer l’intérêt des méthodes proposées par rapport à l'état de l'art en termes de qualité d’estimation et de complexité calculatoire. / During the last decade, the mathematical and statistical study of sparse signal representations and their applications in audio, image, video processing and source separation has been intensively active. However, exploiting sparsity in multidimensional processing contexts such as digital communications remains a largely open problem. At the same time, the blind methods seem to be the answer to a lot of problems recently encountered by the signal processing and the communications communities such as the spectral efficiency. Furthermore, in a context of mobility and non-stationarity, it is important to be able to implement adaptive processing solutions of low algorithmic complexity to ensure reduced consumption of devices. The objective of this thesis is to address these challenges of multidimensional processing by proposing blind solutions of low computational cost by using the sparsity a priori. Our work revolves around three main axes: sparse principal subspace tracking, adaptive sparse source separation and identification of sparse systems. For each problem, we propose new adaptive solutions by integrating the sparsity information to the classical methods in order to improve their performance. Numerical simulations have been conducted to confirm the superiority of the proposed methods compared to the state of the art.

Phased array feeds (PAFs) are a promising new technology for astronomical radio telescopes. While PAFs have been used in other fields, the demanding sensitivity and calibration requirements in astronomy present unique new challenges. This dissertation presents some of the first astronomical PAF results demonstrating the lowest noise temperature and highest sensitivity at the time (66 Kelvin and 3.3 m^2/K, respectively), obtained using a narrowband (425 kHz bandwidth) prototype array of 19 linear co-polarized L-band dipoles mounted at the focus of the Green Bank 20 Meter Telescope at the National Radio Astronomy Observatory (NRAO) in Green Bank, West Virginia. Results include spectral line detection of hydroxyl (OH) sources W49N and W3OH, and some of the first radio camera images made using a PAF, including an image of the Cygnus X region. A novel array Y-factor technique for measuring the isotropic noise response of the array is shown along with experimental measurements for this PAF. Statistically optimal beamformers (Maximum SNR and MVDR) are used throughout the work. Radio-frequency interference (RFI) mitigation is demonstrated experimentally using spatial cancelation with the PAF. Improved RFI mitigation is achieved in the challenging cases of low interference-to-noise ratio (INR) and moving interference by combining subspace projection (SP) beamforming with a polynomial model to track a rank 1 subspace. Limiting factors in SP are investigated including sample estimation error, subspace smearing, noise bias, and spectral scooping; each of these factors is overcome with the polynomial model and prewhitening. Numerical optimization leads to the polynomial subspace projection (PSP) method, and least-squares fitting to the series of dominant eigenvectors over a series of short term integrations (STIs) leads to the eigenvector polynomial subspace projection (EPSP) method. Expressions for the gradient, Hessian, and Jacobian are given for use in numerical optimization. Results are given for simulated and experimental data, demonstrating deeper beampattern nulls by 6 to 30dB. To increase the system bandwidth toward the hundreds of MHz bandwidth required by astronomers for a fully science-ready instrument, an FPGA digital backend is introduced using a 64-input analog-to-digital converter running at 50 Msamp/sec and the ROACH processing board developed at the University of California, Berkeley. International efforts to develop digital back ends for large antenna arrays are considered, and a road map is proposed for development of a hardware correlator/beamformer at BYU using three ROACH boards communicating over 10 gigabit Ethernet.