Tensor network ranks

Abstract

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.

37 pages, 7 figures

References in corpus (2)

• Criticality, the area law, and the computational power of PEPS
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions

Cited by in corpus (16)

• Provable Tensor Ring Completion
• Validating Quantum-Classical Programming Models with Tensor Network Simulations
• Algebraic compressed sensing
• Dimension of Tensor Network varieties
• The trouble with tensor ring decompositions
• Low-rank Tensor Grid for Image Completion
• Adaptive Learning of Tensor Network Structures
• On Stability of Tensor Networks and Canonical Forms
• Complex best $r$-term approximations almost always exist in finite dimensions
• Hermitian Tensor Decompositions
• Tensor Ring Decomposition: Optimization Landscape and One-loop Convergence of Alternating Least Squares
• Best k-layer neural network approximations
• Symmetric Tensor Decompositions On Varieties
• Automatic transformation of irreducible representations for efficient contraction of tensors with cyclic group symmetry
• A Sampling-Based Method for Tensor Ring Decomposition
• Global sensitivity analysis in probabilistic graphical models