FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / In this dissertation the problem of spatial signature and direction of arrival estimation in Linear 2L-Shape and Planar arrays is investigated Methods based on tensor decompositions are proposed to treat the problem of estimating blind spatial signatures disregarding the use of training sequences and knowledge of the covariance structure of the sources By assuming that the power of the sources varies between successive time blocks decompositions for tensors of third and fourth orders obtained from spatial and spatio-temporal covariance of the received data in the array are proposed from which iterative algorithms are formulated to estimate spatial signatures of the sources Then greater spatial diversity is achieved by using the Spatial Smoothing in the 2L-Shape and Planar arrays In that case the estimation of the direction of arrival of the sources can not be obtained directly from the formulated algorithms The factorization of the Khatri-Rao product is then incorporated into these algorithms making it possible extracting estimates for the azimuth and elevation angles from matrices obtained using this method A distinguishing feature of the proposed tensor methods is their efficiency to treat the cases where the covariance matrix of the sources is non-diagonal and unknown which generally happens when working with sample data covariances computed from a reduced number of snapshots / Nesta dissertaÃÃo o problema de estimaÃÃo de assinaturas espaciais e consequentemente da direÃÃo de chegada dos sinais incidentes em arranjos Linear 2L-Shape e Planar à investigado MÃtodos baseados em decomposiÃÃes tensoriais sÃo propostos para tratar o problema de estimaÃÃo cega de assinaturas espaciais desconsiderando a utilizaÃÃo de sequÃncias de treinamento e o conhecimento da estrutura de covariÃncia das fontes Ao assumir que a potÃncia das fontes varia entre blocos de tempos sucessivos decomposiÃÃes para tensores de terceira e quarta ordem obtidas a partir da covariÃncia espacial e espaÃo-temporal dos dados recebidos no arranjo de sensores sÃo propostas a partir das quais algoritmos iterativos sÃo formulados para estimar a assinatura espacial das fontes em seguida uma maior diversidade espacial à alcanÃada utilizando a tÃcnica Spatial Smoothing na recepÃÃo de sinais nos arranjos 2L-Shape e Planar Nesse caso as estimaÃÃes da direÃÃo de chegada das fontes nÃo podem ser obtidas diretamente a partir dos algoritmos formulados de forma que a fatoraÃÃo do produto de Khatri-Rao à incorporada a estes algoritmos tornando possÃvel a obtenÃÃo de estimaÃÃes para os Ãngulos de azimute e elevaÃÃo a partir das matrizes obtidas utilizando este mÃtodo Uma caracterÃstica marcante dos mÃtodos tensoriais propostos està presente na eficiÃncia obtida no tratamento de casos em que a matriz de covariÃncia das fontes à nÃo-diagonal e desconhecida o que geralmente ocorre quando se trabalha com covariÃncias de amostras reais calculadas a partir de um nÃmero reduzido de snapshots

La factorisation des tenseurs est au coeur des méthodes d'analyse des données massives multidimensionnelles dans de nombreux domaines, dont les systèmes de recommandation, les graphes, les données médicales, le traitement du signal, la chimiométrie, et bien d'autres.Pour toutes ces applications, l'obtention rapide de la décomposition des tenseurs est cruciale pour pouvoir traiter manipuler efficacement les énormes volumes de données en jeu.L'objectif principal de cette thèse est la conception d'algorithmes pour la décomposition de tenseurs multidimensionnels creux, possédant de plusieurs centaines de millions à quelques milliards de coefficients non-nuls. De tels tenseurs sont omniprésents dans les applications citées plus haut.Nous poursuivons cet objectif via trois approches.En premier lieu, nous proposons des algorithmes parallèles à mémoire distribuée, comprenant des schémas de communication point-à-point optimisés, afin de réduire les coûts de communication. Ces algorithmes sont indépendants du partitionnement des éléments du tenseur et des matrices de faible rang. Cette propriété nous permet de proposer des stratégies de partitionnement visant à minimiser le coût de communication tout en préservant l'équilibrage de charge entre les ressources. Nous utilisons des techniques d'hypergraphes pour analyser les paramètres de calcul et de communication de ces algorithmes, ainsi que des outils de partitionnement d'hypergraphe pour déterminer des partitions à même d'offrir un meilleur passage à l'échelle. Deuxièmement, nous étudions la parallélisation sur plate-forme à mémoire partagée de ces algorithmes. Dans ce contexte, nous déterminons soigneusement les tâches de calcul et leur dépendances, et nous les exprimons en termes d'une structure de données idoine, et dont la manipulation permet de révéler le parallélisme intrinsèque du problème. Troisièmement, nous présentons un schéma de calcul en forme d'arbre binaire pour représenter les noyaux de calcul les plus coûteux des algorithmes, comme la multiplication du tenseur par un ensemble de vecteurs ou de matrices donnés. L'arbre binaire permet de factoriser certains résultats intermédiaires, et de les ré-utiliser au fil du calcul. Grâce à ce schéma, nous montrons comment réduire significativement le nombre et le coût des multiplications tenseur-vecteur et tenseur-matrice, rendant ainsi la décomposition du tenseur plus rapide à la fois pour la version séquentielle et la version parallèle des algorithmes.Enfin, le reste de la thèse décrit deux extensions sur des thèmes similaires. La première extension consiste à appliquer le schéma d'arbre binaire à la décomposition des tenseurs denses, avec une analyse précise de la complexité du problème et des méthodes pour trouver la structure arborescente qui minimise le coût total. La seconde extension consiste à adapter les techniques de partitionnement utilisées pour la décomposition des tenseurs creux à la factorisation des matrices non-négatives, problème largement étudié et pour lequel nous obtenons des algorithmes parallèles plus efficaces que les meilleurs actuellement connus.Tous les résultats théoriques de cette thèse sont accompagnés d'implémentations parallèles,aussi bien en mémoire partagée que distribuée. Tous les algorithmes proposés, avec leur réalisation sur plate-forme HPC, contribuent ainsi à faire de la décomposition de tenseurs un outil prometteur pour le traitement des masses de données actuelles et à venir. / Tensor factorization has been increasingly used to analyze high-dimensional low-rank data ofmassive scale in numerous application domains, including recommender systems, graphanalytics, health-care data analysis, signal processing, chemometrics, and many others.In these applications, efficient computation of tensor decompositions is crucial to be able tohandle such datasets of high volume. The main focus of this thesis is on efficient decompositionof high dimensional sparse tensors, with hundreds of millions to billions of nonzero entries,which arise in many emerging big data applications. We achieve this through three majorapproaches.In the first approach, we provide distributed memory parallel algorithms with efficientpoint-to-point communication scheme for reducing the communication cost. These algorithmsare agnostic to the partitioning of tensor elements and low rank decomposition matrices, whichallow us to investigate effective partitioning strategies for minimizing communication cost whileestablishing computational load balance. We use hypergraph-based techniques to analyze computational and communication requirements in these algorithms, and employ hypergraphpartitioning tools to find suitable partitions that provide much better scalability.Second, we investigate effective shared memory parallelizations of these algorithms. Here, we carefully determine unit computational tasks and their dependencies, and express them using aproper data structure that exposes the parallelism underneath.Third, we introduce a tree-based computational scheme that carries out expensive operations(involving the multiplication of the tensor with a set of vectors or matrices, found at the core ofthese algorithms) faster by factoring out and storing common partial results and effectivelyre-using them. With this computational scheme, we asymptotically reduce the number oftensor-vector and -matrix multiplications for high dimensional tensors, and thereby rendercomputing tensor decompositions significantly cheaper both for sequential and parallelalgorithms.Finally, we diversify this main course of research with two extensions on similar themes.The first extension involves applying the tree-based computational framework to computingdense tensor decompositions, with an in-depth analysis of computational complexity andmethods to find optimal tree structures minimizing the computational cost. The second workfocuses on adapting effective communication and partitioning schemes of our parallel sparsetensor decomposition algorithms to the widely used non-negative matrix factorization problem,through which we obtain significantly better parallel scalability over the state of the artimplementations.We point out that all theoretical results in the thesis are nicely corroborated by parallelexperiments on both shared-memory and distributed-memory platforms. With these fastalgorithms as well as their tuned implementations for modern HPC architectures, we rendertensor and matrix decomposition algorithms amenable to use for analyzing massive scaledatasets.

Corvino, Corvino and Schoen, Chruściel and Delay have shown the existence of a large class of asymptotically flat vacuum initial data for Einstein's field equations which are static or stationary in a neighborhood of space-like infinity, yet quite general in the interior. The proof relies on some abstract, non-constructive arguments which makes it difficult to calculate such data numerically by using similar arguments. A quasilinear elliptic system of equations is presented of which we expect that it can be used to construct vacuum initial data which are asymptotically flat, time-reflection symmetric, and asymptotic to static data up to a prescribed order at space-like infinity. A perturbation argument is used to show the existence of solutions. It is valid when the order at which the solutions approach staticity is restricted to a certain range. Difficulties appear when trying to improve this result to show the existence of solutions that are asymptotically static at higher order. The problems arise from the lack of surjectivity of a certain operator. Some tensor decompositions in asymptotically flat manifolds exhibit some of the difficulties encountered above. The Helmholtz decomposition, which plays a role in the preparation of initial data for the Maxwell equations, is discussed as a model problem. A method to circumvent the difficulties that arise when fast decay rates are required is discussed. This is done in a way that opens the possibility to perform numerical computations. The insights from the analysis of the Helmholtz decomposition are applied to the York decomposition, which is related to that part of the quasilinear system which gives rise to the difficulties. For this decomposition analogous results are obtained. It turns out, however, that in this case the presence of symmetries of the underlying metric leads to certain complications. The question, whether the results obtained so far can be used again to show by a perturbation argument the existence of vacuum initial data which approach static solutions at infinity at any given order, thus remains open. The answer requires further analysis and perhaps new methods. / Corvino, Corvino und Schoen als auch Chruściel und Delay haben die Existenz einer grossen Klasse asymptotisch flacher Anfangsdaten für Einsteins Vakuumfeldgleichungen gezeigt, die in einer Umgebung des raumartig Unendlichen statisch oder stationär aber im Inneren der Anfangshyperfläche sehr allgemein sind. Der Beweis beruht zum Teil auf abstrakten, nicht konstruktiven Argumenten, die Schwierigkeiten bereiten, wenn derartige Daten numerisch berechnet werden sollen. In der Arbeit wird ein quasilineares elliptisches Gleichungssystem vorgestellt, von dem wir annehmen, dass es geeignet ist, asymptotisch flache Vakuumanfangsdaten zu berechnen, die zeitreflektionssymmetrisch sind und im raumartig Unendlichen in einer vorgeschriebenen Ordnung asymptotisch zu statischen Daten sind. Mit einem Störungsargument wird ein Existenzsatz bewiesen, der gilt, solange die Ordnung, in welcher die Lösungen asymptotisch statische Lösungen approximieren, in einem gewissen eingeschränkten Bereich liegt. Versucht man, den Gültigkeitsbereich des Satzes zu erweitern, treten Schwierigkeiten auf. Diese hängen damit zusammen, dass ein gewisser Operator nicht mehr surjektiv ist. In einigen Tensorzerlegungen auf asymptotisch flachen Räumen treten ähnliche Probleme auf, wie die oben erwähnten. Die Helmholtzzerlegung, die bei der Bereitstellung von Anfangsdaten für die Maxwellgleichungen eine Rolle spielt, wird als ein Modellfall diskutiert. Es wird eine Methode angegeben, die es erlaubt, die Schwierigkeiten zu umgehen, die auftreten, wenn ein schnelles Abfallverhalten des gesuchten Vektorfeldes im raumartig Unendlichen gefordert wird. Diese Methode gestattet es, solche Felder auch numerisch zu berechnen. Die Einsichten aus der Analyse der Helmholtzzerlegung werden dann auf die Yorkzerlegung angewandt, die in den Teil des quasilinearen Systems eingeht, der Anlass zu den genannten Schwierigkeiten gibt. Für diese Zerlegung ergeben sich analoge Resultate. Es treten allerdings Schwierigkeiten auf, wenn die zu Grunde liegende Metrik Symmetrien aufweist. Die Frage, ob die Ergebnisse, die soweit erhalten wurden, in einem Störungsargument verwendet werden können um die Existenz von Vakuumdaten zu zeigen, die im räumlich Unendlichen in jeder Ordnung statische Daten approximieren, bleibt daher offen. Die Antwort erfordert eine weitergehende Untersuchung und möglicherweise auch neue Methoden.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / In the last two decades, multiple input multiple output (MIMO) wireless systems have been subject of intense research due to the theoretical promise of the proportional increase of the communications channel capacity as the number of antennas increases. This outstanding property supposes an efficient use of spatial diversity at both the transmitter and receiver. An important and not well explored path towards improving MIMO system performance using spatial diversity takes into account the interactions among the antennas and the (physical) propagation medium. By understanding these interactions, the transmit and receive antenna arrays can be designed to best âmatchâ the propagation medium so that the link quality and capacity can be further improved in a MIMO system. In this work, we consider the use of spherical harmonics and tensor decompositions in the problem of MIMO channel modeling and estimation. The use of spherical harmonics allows to represent the radiation patterns of antennas in terms of coefficients of an expansion, thus decoupling the transmit and receive antenna array responses from the physical propagation medium. By translating simple propagation-motivated channel models with polarization information into the spherical harmonics domain, we study how propagation parameters themselves and antenna configurations affect MIMO performance in terms of capacity and correlation. A second part of this work addresses the problem of estimating directional MIMO channels in the spherical harmonics domain using tensor decompositions. Considering both single-scattering and double-scattering propagation scenarios, we make use of the parallel factor (PARAFAC) and PARATUCK-2 decompositions, respectively, to estimate the propagating spherical modes, from which the directions of arrival (DoA) and directions of departure (DoD) can be extracted. Finally, we propose and compare two methods for optimizing the coefficients of the spherical harmonics expansion of an antenna array for a prespecified MIMO channel response. / Nas Ãltimas dÃcadas, sistemas de comunicaÃÃo sem fio de mÃltiplas antenas (MIMO - Multiple Input Multiple Output) tÃm sido objetos de intensas pesquisas devido à promessa teÃrica do aumento proporcional da capacidade com o aumento do nÃmero de antenas. Esta propriedade excepcional supÃe um uso eficiente da diversidade espacial no transmissor e receptor. Um caminho importante e nÃo bem explorado no sentido de melhorar o desempenho de sistemas MIMO usando diversidade espacial leva em conta a interaÃÃo entre as antenas e meio de propagaÃÃo (fÃsico). AtravÃs da compreensÃo dessas interaÃÃes, arranjos de antenas de recepÃÃo e transmissÃo podem ser projetados para melhor "casar" com o meio de propagaÃÃo, tal que a qualidade do link de comunicaÃÃo e capacidade possam ser melhoradas em um sistema MIMO. Neste trabalho, consideramos o uso de harmÃnicos esfÃricos e decomposiÃÃes tensoriais no problema de modelagem de canal MIMO e estimaÃÃo. O uso de harmÃnicos esfÃricos permite representar os padrÃes de radiaÃÃo de antenas em termos de coeficientes de uma expansÃo, assim desacoplando as respostas dos arranjos de antenas (transmissoras e receptoras) do meio de propagaÃÃo fÃsica. Traduzindo modelos simples de canais baseados em propagaÃÃo, com informaÃÃes de polarizaÃÃo, para o domÃnio dos harmÃnicos esfÃricos, estudamos como os parÃmetros de propagaÃÃo si e configuraÃÃes especÃficas de antenas afetam o desempenho do sistema MIMO em termos de capacidade e de correlaÃÃo. A segunda parte deste trabalho aborda o problema de estimar canais direcionais MIMO no domÃnio dos harmÃnicos esfÃricos usando decomposiÃÃes por tensores. Considerando tanto cenos de espalhamento simples e de duplo espalhamento, fazemos uso das decomposiÃÃes PARAFAC e PARATUCK2, respectivamente, para estimar os modos esfÃricos propagantes, a partir das quais as direÃÃes de chegada (DoA) e as direÃÃes de saÃda (DoD) podem ser extraÃdas. Finalmente, propomos e comparamos dois mÃtodos de otimizaÃÃo dos coeficientes da expansÃo em harmÃnicos esfÃricos de arranjos de antenas para respostas de canais MIMO prÃ-especificados .

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.

Le traitement des données massives, communément connu sous l’appellation “Big Data”, constitue l’un des principaux défis scientifiques de la communauté STIC.Plusieurs domaines, à savoir économique, industriel ou scientifique, produisent des données hétérogènes acquises selon des protocoles technologiques multi-modales. Traiter indépendamment chaque ensemble de données mesurées est clairement une approche réductrice et insatisfaisante. En faisant cela, des “relations cachées” ou des inter-corrélations entre les données peuvent être totalement ignorées.Les représentations tensorielles ont reçu une attention particulière dans ce sens en raison de leur capacité à extraire de données hétérogènes et volumineuses une information physiquement interprétable confinée à un sous-espace de dimension réduite. Dans ce cas, les données peuvent être organisées selon un tableau à D dimensions, aussi appelé tenseur d’ordre D.Dans ce contexte, le but de ce travail et que certaines propriétés soient présentes : (i) avoir des algorithmes de factorisation stables (ne souffrant pas de probème de convergence), (ii) avoir un faible coût de stockage (c’est-à-dire que le nombre de paramètres libres doit être linéaire en D), et (iii) avoir un formalisme sous forme de graphe permettant une visualisation mentale simple mais rigoureuse des décompositions tensorielles de tenseurs d’ordre élevé, soit pour D > 3.Par conséquent, nous nous appuyons sur la décomposition en train de tenseurs (TT) pour élaborer de nouveaux algorithmes de factorisation TT, et des nouvelles équivalences en termes de modélisation tensorielle, permettant une nouvelle stratégie de réduction de dimensionnalité et d'optimisation de critère des moindres carrés couplés pour l'estimation des paramètres d'intérêts nommé JIRAFE.Ces travaux d'ordre méthodologique ont eu des applications dans le contexte de l'analyse spectrale multidimensionelle et des systèmes de télécommunications à relais. / Massive and heterogeneous data processing and analysis have been clearly identified by the scientific community as key problems in several application areas. It was popularized under the generic terms of "data science" or "big data". Processing large volumes of data, extracting their hidden patterns, while preforming prediction and inference tasks has become crucial in economy, industry and science.Treating independently each set of measured data is clearly a reductiveapproach. By doing that, "hidden relationships" or inter-correlations between thedatasets may be totally missed. Tensor decompositions have received a particular attention recently due to their capability to handle a variety of mining tasks applied to massive datasets, being a pertinent framework taking into account the heterogeneity and multi-modality of the data. In this case, data can be arranged as a D-dimensional array, also referred to as a D-order tensor.In this context, the purpose of this work is that the following properties are present: (i) having a stable factorization algorithms (not suffering from convergence problems), (ii) having a low storage cost (i.e., the number of free parameters must be linear in D), and (iii) having a formalism in the form of a graph allowing a simple but rigorous mental visualization of tensor decompositions of tensors of high order, i.e., for D> 3.Therefore, we rely on the tensor train decomposition (TT) to develop new TT factorization algorithms, and new equivalences in terms of tensor modeling, allowing a new strategy of dimensionality reduction and criterion optimization of coupled least squares for the estimation of parameters named JIRAFE.This methodological work has had applications in the context of multidimensional spectral analysis and relay telecommunications systems.