Deep neural networks are surprisingly efficient at solving practical tasks,
but the theory behind this phenomenon is only starting to catch up with the
practice. Numerous works show that depth is the key to this efficiency. A
certain class of deep convolutional networks -- namely those that correspond to
the Hierarchical Tucker (HT) tensor decomposition -- has been proven to have
exponentially higher expressive power than shallow networks. I.e. a shallow
network of exponential width is required to realize the same score function as
computed by the deep architecture. In this paper, we prove the expressive power
theorem (an exponential lower bound on the width of the equivalent shallow
network) for a class of recurrent neural networks -- ones that correspond to
the Tensor Train (TT) decomposition. This means that even processing an image
patch by patch with an RNN can be exponentially more efficient than a (shallow)
convolutional network with one hidden layer. Using theoretical results on the
relation between the tensor decompositions we compare expressive powers of the
HT- and TT-Networks. We also implement the recurrent TT-Networks and provide
numerical evidence of their expressivity.

本文证明 Tensor Train 分解的一类循环神经网络的表达能力理论上是指数级别的，与 Hierarchical Tucker 张量分解所对应的深度卷积网络相比，使用 RNN 对图像进行逐块处理可以比使用仅具有一个隐藏层的 (浅层) 卷积网络更加高效。