Gotowa bibliografia na temat „Low-Rank Tensor”

Feature extraction and tensor recovery problems are important yet challenging, particularly for multi-dimensional data with missing values and/or noise. Low-rank tensor decomposition approaches are widely used for solving these problems. This thesis focuses on three common tensor decompositions (CP, Tucker and t-SVD) and develops a set of decomposition-based approaches. The proposed methods aim to extract low-dimensional features from complete/incomplete data and recover tensors given partial and/or grossly corrupted observations.;Based on CP decomposition, semi-orthogonal multilinear principal component analysis (SO-MPCA) seeks a tensor-to-vector projection that maximizes the captured variance with the orthogonality constraint imposed in only one mode, and it further integrates the relaxed start strategy (SO-MPCA-RS) to achieve better feature extraction performance. To directly obtain the features from incomplete data, low-rank CP and Tucker decomposition with feature variance maximization (TDVM-CP and TDVM-Tucker) are proposed. TDVM methods explore the relationship among tensor samples via feature variance maximization, while estimating the missing entries via low-rank CP and Tucker approximation, leading to informative features extracted directly from partial observations. TDVM-CP extracts low-dimensional vector features viewing the weight vectors as features and TDVM-Tucker learns low-dimensional tensor features viewing the core tensors as features. TDVM methods can be generalized to other variants based on other tensor decompositions. On the other hand, this thesis solves the missing data problem by introducing low-rank matrix/tensor completion methods, and also contributes to automatic rank estimation. Rank-one matrix decomposition coupled with L1-norm regularization (L1MC) addresses the matrix rank estimation problem. With the correct estimated rank, L1MC refines its model without L1-norm regularization (L1MC-RF) and achieve optimal recovery results given enough observations. In addition, CP-based nuclear norm regularized orthogonal CP decomposition (TREL1) solves the challenging CP- and Tucker-rank estimation problems. The estimated rank can improve the tensor completion accuracy of existing decomposition-based methods. Furthermore, tensor singular value decomposition (t-SVD) combined with tensor nuclear norm (TNN) regularization (ARE_TNN) provides automatic tubal-rank estimation. With the accurate tubal-rank determination, ARE_TNN relaxes its model without the TNN constraint (TC-ARE) and results in optimal tensor completion under mild conditions. In addition, ARE_TNN refines its model by explicitly utilizing its determined tubal-rank a priori and then successfully recovers low-rank tensors based on incomplete and/or grossly corrupted observations (RTC-ARE: robust tensor completion/RTPCA-ARE: robust tensor principal component analysis).;Experiments and evaluations are presented and analyzed using synthetic data and real-world images/videos in machine learning, computer vision, and data mining applications. For feature extraction, the experimental results of face and gait recognition show that SO-MPCA-RS achieves the best overall performance compared with competing algorithms, and its relaxed start strategy is also effective for other CP-based PCA methods. In the applications of face recognition, object/action classification, and face/gait clustering, TDVM methods not only stably yield similar good results under various multi-block missing settings and different parameters in general, but also outperform the competing methods with significant improvements. For matrix/tensor rank estimation and recovery, L1MC-RF efficiently estimates the true rank and exactly recovers the incomplete images/videos under mild conditions, and outperforms the state-of-the-art algorithms on the whole. Furthermore, the empirical evaluations show that TREL1 correctly determines the CP-/Tucker- ranks well, given sufficient observed entries, which consistently improves the recovery performance of existing decomposition-based tensor completion. The t-SVD recovery methods TC-ARE, RTPCA-ARE, and RTC-ARE not only inherit the ability of ARE_TNN to achieve accurate rank estimation, but also achieve good performance in the tasks of (robust) image/video completion, video denoising, and background modeling. This outperforms the state-of-the-art methods in all cases we have tried so far with significant improvements.

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<br>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

In this thesis the application of novel tensor decomposition and tensor representation techniques in highly accurate post Hartree-Fock methods is evaluated. These representation techniques can help to overcome the steep scaling behaviour of high level ab-initio calculations with increasing system size and therefore break the "curse of dimensionality". After a comparison of various tensor formats the application of the "canonical polyadic" format (CP) is described in detail. There, especially the casting of a normal, index based tensor into the CP format (tensor decomposition) and a method for a low rank approximation (rank reduction) of the two-electron integrals in the AO basis are investigated. The decisive quantity for the applicability of the CP format is the scaling of the rank with increasing system and basis set size. The memory requirements and the computational effort for tensor manipulations in the CP format are only linear in the number of dimensions but still depend on the expansion length (rank) of the approximation. Furthermore, the AO-MO transformation and a MP2 algorithm with decomposed tensors in the CP format is evaluated and the scaling with increasing system and basis set size is investigated. Finally, a Coupled-Cluster algorithm based only on low-rank CP representation of the MO integrals is developed. There, especially the successive tensor contraction during the iterative solution of the amplitude equations and the error propagation upon multiple application of the reduction procedure are discussed. In conclusion the overall complexity of a Coupled-Cluster procedure with tensors in CP format is evaluated and some possibilities for improvements of the rank reduction procedure tailored to the needs in electronic structure calculations are shown<br>Die vorliegende Arbeit beschäftigt sich mit der Anwendung neuartiger Tensorzerlegungs- und Tensorrepesentationstechniken in hochgenauen post Hartree-Fock Methoden um das hohe Skalierungsverhalten dieser Verfahren mit steigender Systemgröße zu verringern und somit den "Fluch der Dimensionen" zu brechen. Nach einer vergleichenden Betrachtung verschiedener Representationsformate wird auf die Anwendung des "canonical polyadic" Formates (CP) detailliert eingegangen. Dabei stehen zunächst die Umwandlung eines normalen, indexbasierten Tensors in das CP Format (Tensorzerlegung) und eine Methode der Niedrigrang Approximation (Rangreduktion) für Zweielektronenintegrale in der AO Basis im Vordergrund. Die entscheidende Größe für die Anwendbarkeit ist dabei das Skalierungsverhalten das Ranges mit steigender System- und Basissatzgröße, da der Speicheraufwand und die Berechnungskosten für Tensormanipulationen im CP Format zwar nur noch linear von der Anzahl der Dimensionen des Tensors abhängen, allerdings auch mit der Expansionslänge (Rang) skalieren. Im Anschluss wird die AO-MO Transformation und der MP2 Algorithmus mit zerlegten Tensoren im CP Format diskutiert und erneut das Skalierungsverhalten mit steigender System- und Basissatzgröße untersucht. Abschließend wird ein Coupled-Cluster Algorithmus vorgestellt, welcher ausschließlich mit Tensoren in einer Niedrigrang CP Darstellung arbeitet. Dabei wird vor allem auf die sukzessive Tensorkontraktion während der iterativen Bestimmung der Amplituden eingegangen und die Fehlerfortpanzung durch Anwendung des Rangreduktions-Algorithmus analysiert. Abschließend wird die Komplexität des gesamten Verfahrens bewertet und Verbesserungsmöglichkeiten der Reduktionsprozedur aufgezeigt

Ce manuscrit regroupe différents travaux explorant les interactions entre les tenseurs et l'apprentissage automatique. Le premier chapitre est consacré à l'extension des modèles de séries reconnaissables de chaînes et d'arbres aux graphes. Nous y montrons que les modèles d'automates pondérés de chaînes et d'arbres peuvent être interprétés d'une manière simple et unifiée à l'aide de réseaux de tenseurs, et que cette interprétation s'étend naturellement aux graphes ; nous étudions certaines propriétés de ce modèle et présentons des résultats préliminaires sur leur apprentissage. Le second chapitre porte sur la minimisation approximée d'automates pondérés d'arbres et propose une approche théoriquement fondée à la problématique suivante : étant donné un automate pondéré d'arbres à n états, comment trouver un automate à m<br>This thesis tackles several problems exploring connections between tensors and machine learning. In the first chapter, we propose an extension of the classical notion of recognizable function on strings and trees to graphs. We first show that the computations of weighted automata on strings and trees can be interpreted in a natural and unifying way using tensor networks, which naturally leads us to define a computational model on graphs: graph weighted models; we then study fundamental properties of this model and present preliminary learning results. The second chapter tackles a model reduction problem for weighted tree automata. We propose a principled approach to the following problem: given a weighted tree automaton with n states, how can we find an automaton with m

Thesis: S.M., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2016.<br>This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.<br>Cataloged from student-submitted PDF version of thesis.<br>Includes bibliographical references (pages 79-83).<br>Cyber-physical systems are increasingly becoming integrated in various fields such as medicine, finance, robotics, and energy. In these systems and their applications, safety and correctness of operation is of primary concern, sparking a large amount of interest in the development of ways to verify system behavior. The tight coupling of physical constraints and computation that typically characterize cyber-physical systems make them extremely complex, resulting in unexpected failure modes. Furthermore, disturbances in the environment and uncertainties in the physical model require these systems to be robust. These are difficult constraints, requiring cyberphysical systems to be able to reason about their behavior and respond to events in real-time. Thus, the goal of automated synthesis is to construct a controller that provably implements a range of behaviors given by a specification of how the system should operate. Unfortunately, many approaches to automated synthesis are ad hoc and are limited to simple systems that admit specific structure (e.g. linear, affine systems). Not only that, but they are also designed without taking into account uncertainty. In order to tackle more general problems, several computational frameworks that allow for more general dynamics and uncertainty to be investigated. Furthermore, all of the existing computational algorithms suffer from the curse of dimensionality, the run time scales exponentially with increasing dimensionality of the state space. As a result, existing algorithms apply to systems with only a few degrees of freedom. In this thesis, we consider a stochastic optimal control problem with a special class of linear temporal logic specifications and propose a novel algorithm based on the tensor-train decomposition. We prove that the run time of the proposed algorithm scales linearly with the dimensionality of the state space and polynomially with the rank of the optimal cost-to-go function.<br>by John Irvin P. Alora.<br>S.M.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2017.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 205-214).<br>Optimal decision making under uncertainty is critical for control and optimization of complex systems. However, many techniques for solving problems such as stochastic optimal control and data assimilation encounter the curse of dimensionality when too many state variables are involved. In this thesis, we propose a framework for computing with high-dimensional functions that mitigates this exponential growth in complexity for problems with separable structure. Our framework tightly integrates two emerging areas: tensor decompositions and continuous computation. Tensor decompositions are able to effectively compress and operate with low-rank multidimensional arrays. Continuous computation is a paradigm for computing with functions instead of arrays, and it is best realized by Chebfun, a MATLAB package for computing with functions of up to three dimensions. Continuous computation provides a natural framework for building numerical algorithms that effectively, naturally, and automatically adapt to problem structure. The first part of this thesis describes a compressed continuous computation framework centered around a continuous analogue to the (discrete) tensor-train decomposition called the function-train decomposition. Computation with the function-train requires continuous matrix factorizations and continuous numerical linear algebra. Continuous analogues are presented for performing cross approximation; rounding; multilinear algebra operations such as addition, multiplication, integration, and differentiation; and continuous, rank-revealing, alternating least squares. Advantages of the function-train over the tensor-train include the ability to adaptively approximate functions and the ability to compute with functions that are parameterized differently. For example, while elementwise multiplication between tensors of different sizes is undefined, functions in FT format can be readily multiplied together. Next, we develop compressed versions of value iteration, policy iteration, and multilevel algorithms for solving dynamic programming problems arising in stochastic optimal control. These techniques enable computing global solutions to a broader set of problems, for example those with non-affine control inputs, than previously possible. Examples are presented for motion planning with robotic systems that have up to seven states. Finally, we use the FT to extend integration-based Gaussian filtering to larger state spaces than previously considered. Examples are presented for dynamical systems with up to twenty states.<br>by Alex Arkady Gorodetsky.<br>Ph. D.

Dans ce manuscrit de thèse, nous introduisons les avancées récentes sur la décomposition en matrices (et tenseurs) de rang faible et parcimonieuse ainsi que les contributions pour faire face aux principaux problèmes dans ce domaine. Nous présentons d’abord un aperçu des méthodes matricielles et tensorielles les plus récentes ainsi que ses applications sur la modélisation d’arrière-plan et la segmentation du premier plan. Ensuite, nous abordons le problème de l’initialisation du modèle de fond comme un processus de reconstruction à partir de données manquantes ou corrompues. Une nouvelle méthodologie est présentée montrant un potentiel intéressant pour l’initialisation de la modélisation du fond dans le cadre de VSI. Par la suite, nous proposons une version « double contrainte » de l’ACP robuste pour améliorer la détection de premier plan en milieu marin dans des applications de vidéo-surveillance automatisées. Nous avons aussi développé deux algorithmes incrémentaux basés sur tenseurs afin d’effectuer une séparation entre le fond et le premier plan à partir de données multidimensionnelles. Ces deux travaux abordent le problème de la décomposition de rang faible et parcimonieuse sur des tenseurs. A la fin, nous présentons un travail particulier réalisé en conjonction avec le Centre de Vision Informatique (CVC) de l’Université Autonome de Barcelone (UAB)<br>This thesis introduces the recent advances on decomposition into low-rank plus sparse matrices and tensors, as well as the main contributions to face the principal issues in moving object detection. First, we present an overview of the state-of-the-art methods for low-rank and sparse decomposition, as well as their application to background modeling and foreground segmentation tasks. Next, we address the problem of background model initialization as a reconstruction process from missing/corrupted data. A novel methodology is presented showing an attractive potential for background modeling initialization in video surveillance. Subsequently, we propose a double-constrained version of robust principal component analysis to improve the foreground detection in maritime environments for automated video-surveillance applications. The algorithm makes use of double constraints extracted from spatial saliency maps to enhance object foreground detection in dynamic scenes. We also developed two incremental tensor-based algorithms in order to perform background/foreground separation from multidimensional streaming data. These works address the problem of low-rank and sparse decomposition on tensors. Finally, we present a particular work realized in conjunction with the Computer Vision Center (CVC) at Autonomous University of Barcelona (UAB)