Dans le cadre du traitement statistique du signal, la plupart des algorithmes couramment utilisés reposent sur l'utilisation de la matrice de covariance des signaux étudiés. En pratique, ce sont les versions adaptatives de ces traitements, obtenues en estimant la matrice de covariance à l'aide d'échantillons du signal, qui sont utilisés. Ces algorithmes présentent un inconvénient : ils peuvent nécessiter un nombre d'échantillons important pour obtenir de bons résultats. Lorsque la matrice de covariance possède une structure rang faible, le signal peut alors être décomposé en deux sous-espaces orthogonaux. Les projecteurs orthogonaux sur chacun de ces sous espaces peuvent alors être construits, permettant de développer des méthodes dites rang faible. Les versions adaptatives de ces méthodes atteignent des performances équivalentes à celles des traitements classiques tout en réduisant significativement le nombre d'échantillons nécessaire. Par ailleurs, l'accroissement de la taille des données ne fait que renforcer l'intérêt de ce type de méthode. Cependant, cet accroissement s'accompagne souvent d'un accroissement du nombre de dimensions du système. Deux types d'approches peuvent être envisagées pour traiter ces données : les méthodes vectorielles et les méthodes tensorielles. Les méthodes vectorielles consistent à mettre les données sous forme de vecteurs pour ensuite appliquer les traitements classiques. Cependant, lors de la mise sous forme de vecteur, la structure des données est perdue ce qui peut entraîner une dégradation des performances et/ou un manque de robustesse. Les méthodes tensorielles permettent d'éviter cet écueil. Dans ce cas, la structure est préservée en mettant les données sous forme de tenseurs, qui peuvent ensuite être traités à l'aide de l'algèbre multilinéaire. Ces méthodes sont plus complexes à utiliser puisqu'elles nécessitent d'adapter les algorithmes classiques à ce nouveau contexte. En particulier, l'extension des méthodes rang faible au cas tensoriel nécessite l'utilisation d'une décomposition tensorielle orthogonale. Le but de cette thèse est de proposer et d'étudier des algorithmes rang faible pour des modèles tensoriels. Les contributions de cette thèse se concentrent autour de trois axes. Un premier aspect concerne le calcul des performances théoriques d'un algorithme MUSIC tensoriel basé sur la Higher Order Singular Value Decomposition (HOSVD) et appliqué à un modèle de sources polarisées. La deuxième partie concerne le développement de filtres rang faible et de détecteurs rang faible dans un contexte tensoriel. Ce travail s'appuie sur une nouvelle définition de tenseur rang faible et sur une nouvelle décomposition tensorielle associée : l'Alternative Unfolding HOSVD (AU-HOSVD). La dernière partie de ce travail illustre l'intérêt de l'approche tensorielle basée sur l'AU-HOSVD, en appliquant ces algorithmes à configuration radar particulière: le Traitement Spatio-Temporel Adaptatif ou Space-Time Adaptive Process (STAP). / Most of statistical signal processing algorithms, are based on the use of signal covariance matrix. In practical cases this matrix is unknown and is estimated from samples. The adaptive versions of the algorithms can then be applied, replacing the actual covariance matrix by its estimate. These algorithms present a major drawback: they require a large number of samples in order to obtain good results. If the covariance matrix is low-rank structured, its eigenbasis may be separated in two orthogonal subspaces. Thanks to the LR approximation, orthogonal projectors onto theses subspaces may be used instead of the noise CM in processes, leading to low-rank algorithms. The adaptive versions of these algorithms achieve similar performance to classic classic ones with less samples. Furthermore, the current increase in the size of the data strengthens the relevance of this type of method. However, this increase may often be associated with an increase of the dimension of the system, leading to multidimensional samples. Such multidimensional data may be processed by two approaches: the vectorial one and the tensorial one. The vectorial approach consists in unfolding the data into vectors and applying the traditional algorithms. These operations are not lossless since they involve a loss of structure. Several issues may arise from this loss: decrease of performance and/or lack of robustness. The tensorial approach relies on multilinear algebra, which provides a good framework to exploit these data and preserve their structure information. In this context, data are represented as multidimensional arrays called tensor. Nevertheless, generalizing vectorial-based algorithms to the multilinear algebra framework is not a trivial task. In particular, the extension of low-rank algorithm to tensor context implies to choose a tensor decomposition in order to estimate the signal and noise subspaces. The purpose of this thesis is to derive and study tensor low-rank algorithms. This work is divided into three parts. The first part deals with the derivation of theoretical performance of a tensor MUSIC algorithm based on Higher Order Singular Value Decomposition (HOSVD) and its application to a polarized source model. The second part concerns the derivation of tensor low-rank filters and detectors in a general low-rank tensor context. This work is based on a new definition of tensor rank and a new orthogonal tensor decomposition : the Alternative Unfolding HOSVD (AU-HOSVD). In the last part, these algorithms are applied to a particular radar configuration : the Space-Time Adaptive Process (STAP). This application illustrates the interest of tensor approach and algorithms based on AU-HOSVD.

Modern big data often emerge as tensors. Standard statistical methods are inadequate to deal with datasets of large volume, high dimensionality, and complex structure. Therefore, it is important to develop algorithms such as low-rank tensor decomposition for data compression, dimensionality reduction, and approximation. With the advancement in technology, high-dimensional images are becoming ubiquitous in the medical field. In lung radiation therapy, the respiratory motion of the lung introduces variabilities during treatment as the tumor inside the lung is moving, which brings challenges to the precise delivery of radiation to the tumor. Several approaches to quantifying this uncertainty propose using a model to formulate the motion through a mathematical function over time. [Li et al., 2011] uses principal component analysis (PCA) to propose one such model using each image as a long vector. However, the images come in a multidimensional arrays, and vectorization breaks the spatial structure. Driven by the needs to develop low-rank tensor decomposition and provided the 4DCT and Displacement Vector Field (DVF), we introduce two tensor decompositions, Population Value Decomposition (PVD) and Population Tucker Decomposition (PTD), to estimate the respiratory lung motion with high levels of accuracy and data compression. The first algorithm is a generalization of PVD [Crainiceanu et al., 2011] to higher order tensor. The second algorithm generalizes the concept of PVD using Tucker decomposition. Both algorithms are tested on clinical and phantom DVFs. New metrics for measuring the model performance are developed in our research. Results of the two new algorithms are compared to the result of the PCA algorithm.

<p>The question about how to determine the rank of a tensor has been widely studied in the literature. However the analytical methods to compute the decomposition of tensors have not been so much developed even for low-rank tensors.</p><p>In this report we present analytical methods for finding real and complex PARAFAC decompositions of 2 x 2 x 2 tensors before computing the actual rank of the tensor.</p><p>These methods are also implemented in MATLAB.</p><p>We also consider the question of how best lower-rank approximation gives rise to problems of degeneracy, and give some analytical explanations for these issues.</p>

The question about how to determine the rank of a tensor has been widely studied in the literature. However the analytical methods to compute the decomposition of tensors have not been so much developed even for low-rank tensors. In this report we present analytical methods for finding real and complex PARAFAC decompositions of 2 x 2 x 2 tensors before computing the actual rank of the tensor. These methods are also implemented in MATLAB. We also consider the question of how best lower-rank approximation gives rise to problems of degeneracy, and give some analytical explanations for these issues.

Cities have adopted evolving urban digitization strategies, and most of those increasingly focus on data, especially in the field of public transportation. Transportation data have intuitively spatial and temporal characteristics, for they are often described with when and where the trips occur. Since a trip is often described with many attributes, the transportation data can be presented with a tensor, a container which can house data in $N$-dimensions. Unlike a traditional data frame, which only has column variables, tensor is intuitively more straightforward to explore spatio-temporal data-sets, which makes those attributes more easily interpreted. However, it requires unique techniques to extract useful and relatively correct information in attributes highly correlated with each other. This work presents a mixed model consisting of tensor decomposition combined with seasonal vector autoregression in time to find latent patterns within historical taxi data classified by types of taxis, pick-up and drop-off times of services in NYC, so that it can help predict the place and time where taxis are demanded. We validated the proposed approach using the experiment evaluation with real NYC tax data. The proposed method shows the best prediction among alternative models without geographical inference, and captures the daily patterns of taxi demands for business and entertainment needs.

In this study, to increase inference speed of convolutional neural networks, the optimization technique low-rank tensor decomposition has been implemented and applied to AlexNet which had been trained to classify dog breeds. Due to a small training set, transfer learning was used in order to be able to classify dog breeds. The purpose of the study is to investigate how effective low-rank tensor decomposition is when the training set is limited. The results obtained from this study, compared to a previous study, indicate that there is a strong relationship between the effects of the tensor decomposition and how much available training data exists. A significant speed up can be obtained in the different convolutional layers using tensor decomposition. However, since there is a need to retrain the network after the decomposition and due to the limited dataset there is a slight decrease in accuracy. / För att öka inferenshastigheten hos faltningssnätverk, har i denna studie optimeringstekniken low-rank tensor decomposition implementerats och applicerats på AlexNet, som har tränats för att klassificera hundraser. På grund av en begränsad mängd träningsdata användes transfer learning för uppgiften. Syftet med studien är att undersöka hur effektiv low-rank tensor decomposition är när träningsdatan är begränsad. Jämfört med resultaten från en tidigare studie visar resultaten från denna studie att det finns ett starkt samband mellan effekterna av low-rank tensor decomposition och hur mycket tillgänglig träningsdata som finns. En signifikant hastighetsökning kan uppnås i de olika faltningslagren med hjälp av low-rank tensor decomposition. Eftersom det finns ett behov av att träna om nätverket efter dekompositionen och på grund av den begränsade mängden data så uppnås hastighetsökningen dock på bekostnad av en viss minskning i precisionen för modellen.

Les méthodes de réseau de tenseurs (TN) ont été un ingrédient essentiel des progrès de la physique de la matière condensée et ont récemment suscité l'intérêt de la communauté de l'apprentissage automatique pour leur capacité à représenter de manière compacte des objets de très grande dimension. Les méthodes TN peuvent par exemple être utilisées pour apprendre efficacement des modèles linéaires dans des espaces de caractéristiques exponentiellement grands [1]. Dans ce manuscrit, nous dérivons des limites supérieures et inférieures sur la VC-dimension et la pseudo-dimension d'une grande classe de Modèles TN pour la classification, la régression et la complétion . Nos bornes supérieures sont valables pour les modèles linéaires paramétrés par structures TN arbitraires, et nous dérivons des limites inférieures pour les modèles de décomposition tensorielle courants (CP, Tensor Train, Tensor Ring et Tucker) montrant l'étroitesse de notre borne supérieure générale. Ces résultats sont utilisés pour dériver une borne de généralisation qui peut être appliquée à la classification avec des matrices de faible rang ainsi qu'à des classificateurs linéaires basés sur l'un des modèles de décomposition tensorielle couramment utilisés. En corollaire de nos résultats, nous obtenons une borne sur la VC-dimension du classificateur basé sur le matrix product state introduit dans [1] en fonction de la dimension de liaison (i.e. rang de train tensoriel), qui répond à un problème ouvert répertorié par Cirac, Garre-Rubio et Pérez-García [2]. / Tensor network (TN) methods have been a key ingredient of advances in condensed matter physics and have recently sparked interest in the machine learning community for their ability to compactly represent very high-dimensional objects. TN methods can for example be used to efficiently learn linear models in exponentially large feature spaces [1]. In this manuscript, we derive upper and lower bounds on the VC-dimension and pseudo-dimension of a large class of TN models for classification, regression and completion. Our upper bounds hold for linear models parameterized by arbitrary TN structures, and we derive lower bounds for common tensor decomposition models (CP, Tensor Train, Tensor Ring and Tucker) showing the tightness of our general upper bound. These results are used to derive a generalization bound which can be applied to classification with low-rank matrices as well as linear classifiers based on any of the commonly used tensor decomposition models. As a corollary of our results, we obtain a bound on the VC-dimension of the matrix product state classifier introduced in [1] as a function of the so-called bond dimension (i.e. tensor train rank), which answers an open problem listed by Cirac, Garre-Rubio and Pérez-García [2].

No description available.

Strongly correlated systems have been a major challenge for a long time in the field of theoretical chemistry. For such systems, the relevant portion of the Hilbert space scales exponentially, preventing efficient simulation on large systems. However, in many cases, the Hilbert space can be partitioned into clusters on the basis of strong and weak interactions. In this work, we mainly focus on an approach where we partition the system into smaller orbital clusters in which we can define many-particle cluster states and use traditional many-body methods to capture the rest of the inter-cluster correlations. This dissertation can be mainly divided into two parts. In the first part of this dissertation, the clustered ansatz, termed as tensor product states (TPS), is used to study large strongly correlated systems. In the second part, we study a particular type of strongly correlated system, correlated triplet pair states that arise in singlet fission. The many-body expansion (MBE) is an efficient tool that has a long history of use for calculating interaction energies, binding energies, lattice energies, and so on. We extend the incremental full configuration interaction originally proposed for a Slater determinant to a tensor product state (TPS) based wavefunction. By partitioning the active space into smaller orbital clusters, our approach starts from a cluster mean-field reference TPS configuration and includes the correlation contribution of the excited TPSs using a many-body expansion. This method, named cluster many-body expansion (cMBE), improves the convergence of MBE at lower orders compared to directly doing a block-based MBE from an RHF reference. The performance of the cMBE method is also tested on a graphene nano-sheet with a very large active space of 114 electrons in 114 orbitals, which would require 1066 determinants for the exact FCI solution. Selected CI (SCI) using determinants becomes intractable for large systems with strong correlation. We introduce a method for SCI algorithms using tensor product states which exploits local molecular structure to significantly reduce the number of SCI variables. We demonstrate the potential of this method, called tensor product selected configuration interaction (TPSCI), using a few model Hamiltonians and molecular examples. These numerical results show that TPSCI can be used to significantly reduce the number of SCI variables in the variational space, and thus paving a path for extending these deterministic and variational SCI approaches to a wider range of physical systems. The extension of the TPSCI algorithm for excited states is also investigated. TPSCI with perturbative corrections provides accurate excitation energies for low-lying triplet states with respect to extrapolated results. In the case of traditional SCI methods, accurate excitation energies are obtained only after extrapolating calculations with large variational dimensions compared to TPSCI. We provide an intuitive connection between lower triplet energy mani- folds with Hückel molecular orbital theory, providing a many-body version of Hückel theory for excited triplet states. The n-body Tucker ansatz (which is a truncated TPS wavefunction) developed in our group provides a good approximation to the low-lying states of a clusterable spin system. In this approach, a Tucker decomposition is used to obtain local cluster states which can be truncated to prune the full Hilbert space of the system. As a truncated variational approach, it has been observed that the self-consistently optimized n-body Tucker method is not size- extensive, a property important for many-body methods. We explore the use of perturbation theory and linearized coupled-cluster methods to obtain a robust yet efficient approximation. Perturbative corrections to the n-body Tucker method have been implemented for the Heisenberg Hamiltonian and numerical data for various lattices and molecular systems has been presented to show the applicability of the method. In the second part of this dissertation, we focus on studying a particular type of strongly correlated states that occurs in singlet fission material. The correlated triplet pair state 1(TT) is a key intermediate in the singlet fission process, and understanding the mechanism by which it separates into two independent triplet states is critical for leveraging singlet fission for improving solar cell efficiency. This separation mechanism is dominated by two key interactions: (i) the exchange interaction (K) between the triplets which leads to the spin splitting of the biexciton state into 1(TT),3(TT) and 5(TT) states, and (ii) the triplet-triplet energy transfer integral (t) which enables the formation of the spatially separated (but still spin entangled) state 1(T...T). We develop a simple ab initio technique to compute both the triplet-triplet exchange (K) and triplet-triplet energy transfer coupling (t). Our key findings reveal new conditions for successful correlated triplet pair state dissociation. The biexciton exchange interaction needs to be ferromagnetic or negligible compared to the triplet energy transfer for favorable dissociation. We also explore the effect of chromophore packing to reveal geometries where these conditions are achieved for tetracene. We also provide a simple connectivity rule to predict whether the through-bond coupling will be stabilizing or destabilizing for the (TT) state in covalently linked singlet fission chromophores. By drawing an analogy between the chemical system and a simple spin-lattice, one is able to determine the ordering of the multi-exciton spin state via a generalized usage of Ovchinnikov's rule. In the case of meta connectivity, we predict 5(TT) to be formed and this is later confirmed by experimental techniques like time-resolved electron spin resonance (TR-ESR). / Doctor of Philosophy / The study of the correlated motion of electrons in molecules and materials allows scientists to gain useful insights into many physical processes like photosynthesis, enzyme catalysis, superconductivity, chemical reactions and so on. Theoretical quantum chemistry tries to study the electronic properties of chemical species. The exact solution of the electron correlation problem is exponentially complex and can only be computed for small systems. Therefore, approximations are introduced for practical calculations that provide good results for ground state properties like energy, dipole moment, etc. Sometimes, more accurate calculations are required to study the properties of a system, because the system may not adhere to the as- sumptions that are made in the methods used. One such case arises in the study of strongly correlated molecules. In this dissertation, we present methods which can handle strongly correlated cases. We partition the system into smaller parts, then solve the problem in the basis of these smaller parts. We refer to this block-based wavefunction as tensor product states and they provide accurate results while avoiding the exponential scaling of the full solution. We present accurate energies for a wide variety of challenging cases, including bond breaking, excited states and π conjugated molecules. Additionally, we also investigate molecular systems that can be used to increase the efficiency of solar cells. We predict improved solar efficiency for a chromophore dimer, a result which is later experimentally verified.

In dieser Arbeit werden verschiedene Ansätze untersucht, um Tensorzerlegungsmethoden auf die Full-Configuration-Interaction-Methode (FCI) anzuwenden. Das Ziel dieser Ansätze ist es, zuverlässig konvergierende Algorithmen zu erstellen, welche es erlauben, die Wellenfunktion effizient im Canonical-Product-Tensorformat (CP) zu approximieren. Hierzu werden drei Ansätze vorgestellt, um die FCI-Wellenfunktion zu repräsentieren und darauf basierend die benötigten Koeffizienten zu bestimmen. Der erste Ansatz beruht auf einer Entwicklung der Wellenfunktion als Linearkombination von Slaterdeterminanten, bei welcher in einer Hierarchie ausgehend von der Hartree-Fock-Slaterdeterminante sukzessive besetzte Orbitale durch virtuelle Orbitale ersetzt werden. Unter Nutzung von Tensorrepräsentationen im CP wird ein lineares Gleichungssystem gelöst, um die FCI-Koeffizienten zu bestimmen. Im darauf folgenden Ansatz, welcher an Direct-CI angelehnt ist, werden Tensorrepräsentationen der Hamiltonmatrix und des Koeffizientenvektors aufgestellt, welche zur Lösung des FCI-Eigenwertproblems erforderlich sind. Hier wird ein Algorithmus vorgestellt, mit welchem das Eigenwertproblem im CP gelöst wird. In einem weiteren Ansatz wird die Repräsentation der Hamiltonmatrix und des Koeffizientenvektors im Fockraum formuliert. Dieser Ansatz erlaubt die Lösung des FCI-Eigenwertproblems mit Hilfe verschiedener Algorithmen. Diese orientieren sich an den Rayleighquotienteniterationen oder dem Davidsonalgorithmus, wobei für den ersten Algorithmus eine zweite Version entwickelt wurde, wo die Rangreduktion teilweise durch Projektionen ersetzt wurde. Für den Davidsonalgorithmus ist ein breiteres Spektrum von Molekülen behandelbar und somit können erste Untersuchungen zur Skalierung und zu den zu erwartenden Fehlern vorgestellt werden. Schließlich wird ein Ausblick auf mögliche Weiterentwicklungen gegeben, welche eine effizientere Berechnung ermöglichen und somit FCI im CP auch für größere Moleküle zugänglich macht. / In this thesis, various approaches are investigated to apply tensor decomposition methods to the Full Configuration Interaction method (FCI). The aim of these approaches is the development of algorithms, which converge reliably and which permit to approximate the wave function efficiently in the Canonical Product format (CP). Three approaches are introduced to represent the FCI wave function and to obtain the corresponding coefficients. The first approach ist based on an expansion of the wave function as a linear combination of slater determinants. In this hierarchical expansion, starting from the Hartree Fock slater determinant, the occupied orbitals are substituted by virtual orbitals. Using tensor representations in the CP, a linear system of equations is solved to obtain the FCI coefficients. In a further approach, tensor representations of the Hamiltonian matrix and the coefficient vectors are set up, which are required to solve the FCI eigenvalue problem. The tensor contractions and an algorithm to solve the eigenvalue problem in the CP are explained her in detail. In the next approach, tensor representations of the Hamiltonian matrix and the coefficient vector are constructed in the Fock space. This approach allows the application of various algorithms. They are based on the Rayleight Quotient Algorithm and the Davidson algorithm and for the first one, there exists a second version, where the rank reduction algorithm is replaced by projections. The Davidson algorithm allows to treat a broader spectrum of molecules. First investigations regarding the scaling behaviour and the expectable errors can be shown for this approach. Finally, an outlook on the further development is given, that allows for more efficient calculations and makes FCI in the CP accessible for larger molecules.