Higher order tensor decompositions: from intuition to implementation and application

Abstract

The exponentially increasing availability of Big Data and streaming services comes as a direct consequence of the rapid development and widespread use of multi-sensor technology. The quest to make sense from such large volumes and varieties of data has both highlighted the limitations of standard “flat-view” matrix models and the necessity to move toward more versatile data analysis tools. One such algebraic framework which is naturally suited to data of large volume, variety, and veracity is a multi-way array or a tensor. The associated tensor decompositions have been recognised as a viable system to break the “Curse of Dimensionality”, an exponential increase in data volume with the tensor order. Owing to a scalable way in which they deal with multi-way data and their ability to exploit inherent deep data structures when performing feature extraction, tensor decompositions have found application in a wide range of disciplines, from very theoretical ones, such as scientific computing and physics, to the more practical aspects of signal processing and machine learning. Despite the obvious advantages, multi-dimensional analysis through tensors is not as intuitive as classical linear algebra, its counterpart for matrices and vectors. Also, tensor expressions are not so easily manipulated while the notation can be overwhelming; these may become obstacles when it comes to understanding the physical meaning of underlying operations. To this end, the material in this thesis is supported by numerous self-explanatory diagrams and examples, to equip interested readers with a natural way to grasp more sophisticated concepts inherent to multi-linear algebra. An overreaching theme of this thesis is joint analysis of multi-block information that can be naturally represented in a form of an N-way array. We demonstrate that the flexibility of tensor decompositions provides a unique opportunity to explore tensor-value data, for example through a projection onto a lower dimensional subspace where latent components can be discovered more easily. Upon providing an intrinsic link between the properties of the outer vector product, we develop a novel method for common and individual feature extraction. The proposed framework is shown to be suitable for data structures obtained from multiple observations of the same phenomenon under various interconnected conditions, such as a collection of images of the same objects taken under a range of lighting conditions and from different angles. Another aim of this thesis is to improve performance efficiency of tensor operations, the computation of which can be prohibitively expensive or completely infeasible on the raw input data in big data applications. At first, we devise a new algorithm for boosting computation of the contraction product by virtue of the Tensor Train decomposition, before introducing a cutting edge approach for evaluation of the Tucker decomposition based on the recursive update strategy that takes place only upon arrival of a new tensor-variate data sample. The efficacy of the proposed algorithms opens new avenues for the next generation of real-time streaming technologies and applications. Next, we proceed to fill the void in the open literature by introducing a novel framework that naturally incorporates physically meaningful tensor decompositions and extends classical ensemble learning in order to accommodate the intrinsically multi-way and multi-modal data. This contribution is further supported by a blood flow analysis of patients that underwent renal replacement therapy and were under constant surveillance for identifying failure in cardiovascular procedure. Finally, after revising publically available software for multi-linear analysis, we aspire to bridge the gap between sophisticated algorithms and their practical implementations. To this end, an open source toolbox is developed which offers a unifying interface that establishes a self- sufficient ecosystem for various forms of efficient representation of multi-way data and associated tensor decompositions and promotes rapid development and quick iteration from an idea to an initial functioning prototype for anyone familiar with existing machine learning libraries.