Quantum chemistry is plagued by the presence of high-rank quantities, stemming from the N-body nature of the electronic Schrödinger equation. These high-rank quantities present a significant mathematical and computational barrier to the computation of chemical observables, and also drastically complicate the pedagogical understanding of important interactions between particles in a molecular system. The application of physically-motivated rank reduction approaches can help address these to problems. This thesis details recent efforts to apply rank reduction techniques in both of these arenas. With regards to computational tractability, the representation of the 1/r Coulomb repulsion between electrons is a critical stage in the solution of the electronic Schrödinger equation. Typically, this interaction is encapsulated via the order-4 electron repulsion integral (ERI) tensor, which is a major bottleneck in terms of generation, manipulation, and storage. Many rank reduction techniques for the ERI tensor have been proposed to ameliorate this bottleneck, most notably including the order-3 density fitting (DF) and pseudospectral (PS) representations. Here we detail a new and uniquely powerful factorization - tensor hypercontraction (THC). THC decomposes the ERI tensor as a product of five order-2 matrices (the first wholly order-2 compression proposed for the ERI) and offers great flexibility for low-scaling algorithms for the manipulations of the ERI tensor underlying electronic structure theory. THC is shown to be physically-motivated, markedly accurate, and uniquely efficient for some of the most difficult operations encountered in modern quantum chemistry. On the front of chemical understanding of electronic structure theory, we present our recent work in developing robust two-body partitions for ab initio computations of intermolecular interactions. Noncovalent interactions are the critical and delicate forces which govern such important processes as drug-protein docking, enzyme function, crystal packing, and zeolite adsorption. These forces arise as weak residual interactions leftover after the binding of electrons and nuclei into molecule, and, as such, are extremely difficult to accurately quantify or systematically understand. Symmetry-adapted perturbation theory (SAPT) provides an excellent approach to rigorously compute the interaction energy in terms of the physically-motivated components of electrostatics, exchange, induction, and dispersion. For small intermolecular dimers, this breakdown provides great insight into the nature of noncovalent interactions. However, SAPT abstracts away considerable details about the N-body interactions between particles on the two monomers which give rise to the interaction energy components. In the work presented herein, we step back slightly and extract an effective 2-body interaction for each of the N-body SAPT terms, rather than immediately tracing all the way down to the order-0 interaction energy. This effective order-2 representation of the order-N SAPT interaction allows for the robust assignment of interaction energy contributions to pairs of atoms or functional groups (the A-SAPT or F-SAPT partitions), allowing one to discuss the interaction in terms of atom- or functional-group-pairwise interactions. These A-SAPT and F-SAPT partitions can provide deep insight into the origins of complicated noncovalent interactions, e.g., by clearly shedding light on the long-contested question of the nature of the substituent effect in substituted sandwich benzene dimers.

abstract: Multidimensional data have various representations. Thanks to their simplicity in modeling multidimensional data and the availability of various mathematical tools (such as tensor decompositions) that support multi-aspect analysis of such data, tensors are increasingly being used in many application domains including scientific data management, sensor data management, and social network data analysis. Relational model, on the other hand, enables semantic manipulation of data using relational operators, such as projection, selection, Cartesian-product, and set operators. For many multidimensional data applications, tensor operations as well as relational operations need to be supported throughout the data life cycle. In this thesis, we introduce a tensor-based relational data model (TRM), which enables both tensor- based data analysis and relational manipulations of multidimensional data, and define tensor-relational operations on this model. Then we introduce a tensor-relational data management system, so called, TensorDB. TensorDB is based on TRM, which brings together relational algebraic operations (for data manipulation and integration) and tensor algebraic operations (for data analysis). We develop optimization strategies for tensor-relational operations in both in-memory and in-database TensorDB. The goal of the TRM and TensorDB is to serve as a single environment that supports the entire life cycle of data; that is, data can be manipulated, integrated, processed, and analyzed. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2014

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / In this dissertation the problem of channel estimation in cooperative MIMO systems is investigated. More specifically, channel estimation techniques have been developed for a communication system assisted by relays with amplify-and-forward (AF) processing system in a three-hop scenario. The techniques developed use training sequences and enable, at the receiving node, the estimation of all the channels involved in the communication process. In an initial scenario, we consider a communication system with N transmit antennas and M receive antennas and between these nodes we have two relay groups with R1 and R2 antennas each. We propose protocols based on temporal multiplexing to coordinate the retransmission of the signals. At the end of the training phase, the receiving node estimates the channel matrices by combining the received data. By exploiting the multilinear (tensorial) structure of the sets of signals, we can model the received data through tensor models, such as PARAFAC and PARATUCK2 . This work proposes the combined use of these models and algebraic techniques to explore the spatial diversity. Secondly, we consider that the number of transmit and receive antennas at the relays may be different and that the data can travel in a bidirectional scheme (two-way). In order to validate the algorithms we use Monte-Carlo simulations in which we compare our proposed models with competing channel estimation algorithms, such as, the PARAFAC and Khatri-Rao factorization based algorithms in terms of NMSE and bit error rate. / Nesta dissertaÃÃo o problema de estimaÃÃo de canal em sistemas MIMO cooperativos à investigado. Mais especificamente, foram desenvolvidas tÃcnicas para estimaÃÃo de canal em um sistema de comunicaÃÃo assistida por relays com processamento do tipo amplifica-e-encaminha (do inglÃs, amplify-and-forward) em um cenÃrio de 3 saltos. As tÃcnicas desenvolvidas utilizam sequÃncia de treinamento e habilitam, no nà receptor, a estimaÃÃo de todos os canais envolvidos no processo de comunicaÃÃo. Em um cenÃrio inicial, consideramos um sistema de comunicaÃÃo com N antenas transmissoras e M antenas receptoras e entre esses nÃs temos dois grupos de relays com R1 e R2 antenas cada um. Foram desenvolvidos protocolos de transmissÃo baseado em multiplexaÃÃo temporal para coordenar as retransmissÃes dos sinais. Ao final da fase de treinamento, o nà receptor faz a estimaÃÃo das matrizes de canal atravÃs da combinaÃÃo dos dados recebidos. Explorando a estrutura multilinear (tensorial) dos diversos conjuntos de sinais, podemos modelar os dados recebidos atravÃs de modelos tensoriais, tais como: PARAFAC e PARATUCK2. Este trabalho propÃe a utilizaÃÃo combinada desses modelos e de tÃcnicas algÃbricas para explorar a diversidade espacial. Em um segundo momento, consideramos que o nÃmero de antenas transmissoras e receptoras dos relays podem ser diferentes e ainda que os dados podem trafegar em um esquema bidirecional (do inglÃs, two-way). Para fins de validaÃÃo dos algoritmos utilizamos simulaÃÃes de Monte-Carlo em que comparamos os modelos propostos com outros algoritmos de estimaÃÃo de canal, tais como os algoritmos baseados em PARAFAC e FatoraÃÃo de Khatri-Rao em termos de NMSE e taxa de erro de bit.

No description available.

Le développement de méthodes de décomposition de tableaux multi-dimensionnels suscite toujours autant d'attention, notamment d'un point de vue applicatif. La plupart des algorithmes, de décompositions tensorielles, existants requièrent une estimation du rang du tenseur et sont sensibles à une surestimation de ce dernier. Toutefois, une telle estimation peut être difficile par exemple pour des rapports signal à bruit faibles. D'un autre côté, estimer simultanément le rang et les matrices de facteurs du tenseur ou du tenseur cœur n'est pas tâche facile tant les problèmes de minimisation de rang sont généralement NP-difficiles. Plusieurs travaux existants proposent d'utiliser la norme nucléaire afin de servir d'enveloppe convexe de la fonction de rang. Cependant, la minimisation de la norme nucléaire engendre généralement un coût de calcul prohibitif pour l'analyse de données de grande taille. Dans cette thèse, nous nous sommes donc intéressés à l'approximation d'un tenseur bruité par un tenseur de rang faible. Plus précisément, nous avons étudié trois modèles de décomposition tensorielle, le modèle CPD (Canonical Polyadic Decomposition), le modèle BTD (Block Term Decomposition) et le modèle MTD (Multilinear Tensor Decomposition). Pour chacun de ces modèles, nous avons proposé une nouvelle méthode d'estimation de rang utilisant une métrique moins coûteuse exploitant la parcimonie de groupe. Ces méthodes de décomposition comportent toutes deux étapes : une étape d'estimation de rang, et une étape d'estimation des matrices de facteurs exploitant le rang estimé. Des simulations sur données simulées et sur données réelles montrent que nos méthodes présentent toutes une plus grande robustesse à la présence de bruit que les approches classiques. / Last decades, tensor decompositions have gained in popularity in several application domains. Most of the existing tensor decomposition methods require an estimating of the tensor rank in a preprocessing step to guarantee an outstanding decomposition results. Unfortunately, learning the exact rank of the tensor can be difficult in some particular cases, such as for low signal to noise ratio values. The objective of this thesis is to compute the best low-rank tensor approximation by a joint estimation of the rank and the loading matrices from the noisy tensor. Based on the low-rank property and an over estimation of the loading matrices or the core tensor, this joint estimation problem is solved by promoting group sparsity of over-estimated loading matrices and/or the core tensor. More particularly, three new methods are proposed to achieve efficient low rank estimation for three different tensors decomposition models, namely Canonical Polyadic Decomposition (CPD), Block Term Decomposition (BTD) and Multilinear Tensor Decomposition (MTD). All the proposed methods consist of two steps: the first step is designed to estimate the rank, and the second step uses the estimated rank to compute accurately the loading matrices. Numerical simulations with noisy tensor and results on real data the show effectiveness of the proposed methods compared to the state-of-the-art methods.

We describe the use of a tensor mode-1 higher-order singular value decomposition (HOSVD) in the analyses of alignments of 16S and 23S ribosomal RNA (rRNA) sequences, each encoded in a cuboid of frequencies of nucleotides across positions and organisms. This mode-1 HOSVD separates the data cuboids into combinations of patterns of nucleotide frequency variation across the positions and organisms, i.e., "eigenorganisms"' and corresponding nucleotide-specific segments of "eigenpositions," respectively, independent of a-priori knowledge of the taxonomic groups and their relationships, or the rRNA structures. We show that this mode-1 HOSVD provides a mathematical framework for modeling the sequence alignments where the mathematical variables, i.e., the significant eigenpositions and eigenorganisms, are consistent with current biological understanding of the 16S and 23S rRNAs. First, the significant eigenpositions identify multiple relations of similarity and dissimilarity among the taxonomic groups, some known and some previously unknown. Second, the corresponding eigenorganisms identify positions of nucleotides exclusively conserved within the corresponding taxonomic groups, but not among them, that map out entire substructures inserted or deleted within one taxonomic group relative to another. These positions are also enriched in adenosines that are unpaired in the rRNA secondary structure, the majority of which participate in tertiary structure interactions, and some also map to the same substructures. This demonstrates that an organism's evolutionary pathway is correlated and possibly also causally coordinated with insertions or deletions of entire rRNA substructures and unpaired adenosines, i.e., structural motifs which are involved in rRNA folding and function. Third, this mode-1 HOSVD reveals two previously unknown subgenic relationships of convergence and divergence between the Archaea and Microsporidia, that might correspond to two evolutionary pathways, in both the 16S and 23S rRNA alignments. This demonstrates that even on the level of a single rRNA molecule, an organism's evolutionary pathway is composed of different types of changes in structure in reaction to multiple concurrent evolutionary forces. / text

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / In this work, the performance of MIMO systems based on space-time coding is investigated through multilinear algebra, more specifically, by means of tensor decompositions, pulling away a bit from commonly used matrix models. We assume a system composed of P transmit and M receive antennas, consisting of a combination of a space-time block code (STBC) with a formatting filter. This filter is formed by a precoding matrix and a matrix that maps the precoded signal onto the transmit antennas. For the considered system, two contributions are presented to solve the problem of channel estimation. First, we propose a tensor-based channel estimation method for orthogonal STBCs in MIMO systems, by focusing on the specific case of the Alamouti scheme. We resort to a third order PARATUCK2 tensor model for the received signal, the third dimension of which is related to the presence of the formatting filter. By capitalizing on this tensor model, a channel estimation method based on the alternating least squares (ALS) algorithm is proposed. As a second contribution, a generalization of this method to an arbitrary nonorthogonal STBC is made, where a generalized structure is proposed for the formatting filter, introducing a fourth dimension into the tensor signal model. In this case, we make use of the PARATUCK(2-4) model followed by its reduction to a structured PARAFAC model, from which a closed-form solution to the channel estimation problem is established. The performance metrics considered for evaluating the proposed channel estimation method are: (I) the quality of the estimation in terms of NMSE and (II) the system reliability in terms of Bit Error Rate. / Neste trabalho, o desempenho de sistemas MIMO baseados em codificaÃÃo espaÃo temporal à investigado via Ãlgebra multilinear, mais especificamente, por meio de decomposiÃÃes tensoriais, afastando-se um pouco dos modelos matriciais comumente adotados. Assume-se um sistema composto de P antenas transmissoras e M receptoras, consistindo de uma combinaÃÃo de um cÃdigo espaÃo-temporal em bloco com um filtro formatador. Esse filtro à formado por uma matriz de prÃ-codificaÃÃo e uma matriz que mapeia os sinais prÃ-codificados nas antenas transmissoras. Para o sistema considerado, duas contribuiÃÃes sÃo apresentadas para solucionar o problema de estimaÃÃo de canal. Primeiro, à proposto um mÃtodo tensorial de estimaÃÃo de canal para STBCs ortogonais em sistemas MIMO, tomando-se como exemplo o esquema de Alamouti. Tal mÃtodo faz uso de um modelo tensorial PARATUCK2 de terceira ordem para o sinal recebido, cuja terceira dimensÃo està associada à presenÃa do filtro formatador. Aproveitando-se desse modelo tensorial, um mÃtodo de estimaÃÃo de canal baseado no algoritmo dos mÃnimos quadrados alternados à proposto. Como uma segunda contribuiÃÃo, uma generalizaÃÃo desse modelo para um STBC nÃo ortogonal arbitrÃrio à feita, em que uma estrutura generalizada à proposta para o filtro formatador, introduzindo uma quarta dimensÃo no modelo tensorial de sinal. Neste caso, faz-se uso do modelo PARATUCK(2-4) seguido pela sua reduÃÃo a um modelo PARAFAC estruturado, a partir do qual uma soluÃÃo em forma fechada para o problema de estimaÃÃo de canal à estabelecida. As mÃtricas de desempenho consideradas para avaliaÃÃo dos mÃtodos de estimaÃÃo de canal propostos sÃo: (I) A qualidade da estimaÃÃo do canal em termos de NMSE e (II) a confiabilidade do sistema em termos de Taxa de Erro de Bit.

L'électroencéphalographie (EEG) est une technique qui est couramment utilisée pour le diagnostic et le suivi de l'épilepsie. L'objectif de cette thèse consiste à fournir des algorithmes pour l'extraction, la séparation, et la localisation de sources épileptiques à partir de données EEG. D'abord, nous considérons deux étapes de prétraitement. La première étape vise à éliminer les artéfacts musculaires à l'aide de l'analyse en composantes indépendantes (ACI). Dans ce contexte, nous proposons un nouvel algorithme par déflation semi-algébrique qui extrait les sources épileptiques de manière plus efficace que les méthodes conventionnelles, ce que nous démontrons sur données EEG simulées et réelles. La deuxième étape consiste à séparer des sources corrélées. A cette fin, nous étudions des méthodes de décomposition tensorielle déterministe exploitant des données espace-temps-fréquence ou espace-temps-vecteur-d'onde. Nous comparons les deux méthodes de prétraitement à l'aide de simulations pour déterminer dans quels cas l'ACI, la décomposition tensorielle, ou une combinaison des deux approches devraient être utilisées. Ensuite, nous traitons la localisation de sources distribuées. Après avoir présenté et classifié les méthodes de l'état de l'art, nous proposons un algorithme pour la localisation de sources distribuées qui s'appuie sur les résultats du prétraitement tensoriel. L'algorithme est évalué sur données EEG simulées et réelles. En plus, nous apportons quelques améliorations à une méthode de localisation de sources basée sur la parcimonie structurée. Enfin, une étude des performances de diverses méthodes de localisation de sources est conduite sur données EEG simulées. / Electroencephalography (EEG) is a routinely used technique for the diagnosis and management of epilepsy. In this context, the objective of this thesis consists in providing algorithms for the extraction, separation, and localization of epileptic sources from the EEG recordings. In the first part of the thesis, we consider two preprocessing steps applied to raw EEG data. The first step aims at removing muscle artifacts by means of Independent Component Analysis (ICA). In this context, we propose a new semi-algebraic deflation algorithm that extracts the epileptic sources more efficiently than conventional methods as we demonstrate on simulated and real EEG data. The second step consists in separating correlated sources that can be involved in the propagation of epileptic phenomena. To this end, we explore deterministic tensor decomposition methods exploiting space-time-frequency or space-time-wave-vector data. We compare the two preprocessing methods using computer simulations to determine in which cases ICA, tensor decomposition, or a combination of both should be used. The second part of the thesis is devoted to distributed source localization techniques. After providing a survey and a classification of current state-of-the-art methods, we present an algorithm for distributed source localization that builds on the results of the tensor-based preprocessing methods. The algorithm is evaluated on simulated and real EEG data. Furthermore, we propose several improvements of a source imaging method based on structured sparsity. Finally, a comprehensive performance study of various brain source imaging methods is conducted on physiologically plausible, simulated EEG data.

Recent advancements in sports information and technology systems have ushered in a new age of applications of both supervised and unsupervised analytical techniques in the sports domain. These automated systems capture large volumes of data points about competitors during live competition. As a result, multi-relational analyses are gaining popularity in the field of Sports Analytics. We review two case studies of dimensionality reduction with Principal Component Analysis and latent factor analysis with Non-Negative Matrix Factorization applied in sports. Also, we provide a review of a framework for extending these techniques for higher order data structures. The primary scope of this thesis is to further extend the concept of tensor decomposition through the use of function spaces. In doing so, we address the limitations of PCA to vector and matrix representations and the CP-Decomposition to tensor representations. Lastly, we provide an application in the context of professional stock car racing.

La reconnaissance en vidéo atteint de meilleures performances ces dernières années, notamment grâce à l'amélioration des réseaux de neurones profonds sur les images. Pourtant l'explosion des taux de reconnaissance en images ne s'est pas directement répercuté sur les taux en reconnaissance vidéo. Cela est dû à cette dimension supplémentaire qu'est le temps et dont il est encore difficile d'extraire une description robuste. Les réseaux de neurones récurrents introduisent une temporalité mais ils ont une mémoire limitée dans le temps. Les méthodes de description vidéo de l'état de l'art gèrent généralement le temps comme une dimension spatiale supplémentaire et la combinaison de plusieurs méthodes de description vidéo apportent les meilleures performances actuelles. Or la dimension temporelle possède une élasticité propre, différente des dimensions spatiales. En effet, la dimension temporelle peut être déformée localement : une dilatation partielle provoquera un ralentissement visuel de la vidéo sans en changer la compréhension, à l'inverse d'une dilatation spatiale sur une image qui modifierait les proportions des objets. On peut donc espérer améliorer encore la classification de contenu vidéo par la conception d'une description invariante aux changements de vitesse. Cette thèse porte sur la problématique d'une description robuste de vidéo en considérant l'élasticité de la dimension temporelle sous trois angles différents. Dans un premier temps, nous avons décrit localement et explicitement les informations de mouvements. Des singularités sont détectées sur le flot optique, puis traquées et agrégées dans une chaîne pour décrire des portions de vidéos. Nous avons utilisé cette description sur du contenu sportif. Puis nous avons extrait des descriptions globales implicites grâce aux décompositions tensorielles. Les tenseurs permettent de considérer une vidéo comme un tableau de données multi-dimensionnelles. Les descriptions extraites sont évaluées dans une tache de classification. Pour finir, nous avons étudié les méthodes de normalisation de la dimension temporelle. Nous avons utilisé les méthodes de déformations temporelles dynamiques des séquences. Nous avons montré que cette normalisation aide à une meilleure classification. / Video recognition gain in performance during the last years, especially due to the improvement in the deep learning performances on images. However the jump in recognition rate on images does not directly impact the recognition rate on videos. This limitation is certainly due to this added dimension, the time, on which a robust description is still hard to extract. The recurrent neural networks introduce temporality but they have a limited memory. State of the art methods for video description usually handle time as a spatial dimension and the combination of video description methods reach the current best accuracies. However the temporal dimension has its own elasticity, different from the spatial dimensions. Indeed, the temporal dimension of a video can be locally deformed: a partial dilatation produces a visual slow down during the video, without changing the understanding, in contrast with a spatial dilatation on an image which will modify the proportions of the shown objects. We can thus expect to improve the video content classification by creating an invariant description to these speed changes. This thesis focus on the question of a robust video description considering the elasticity of the temporal dimension under three different angles. First, we have locally and explicitly described the motion content. Singularities are detected in the optical flow, then tracked along the time axis and organized in chain to describe video part. We have used this description on sport content. Then we have extracted global and implicit description thanks to tensor decompositions. Tensor enables to consider a video as a multi-dimensional data table. The extracted description are evaluated in a classification task. Finally, we have studied speed normalization method thanks to Dynamical Time Warping methods on series. We have showed that this normalization improve the classification rates.