Tensor network ranks
Tensor network ranks
复制标题
张量网络排名
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Lek
中科院分区：
文献类型：
--
作者：
Ke Ye;Lek
在涉及近似、完备化、去噪、降维、估计、插值、建模、降阶、回归等问题中，我们认为假设函数、矩阵或张量（我们将在本文中看到的都是同一个对象）具有低秩的近乎普遍的做法可能是不合理的。有许多自然的情况下，有关对象具有高秩相对于经典概念的秩：矩阵秩，张量秩，多线性秩-后两个是最简单的概括前者。为了弥补这一点，我们表明，可以大大扩展这些经典的概念的行列：给定任何无向图$G$，有一个概念的$G$-秩与$G$，这为我们提供了许多不同种类的行列，因为有无向图。特别是，物理学中流行的张量网络状态（例如，MPS、TTNS、PEPS、MERA）可以被认为是用于$G$的各种选择的特定$G$-秩的函数。除此之外，我们将看到一个函数、矩阵或张量可能具有非常高的矩阵、张量或多线性秩，但对于某些G$，G$秩可能非常低。事实上，差异是在数量级和差距之间的$G$-职级和这些经典职级是任意大的一些重要对象在计算机科学，数学和物理。此外，我们还证明了存在一个$G$使得几乎每个张量的$G$-秩指数地低于其秩或其周围空间的维数。
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 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., MPS, TTNS, PEPS, MERA) 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.