In many applications that deal with high dimensional data, it is important to not store the high dimensional object itself, but its representation in a data sparse way. This aims to reduce the storage and computational complexity. There is a general scheme for representing tensors with the help of sums of elementary tensors, where the summation structure is defined by a graph/network. This scheme allows to generalize commonly used approaches in representing a large amount of numerical data (that can be interpreted as a high dimensional object) using sums of elementary tensors. The classification does not only distinguish between elementary tensors and non-elementary tensors, but also describes the number of terms that is needed to represent an object of the tensor space. This classification is referred to as tensor network (format). This work uses the tensor network based approach and describes non-linear block Gauss-Seidel methods (ALS and DMRG) in the context of the general tensor network framework. Another contribution of the thesis is the general conversion of different tensor formats. We are able to efficiently change the underlying graph topology of a given tensor representation while using the similarities (if present) of both the original and the desired structure. This is an important feature in case only minor structural changes are required. In all approximation cases involving iterative methods, it is crucial to find and use a proper initial guess. For linear iteration schemes, a good initial guess helps to decrease the number of iteration steps that are needed to reach a certain accuracy, but it does not change the approximation result. For non-linear iteration schemes, the approximation result may depend on the initial guess. This work introduces a method to successively create an initial guess that improves some approximation results. This algorithm is based on successive rank 1 increments for the r-term format. There are still open questions about how to find the optimal tensor format for a given general problem (e.g. storage, operations, etc.). For instance in the case where a physical background is given, it might be efficient to use this knowledge to create a good network structure. There is however, no guarantee that a better (with respect to the problem) representation structure does not exist.
Strongly correlated systems exhibit phenomena -- such as high-T_c superconductivity or the fractional quantum Hall effect -- that are not explicable by classical and semi-classical methods. Moreover, due to the exponential scaling of the associated Hilbert space, solving the proposed model Hamiltonians by brute-force numerical methods is bound to fail. Thus, it is important to develop novel numerical and analytical methods that can explain the physics in this regime. Tensor Network states are quantum many-body states that help to overcome some of these difficulties by defining a family of states that depend only on a small number of parameters. Their use is twofold: they are used as variational ansatzes in numerical algorithms as well as providing a framework to represent a large class of exactly solvable models that are believed to represent all possible phases of matter. The present thesis investigates mathematical properties of these states thus deepening the understanding of how and why Tensor Networks are suitable for the description of quantum many-body systems. It is believed that tensor networks can represent ground states of local Hamiltonians, but how good is this representation? This question is of fundamental importance as variational algorithms based on tensor networks can only perform well if any ground state can be approximated efficiently in such a way. While any state can be written as a tensor network state, the number of parameters needed for the description might be too large. This is not the case for one-dimensional systems: only a few parameters are required to have a good approximation of their ground states; that, in turn, allows for numerical algorithms based on tensor networks performing well. The situation in two dimensions is somewhat more complicated, but it is known that ground states of local Hamiltonians can be expressed as tensor networks with sub-exponentially many parameters. In the present thesis, we improve on these existing bounds strengthening the claim that the language of tensor networks is suitable to describe many-body systems. Another central question is how symmetries of the system such as translational invariance, time-reversal symmetry or local unitary symmetry can be reflected in tensor networks. This question is important as systems appearing in nature might intrinsically possess certain symmetries; on one hand, understanding these symmetries simplifies the description of these systems. On the other hand, the presence of symmetries leads to the appearance of novel phases -- symmetry-protected topological (SPT) order, -- and tensor networks provide the right language to classify these phases. In one dimension and for certain classes of two-dimensional tensor networks (states generated by so-called injective tensors) it is well understood how symmetries of the state can be described. A general framework, however, has yet to be developed. In the present thesis, we contribute to the development of the theory in two ways. We first investigate the question for injective tensors, and generalize the existing proof for any geometry including the hyperbolic geometry used in the AdS/CFT correspondence. Second, we introduce a class of tensor network states that include previously known examples of states exhibiting SPT order. We show how symmetries are reflected in these states thus deepening the understanding of SPT order in two dimensions.
We study the approximation of functions by tensor networks (TNs). We show that Lebesgue
Lp-spaces in one dimension can be identified with tensor product spaces of arbitrary order through tensorization. We use this tensor product structure to define subsets of
Lp of rank-structured functions of finite representation complexity. These subsets are then used to define different approximation classes of tensor networks, associated with different measures of complexity. These approximation classes are shown to be quasi-normed linear spaces. We study some elementary properties and relationships of said spaces. In part II of this work, we will show that classical smoothness (Besov) spaces are continuously embedded into these approximation classes. We will also show that functions in these approximation classes do not possess any Besov smoothness, unless one restricts the depth of the tensor networks. The results of this work are both an analysis of the approximation spaces of TNs and a study of the expressivity of a particular type of neural networks (NN) -- namely feed-forward sum-product networks with sparse architecture. The input variables of this network result from the tensorization step, interpreted as a particular featuring step which can also be implemented with a neural network with a specific architecture. We point out interesting parallels to recent results on the expressivity of rectified linear unit (ReLU) networks -- currently one of the most popular type of NNs.
We present a brief survey on the modern tensor numerical methods for multidimensional stationary and time-dependent partial differential equations (PDEs). The guiding principle of the tensor approach is the rank-structured separable approximation of multivariate functions and operators represented on a grid. Recently, the traditional Tucker, canonical, and matrix product states (tensor train) tensor models have been applied to the grid-based electronic structure calculations, to parametric PDEs, and to dynamical equations arising in scientific computing. The essential progress is based on the quantics tensor approximation method proved to be capable to represent (approximate) function related d-dimensional data arrays of size Nd with log-volume complexity, O(dlog N). Combined with the traditional numerical schemes, these novel tools establish a new promising approach for solving multidimensional integral and differential equations using low-parametric rank-structured tensor formats. As the main example, we describe the grid-based tensor numerical approach for solving the 3D nonlinear Hartree-Fock eigenvalue problem, that was the starting point for the developments of tensor-structured numerical methods for large-scale computations in solving real-life multidimensional problems. We also discuss a new method for the fast 3D lattice summation of electrostatic potentials by assembled low-rank tensor approximation capable to treat the potential sum over millions of atoms in few seconds. We address new results on tensor approximation of the dynamical Fokker-Planck and master equations in many dimensions up to d = 20. Numerical tests demonstrate the benefits of the rank-structured tensor approximation on the aforementioned examples of multidimensional PDEs. In particular, the use of grid-based tensor representations in the reduced basis of atomics orbitals yields an accurate solution of the Hartree-Fock equation on large N × N × N grids with a grid size of up to N = 105.
In many applications, it is needed to change the topology of a tensor network directly and without approximation. This work will introduce a general scheme that satisfies these needs. We will describe the procedure by two examples and show its efficiency in terms of memory consumption and speed in various numerical experiments. In general, we are going to provide an algorithm to add an edge to a tensor network as well as an algorithm to remove an edge unless the resulting network is a connected graph.
Quantification of stochastic or quantum systems by a joint probability density or wave function is a notoriously difficult computational problem, since the solution depends on all possible states (or realizations) of the system. Due to this combinatorial flavor, even a system containing as few as ten particles may yield as many as
1010 discretized states. None of even modern supercomputers are capable to cope with this curse of dimensionality straightforwardly, when the amount of quantum particles, for example, grows up to more or less interesting order of hundreds. A traditional approach for a long time was to avoid models formulated in terms of probabilistic functions, and simulate particular system realizations in a randomized process. Since different times in different communities, data-sparse methods came into play. Generally, they aim to define all data points indirectly, by a map from a low amount of representers, and recast all operations (e.g. linear system solution) from the initial data to the effective parameters. The most advanced techniques can be applied (at least, tried) to any given array, and do not rely explicitly on its origin. The current work contributes further progress to this area in the particular direction: tensor product methods for separation of variables. The separation of variables has a long history, and is based on the following elementary concept: a function of many variables may be expanded as a product of univariate functions. On the discrete level, a function is encoded by an array of its values, or a tensor. Therefore, instead of a huge initial array, the separation of variables allows to work with univariate factors with much less efforts. The dissertation contains a short overview of existing tensor representations: canonical PARAFAC, Hierarchical Tucker, Tensor Train (TT) formats, as well as the artificial tensorisation, resulting in the Quantized Tensor Train (QTT) approximation method. The contribution of the dissertation consists in both theoretical constructions and practical numerical algorithms for high-dimensional models, illustrated on the examples of the Fokker-Planck and the chemical master equations. Both arise from stochastic dynamical processes in multiconfigurational systems, and govern the evolution of the probability function in time. A special focus is put on time propagation schemes and their properties related to tensor product methods. We show that these applications yield large-scale systems of linear equations, and prove analytical separable representations of the involved functions and operators. We propose a new combined tensor format (QTT-Tucker), which descends from the TT format (hence TT algorithms may be generalized smoothly), but provides complexity reduction by an order of magnitude. We develop a robust iterative solution algorithm, constituting most advantageous properties of the classical iterative methods from numerical analysis and alternating density matrix renormalization group (DMRG) techniques from quantum physics. Numerical experiments confirm that the new method is preferable to DMRG algorithms. It is as fast as the simplest alternating schemes, but as reliable and accurate as the Krylov methods in linear algebra.
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.