Tensor-Train Decompositions and Rank Structure

Why a Sequential Tensor Representation?

A tensor with \(d\) modes and mode sizes \(I_1,\ldots,I_d\) has \(\prod_{k=1}^d I_k\) entries. That count grows rapidly with the number of modes. A tensor-train representation replaces a single large array with a sequence of smaller three-way arrays linked by indices called bond indices. The representation is useful when the bond dimensions stay small: it can encode a large tensor with far fewer stored numbers than its dense form.

The central question is how these bond dimensions relate to the tensor itself. They are not arbitrary labels: for an exact representation with the smallest possible bonds, each bond dimension is the rank of a particular matrix unfolding. The sequential construction below explains both how to obtain the representation and why that rank relationship holds.

Tensor-Train Definition and Sequential Construction

A sequential construction starts with \(\mathcal{X}\) itself. At step \(k\), arrange the current residual array as a matrix whose rows index the current bond and \(i_k\), and whose columns index \(i_{k+1},\ldots,i_d\). Factor that matrix exactly as \(U_kV_k\), with the inner dimension equal to its matrix rank. Reshape \(U_k\) into the next core; treat \(V_k\) as the residual for the following step. At the final step, reshape the remaining matrix into the last core. No entries are discarded in this construction.

For relating bonds to ranks, define the prefix unfolding \(\mathcal{X}_{[k]}\) by putting \((i_1,\ldots,i_k)\) in its rows and \((i_{k+1},\ldots,i_d)\) in its columns. Use lexicographic order within each group. Thus its dimensions are \((\prod_{j=1}^k I_j)\times(\prod_{j=k+1}^d I_j)\). Changing a consistent ordering only permutes rows or columns and does not change matrix rank.

Unfolding Ranks Are the Minimal Bond Dimensions

Proof. In any tensor train, group the first \(k\) cores and their contracted bond indices into a matrix \(L_k\), with rows indexed by \((i_1,\ldots,i_k)\) and columns by \(a_k\). Group the remaining cores into a matrix \(R_k\), with rows indexed by \(a_k\) and columns by \((i_{k+1},\ldots,i_d)\). The entry formula for the tensor gives

The product has inner dimension \(r_k\), so its rank cannot exceed \(r_k\). This proves the lower bound for every representation.

For attainment, perform the sequential construction using exact rank factorizations. At step \(k\), let \(M_k\) be the matrix made from the current residual, with rows indexed by \((a_{k-1},i_k)\) and columns by the remaining modes. Maintain a matrix \(L_{k-1}\) with \(r_{k-1}\) linearly independent columns such that the prefix unfolding through mode \(k-1\) equals \(L_{k-1}\) times the residual. Initially \(L_0\) is the scalar \(1\), so this property holds before the first step.

When the residual is unfolded to form \(M_k\), the prefix unfolding through mode \(k\) is \(Q_kM_k\), where \(Q_k\) maps each pair \((a_{k-1},i_k)\) to the corresponding prefix rows using \(L_{k-1}\). Up to a permutation from the chosen index order, this map applies \(L_{k-1}\) separately for each \(i_k\). Since \(L_{k-1}\) has linearly independent columns, \(Q_k\) does too. Left multiplication by a matrix with linearly independent columns preserves the rank of \(M_k\): it is an injective map on its column space. Consequently,

Factor \(M_k=U_kV_k\) with inner dimension \(\operatorname{rank}(M_k)\), using a rank factorization in which \(U_k\) has linearly independent columns. Reshape \(U_k\) as the next core. Multiplying \(L_{k-1}\) through this reshaped core gives the new prefix factor \(L_k\); it has linearly independent columns because both the previous map and the new factor are injective. This establishes the maintained property for the next step. Repeating through mode \(d-1\), then placing the residual in the final core, gives an exact representation with \(r_k=\operatorname{rank}(\mathcal{X}_{[k]})\) at every cut. Together with the lower bound, this proves the claim. \(\square\)

Storage Cost and When the Representation Helps

A core \(G^{(k)}\) contains \(r_{k-1}I_kr_k\) entries. Counting all core entries gives the nominal storage requirement

This count is a direct consequence of the core dimensions; it does not require the entries to be independent parameters. The dense tensor has \(N_{\mathrm{dense}}=\prod_{k=1}^d I_k\) entries. A tensor train saves storage when the sum of core sizes is smaller than that product. Small unfolding ranks can make this happen, but a tensor-train representation is not automatically compressed.

Rank Constraints and a Common Pitfall

For any tensor, the unfolding dimensions imply

for minimal exact bonds. These bounds are necessary, but they do not mean one can assign arbitrary bond dimensions independently and obtain a representation of a given tensor. The unfolding ranks must be calculated from that tensor. A large bond can always be redundant in a nonminimal representation; an exact minimal representation uses the ranks above.

• Mistake: assuming that every tensor-train representation has bond dimensions equal to unfolding ranks. Any representation has bonds at least as large as those ranks; equality characterizes the minimal possible bonds.
• Correction: factor each sequential residual at its actual matrix rank. The theorem shows that this produces the minimal bond at each cut.
• Mistake: assuming that replacing a dense tensor by cores necessarily reduces storage.
• Correction: count \(\sum_k r_{k-1}I_kr_k\) and compare it with \(\prod_k I_k\). For small tensors or large bonds, the core count can exceed the dense count.

The rank structure matters because it identifies which separations of the modes admit compact representations. Sequential factorization exposes these separations one cut at a time, and the unfolding ranks quantify the dimensions needed to carry information across each cut. For a fixed tensor, those ranks provide the exact minimal bond sizes; the storage formula then tells whether that structure is computationally useful.