Extending Tensor Depth Efficiency to Tensor-Train and RNN-like Models

May 12, 2026
Theory Tensor Decomposition RNNs

ECE/CS 761

Overview

This project began from the paper On the Expressive Power of Deep Learning: A Tensor Analysis, which shows why deep hierarchical tensor factorizations are exponentially more expressive than shallow ones. The presentation mostly summarized that original paper. My actual project contribution, however, sits in the extension report: instead of stopping at the CP and HT decompositions from the paper, we asked whether a tensor-train (TT) decomposition could be analyzed in a similar way and whether it suggests an analogous depth-efficiency story for an RNN-like model.

The extension had two parts. First, we rewrote the TT decomposition into a sequential score function that behaves much more like a recurrent architecture than the original paper’s convolution-and-pooling constructions. Second, we adapted the paper’s proof style to argue that TT-generated tensors also require exponentially large CP rank almost everywhere, giving a similar separation between a deep sequential composition and a shallow CP-style model.

Motivation

The original paper is important because it gives a rigorous reason that depth matters, rather than only an empirical one. But its constructions are tied to CP and HT tensor decompositions, which line up most naturally with shallow and deep convolutional arithmetic circuits. That leaves an obvious question open: can the same theoretical viewpoint say something useful about other model families?

TT decomposition was a natural next step because it is already a popular tensor format and, unlike HT, it composes information sequentially. That makes it a promising bridge to recurrent models. The goal of the extension was therefore not just to introduce another tensor factorization, but to test whether the paper’s depth-efficiency phenomenon extends to a more sequence-like architecture.

What we extended

The original paper studies a score function built from representation functions and a coefficient tensor $A_y$ . In our extension, we replaced that coefficient tensor with a tensor-train factorization:

A_y(i_1, \ldots, i_N) = G^{(1)}_{1,i_1,:} G^{(2)}_{:,i_2,:} \cdots G^{(N)}_{:,i_N,1}

Substituting this into the score function and regrouping terms yields a sequential computation that can be written recursively as

h_y^{(0)}(X) = 1,

h_y^{(k)}(X) = \sum_{d_k=1}^{M} \left(h_y^{(k-1)} G^{(k)}_{:,d_k,:}\right) \phi_k[d_k].

This is not a vanilla RNN in a strict architectural sense. The model has no standard activation function and the interaction with the new input occurs through tensor-derived dot-product structure rather than the usual affine-plus-nonlinearity update. But it is close enough to be meaningful: each step combines a previous hidden state with a new local input representation and propagates information forward through a sequence of shared structural operations.

TT decomposition rewritten as an RNN-like sequential model.

That sequential view is what made the extension interesting. It changed the question from “Can TT factorize the same tensor?” to “Does TT induce a deeper sequential model that inherits the same kind of expressive advantage over CP?”

Theoretical result

The extension follows the original paper’s measure-theoretic proof strategy. The key claim is an analogue of the paper’s main CP-rank lower bound:

\mathrm{CP\text{-}rank}(A_y) \ge r^{N/2} \qquad \text{almost everywhere,}

where

r = \min\{r_1, \ldots, r_{N-1}, M\}.

Informally, this means that for almost every tensor generated by the TT construction, any CP representation that matches it would require exponentially many components. The bad parameter settings where this fails form a measure-zero set.

That is the heart of the extension. It says that the depth-efficiency intuition from the original HT-vs-CP result is not limited to the exact decomposition used in the paper. A sequential TT construction appears to inherit the same broad phenomenon: deep structured composition can represent tensors that shallow CP forms can only match with exponentially larger size.

Empirical check

Beyond the proof sketch, the report also included experiments on randomly generated TT core tensors. For each generated tensor, we computed the rank of its matricization as a lower bound on the CP rank needed to match it.

Empirical matricized-rank growth for randomly generated TT tensors.

The experiments supported the theory in two ways. First, matricized rank grew rapidly with tensor order, aligning with the expected exponential trend. Second, the measured ranks often exceeded the report’s proven lower bound, suggesting that the theoretical statement may be conservative and that tighter bounds could exist somewhere between $r^{N/2}$ and $r^{N-1}$ for many TT tensors.

This empirical section mattered because it kept the report from being only a proof adaptation. It gave a sanity check that the extension’s lower bound is visible in concrete random constructions, not only in symbolic analysis.

Why this extension mattered

What I like about this project is that it sits in the space between theory and architecture. The presentation material was useful for understanding the original paper, but the extension was where the actual work became mine: recasting TT decomposition into a sequential model, connecting that structure to RNN intuition, and extending the CP-rank analysis in a way that remains faithful to the original proof style.

The extension also helped clarify what kinds of statements are safe to make. I would not claim that the report proves depth efficiency for all real-world RNNs. That would be too strong. What it does provide is a principled argument that a TT-induced RNN-like construction exhibits the same sort of exponential shallow-vs-deep gap that made the original paper influential.

My contribution

This was a two-person project, and my contribution centered on the extension rather than the recap. I contributed to formulating the TT-based model, relating it to recurrent computation, and working through the proof strategy that adapts the original paper’s rank and measure-theory arguments to the TT case.

I also contributed to the experimental side that generates random TT tensors and compares their matricized ranks against the theoretical lower bound. That part was important because it let us move beyond a purely formal analogy and ask whether the extension behaves plausibly in practice.

Conclusion

This project extended a classic depth-efficiency result into a new setting that is more naturally connected to sequential models. The main takeaway is not just that TT is another useful tensor factorization, but that it provides a path for reasoning about RNN-like depth efficiency through the same tensor-analysis lens used for CNN-like architectures in the original paper.

For me, the project was valuable because it showed how to do a research extension the right way: understand the original theorem carefully, identify what structure actually matters, and then move to a new model family without claiming more than the mathematics supports. That kind of disciplined extension work is exactly the kind of theory-building I want to keep doing.