The simulation and analysis of high-dimensional problems is often infeasible due to the curse of dimensionality. In this thesis, we investigate the potential of tensor decompositions for mitigating this curse when considering systems from several application areas. Using tensor-based solvers, we directly compute numerical solutions of master equations associated with Markov processes on extremely large state spaces. Furthermore, we exploit the tensor-train format to approximate eigenvalues and corresponding eigentensors of linear tensor operators. In order to analyze the dominant dynamics of high- dimensional stochastic processes, we propose several decomposition techniques for highly diverse problems. These include tensor representations for operators based on nearest-neighbor interactions, construction of pseudoinverses for tensor-based reformulations of dimensionality reduction methods, and the approximation of transfer operators of dynamical systems. The results show that the tensor-train format enables us to compute low-rank approximations for various numerical problems as well as to reduce the memory consumption and the computational costs compared to classical approaches significantly. We demonstrate that tensor decompositions are a powerful tool for solving high-dimensional problems from various application areas.
This paper presents a novel approach to approximating tensor eigenvalues using randomized benchmarking techniques. Traditional methods for tensor eigenvalue computation, particularly for large-scale tensors, often suffer from computational bottlenecks and scalability issues. Our method addresses this challenge by exploiting the inherent redundancy in tensor representations through randomized sampling. We develop a framework that efficiently estimates tensor eigenvalues by iteratively applying randomized measurements and analyzing the resulting data. The core of the method lies in the strategic selection of measurement bases and the subsequent application of benchmarking techniques to minimize the variance of eigenvalue estimates. The resulting algorithm offers a scalable solution suitable for handling tensors with a significantly higher dimensionality compared to conventional methods. This approach demonstrates a promising avenue for accelerating tensor computations and unlocking new possibilities in various scientific and engineering domains. The theoretical analysis provides insights into the convergence properties of the algorithm, and the proposed method is demonstrated with a theoretical framework.
In problems involving approximation, completion, denoising, dimension reduction, estimation, interpolation, modeling, order reduction, regression, etc, we argue that the near-universal practice of assuming that a function, matrix, or tensor (which we will see are all the same object in this context) has \emph{low rank} may be ill-justified. There are many natural instances where the object in question has high rank with respect to the classical notions of rank: matrix rank, tensor rank, multilinear rank --- the latter two being the most straightforward generalizations of the former. To remedy this, we show that one may vastly expand these classical notions of ranks: Given any undirected graph
G, there is a notion of
G-rank associated with
G, which provides us with as many different kinds of ranks as there are undirected graphs. In particular, the popular tensor network states in physics (e.g., \textsc{mps}, \textsc{ttns}, \textsc{peps}) may be regarded as functions of a specific
G-rank for various choices of
G. Among other things, we will see that a function, matrix, or tensor may have very high matrix, tensor, or multilinear rank and yet very low
G-rank for some
G. In fact the difference is in the orders of magnitudes and the gaps between
G-ranks and these classical ranks are arbitrarily large for some important objects in computer science, mathematics, and physics. Furthermore, we show that there is a
G such that almost every tensor has
G-rank exponentially lower than its rank or the dimension of its ambient space.
Machine learning and data mining algorithms are becoming increasingly important in analyzing large volume, multi-relational and multi--modal datasets, which are often conveniently represented as multiway arrays or tensors. It is therefore timely and valuable for the multidisciplinary research community to review tensor decompositions and tensor networks as emerging tools for large-scale data analysis and data mining. We provide the mathematical and graphical representations and interpretation of tensor networks, with the main focus on the Tucker and Tensor Train (TT) decompositions and their extensions or generalizations. Keywords: Tensor networks, Function-related tensors, CP decomposition, Tucker models, tensor train (TT) decompositions, matrix product states (MPS), matrix product operators (MPO), basic tensor operations, multiway component analysis, multilinear blind source separation, tensor completion, linear/multilinear dimensionality reduction, large-scale optimization problems, symmetric eigenvalue decomposition (EVD), PCA/SVD, huge systems of linear equations, pseudo-inverse of very large matrices, Lasso and Canonical Correlation Analysis (CCA) (This is Part 1)
The hierarchical (multi-linear) rank of an order-
d tensor is key in determining the cost of representing a tensor as a (tree) Tensor Network (TN). In general, it is known that, for a fixed accuracy, a tensor with random entries cannot be expected to be efficiently approximable without the curse of dimensionality, i.e., a complexity growing exponentially with
d. In this work, we show that the ground state projection (GSP) of a class of unbounded Hamiltonians can be approximately represented as an operator of low effective dimensionality that is independent of the (high) dimension
d of the GSP. This allows to approximate the GSP without the curse of dimensionality.
Quantum circuits, fundamental to quantum computation, represent quantum states through a sequence of unitary transformations. The exponential growth in the Hilbert space dimension with increasing circuit size presents a significant challenge to simulation and analysis. This work introduces a novel tensor network approach to formally model and manipulate quantum circuits, specifically designed to mitigate this exponential scaling issue. The core idea is to represent the circuit's state vector as a tensor network, leveraging techniques for efficient compression and expansion. We explore the application of variational tensor networks (VTNs) to approximate the dynamics of quantum circuits, offering a pathway towards more scalable simulations. The effectiveness of this method is demonstrated through theoretical analysis and conceptual design, focusing on key aspects of tensor network construction and manipulation tailored to quantum circuit representations. This approach aims to provide a more scalable representation compared to existing methods.