Tensor train compression and truncation error

Fix a field $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, an integer $d\ge 2$, and positive integers $n_1,\dots ,n_d$. A finite order-$d$ tensor of shape $(n_1,\dots ,n_d)$ is an array $A=(A_{i_1,\dots ,i_d})$ indexed by $1\le i_k\le n_k$. Its Frobenius inner product and norm are $⟨A,B{⟩}_F={\sum }_{i_1=1}^{n_1}\cdots {\sum }_{i_d=1}^{n_d}\overline{A_{i_1,\dots ,i_d}}{B}_{i_1,\dots ,i_d},\mathrm{\parallel }A{\mathrm{\parallel }}_F=\sqrt{⟨A,A{⟩}_F}\mathrm{.}$ For a matrix, rank means the dimension of its column image and the Frobenius inner product is the same entrywise formula. The adjoint $M^{\ast }$ is conjugate transpose (transpose over $\mathbb{R}$).

For $1\le k\le d$, the mode-$k$ unfolding $A_{(k)}$ has $n_k$ rows and ${\prod }_{j\mathrm{\ne }k}{n}_j$ columns. Its row index is $i_k$ and its column index is the remaining tuple in increasing mode order, lexicographically ordered. Its entry at that row and column is the corresponding entry of $A$. For $1\le k<d$, the cut-$k$ unfolding $A^{⟨k⟩}$ has row tuple $(i_1,\dots ,i_k)$ and column tuple $(i_{k+1},\dots ,i_d)$, each lexicographically ordered. These conventions fix all reshapes used below.

For tensors $A,B$ of the same finite shape, every mode unfolding and every cut unfolding preserves the Frobenius inner product and norm.

For a tensor $A\in {\mathbb{F}}^{n_1\times \cdots \times n_d}$, its multilinear rank is $\mathrm{mlrank}(A)=(\mathrm{rank}{A}_{(1)},\dots ,\mathrm{rank}{A}_{(d)})\mathrm{.}$ If $U\in {\mathbb{F}}^{m\times n_k}$, the mode-$k$ product $A{\times }_{k}U$ is the tensor with mode-$k$ size $m$ and entries $(A{\times }_{k}U{)}_{i_1,\dots ,i_{k-1},j,i_{k+1},\dots ,i_d}={\sum }_{i_k=1}^{n_k}{A}_{i_1,\dots ,i_d}{U}_{j,i_k}\mathrm{.}$ The product is bilinear in the entries; no conjugation is used in this tensor contraction.

A Tucker representation with mode ranks bounded by $r=(r_1,\dots ,r_d)$ is a factorization $A=G{\times }_1{U}_1{\times }_2\cdots {\times }_d{U}_d,$ where $U_k\in {\mathbb{F}}^{n_k\times r_k}$ and $G\in {\mathbb{F}}^{r_1\times \cdots \times r_d}$. Separately, write ${\mathcal{T}}_r=\{B\in {\mathbb{F}}^{n_1\times \cdots \times n_d}:\mathrm{rank}{B}_{(k)}\le r_k\text{ for each }k\}$ for the multilinear-rank-bounded set used in approximation statements.

Let $A\in {\mathbb{F}}^{n_1\times \cdots \times n_d}$ with $d\ge 2$. A tensor-train (TT) representation consists of integers $r_0=r_d=1$, internal bond sizes $r_1,\dots ,r_{d-1}\in {\mathbb{N}}_0$, and cores $G_k\in {\mathbb{F}}^{r_{k-1}\times n_k\times r_k}(1\le k\le d)$ such that $A_{i_1,\dots ,i_d}={\sum }_{{\alpha }_1=1}^{r_1}\cdots {\sum }_{{\alpha }_{d-1}=1}^{r_{d-1}}{G}_1(1,i_1,{\alpha }_1)G_2({\alpha }_1,i_2,{\alpha }_2)\cdots G_d({\alpha }_{d-1},i_d,1)\mathrm{.}$ An empty bond index set gives an empty sum, hence the zero tensor; in particular, all internal bond sizes zero represent zero. A bond size $r_k$ is the storage dimension contracted between cores $k$ and $k+1$. The cut-$k$ unfolding groups modes $1,\dots ,k$ against $k+1,\dots ,d$ as fixed in Finite tensor arrays and the Frobenius inner product.

For an internal bond $k$, an invertible matrix $S\in {\mathbb{F}}^{r_k\times r_k}$ gives a gauge transformation by replacing the two adjacent cores with ${\tilde{G}}_k(\alpha ,i,\beta )={\sum }_{\gamma =1}^{r_k}{G}_k(\alpha ,i,\gamma )S_{\gamma \beta },{\tilde{G}}_{k+1}(\beta ,j,\eta )={\sum }_{\gamma =1}^{r_k}(S^{-1}{)}_{\beta \gamma }{G}_{k+1}(\gamma ,j,\eta )\mathrm{.}$ Their contraction is unchanged because ${\sum }_{\beta }{S}_{\gamma \beta }(S^{-1}{)}_{\beta {\gamma }^{\mathrm{\prime }}}={\delta }_{\gamma ,{\gamma }^{\mathrm{\prime }}}$.

The left matricization of core $G_k$ has row index $({\alpha }_{k-1},i_k)$ and column index ${\alpha }_k$. The core is left-isometric if this matrix $L_k$ satisfies $L_k^{\ast }{L}_k=I_{r_k}$. The right matricization has row index ${\alpha }_{k-1}$ and column index $(i_k,{\alpha }_k)$; the core is right-isometric if its matrix $R_k$ satisfies $R_k{R}_k^{\ast }=I_{r_{k-1}}$. A TT is in mixed canonical gauge about core $\mathrm{\ell }$ when cores $k<\mathrm{\ell }$ are left-isometric and cores $k>\mathrm{\ell }$ are right-isometric.

The diagram shows the order-three pattern. Each box is one core, each horizontal wire is a bond index summed over in the entry formula, and each vertical leg is a free physical index. Thus leaving the physical legs open and contracting the two bond wires denotes exactly the core product defining $A_{i_1,i_2,i_3}$; the diagram is only a notation for that finite sum.

For $A\in {\mathbb{F}}^{n_1\times \cdots \times n_d}$, its canonical polyadic rank (CP rank) is the least integer $R\ge 0$ for which $A={\sum }_{q=1}^R{a}_q^{(1)}\otimes \cdots \otimes a_q^{(d)},a_q^{(k)}\in {\mathbb{F}}^{n_k}\mathrm{.}$ The empty sum is zero, so the zero tensor has CP rank $0$. The coordinate expansion $A={\sum }_{i_1=1}^{n_1}\cdots {\sum }_{i_d=1}^{n_d}{A}_{i_1,\dots ,i_d}{e}_{i_1}^{(1)}\otimes \cdots \otimes e_{i_d}^{(d)}$ shows that the set of admissible finite integers $R$ is nonempty. The well-ordering of ${\mathbb{N}}_0$ therefore makes the least such $R$ well-defined.

Let $A\in {\mathbb{F}}^{m\times n}$, where $m,n\ge 1$, have a singular value decomposition $A={\sum }_{j=1}^q{\sigma }_j{u}_j{v}_j^{\ast },{\sigma }_1\ge \cdots \ge {\sigma }_q>0,$ where $q=\mathrm{rank}(A)$. For an integer $k\ge 0$, put $A_k={\sum }_{j=1}^{\min (k,q)}{\sigma }_j{u}_j{v}_j^{\ast },{\delta }_k^2={\sum }_{j=k+1}^q{\sigma }_j^2$ with an empty sum equal to zero. Then $\mathrm{rank}(A_k)\le k$, $\mathrm{\parallel }A-A_k{\mathrm{\parallel }}_F={\delta }_k$, and every matrix $B$ with $\mathrm{rank}(B)\le k$ satisfies $\mathrm{\parallel }A-B{\mathrm{\parallel }}_F\ge {\delta }_k$.

Let $p,r,s\ge 1$, let $M\in {\mathbb{F}}^{p\times r}$ have full column rank, and let $Y\in {\mathbb{F}}^{p\times s}$. Among all $W\in {\mathbb{F}}^{r\times s}$, the function $W\mapsto \mathrm{\parallel }Y-MW{\mathrm{\parallel }}_F$ has the unique minimizer $W_{\ast }=(M^{\ast }M{)}^{-1}{M}^{\ast }Y\mathrm{.}$

Work in exact arithmetic over $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$. The input is a tensor $A\in {\mathbb{F}}^{n_1\times \cdots \times n_d}$ with $d\ge 2$, and exactly one of:

• rank caps $c_1,\dots ,c_{d-1}\in {\mathbb{N}}_0$; or
• absolute tail tolerances ${\tau }_1,\dots ,{\tau }_{d-1}\in [0,\mathrm{\infty })$.

At cut $k$, flatten the current remainder with rows $({\alpha }_{k-1},i_k)$ and columns $(i_{k+1},\dots ,i_d)$, where ${\alpha }_0=1$, and compute an exact compact SVD $M_k=U_k{\mathrm{\Sigma }}_k{V}_k^{\ast }$. Its positive singular values are ordered decreasingly as ${\sigma }_1,\dots ,{\sigma }_s$. Under rank caps choose $q_k=\min (c_k,s)$. Under tolerances choose the least $q_k\in \{0,\dots ,s\}$ for which ${\sum }_{j>q_k}{\sigma }_j^2\le {\tau }_k^2$. This set is nonempty because $q_k=s$ gives tail zero. Record the discarded tail ${\delta }_k={\left({\sum }_{j>q_k}{\sigma }_j^2\right)}^{1\mathrm{/}2}\mathrm{.}$

Reshape the first $q_k$ columns of $U_k$ into core $G_k$ and reshape ${\mathrm{\Sigma }}_{k,1:q_k}{V}_{k,1:q_k}^{\ast }$ as the next remainder. After cut $d-1$, reshape the remaining matrix as $G_d$. If $q_k=0$, the remainder has zero row dimension; all later ranks and tails are set to zero and the remaining cores are the corresponding empty zero arrays. Thus the zero tensor has all internal ranks zero, a cap zero returns the zero tensor, and a tolerance large enough to select $q_k=0$ does the same. The output is the TT core list and the cut tails $({\delta }_k)$. Any SVD tie at a retained cutoff may be resolved by any orthonormal choice within the tied singular subspace.

Work in exact arithmetic over $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$. The input is a valid TT core list for a tensor of order $d\ge 2$ and exactly one of rank caps $c_1,\dots ,c_{d-1}\in {\mathbb{N}}_0$ or absolute tail tolerances ${\tau }_1,\dots ,{\tau }_{d-1}\in [0,\mathrm{\infty })$.

1. Left orthogonalize without truncation. For $k=1,\dots ,d-1$, reshape core $G_k$ into a matrix with rows $({\alpha }_{k-1},i_k)$ and columns ${\alpha }_k$. Compute an exact compact SVD $M=U\mathrm{\Sigma }{V}^{\ast }$, replace $G_k$ by the reshape of $U$, and absorb $\mathrm{\Sigma }{V}^{\ast }$ into the next core along their common bond. Omitting zero singular directions is exact. The resulting cores $G_1,\dots ,G_{d-1}$ are left-isometric.

2. Truncate from right to left. For $k=d,d-1,\dots ,2$, reshape the current $G_k$ into a matrix $M_k$ with rows ${\alpha }_{k-1}$ and columns $(i_k,{\alpha }_k)$, and compute an exact compact SVD $M_k=U_k{\mathrm{\Sigma }}_k{V}_k^{\ast }$. If its positive singular values are ${\sigma }_1\ge \cdots \ge {\sigma }_s>0$, choose $q_{k-1}=\min (c_{k-1},s)$ for rank caps, or the least $q_{k-1}\in \{0,\dots ,s\}$ with ${\sum }_{j>q_{k-1}}{\sigma }_j^2\le {\tau }_{k-1}^2$ for tolerances. Record ${\delta }_{k-1}=({\sum }_{j>q_{k-1}}{\sigma }_j^2{)}^{1\mathrm{/}2}$. Replace $G_k$ by the reshape of the first $q_{k-1}$ rows of $V_k^{\ast }$ and absorb $U_{k,1:q}{\mathrm{\Sigma }}_{k,1:q}$ into the previous core.

If $q_{k-1}=0$, the represented tensor becomes zero; set all remaining internal ranks to zero and their unperformed tails to zero. If the input represents zero, return the all-zero-rank representation and zero tails immediately. The output is the rounded core list and all recorded cut tails. No finite-precision error guarantee is part of this exact-arithmetic procedure.

If a TT representation has mode sizes $n_k$ and bond sizes $r_0=r_d=1,r_1,\dots ,r_{d-1}$, its core storage is exactly ${\sum }_{k=1}^d{n}_k{r}_{k-1}{r}_k$ field entries. If $A$ and $B$ have TT cores of bond sizes $r_k$ and $s_k$, respectively, their Frobenius inner product can be computed with $O\text{\hspace{0.17em}⁣}\left({\sum }_{k=1}^d{n}_k{r}_{k-1}{s}_{k-1}{r}_k{s}_k\right)$ scalar arithmetic operations and $O({\max }_k{r}_k{s}_k)$ additional workspace entries.

Work in exact arithmetic over $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$. Given $A\in {\mathbb{F}}^{n_1\times \cdots \times n_d}$ and integer rank caps $0\le r_k\le n_k$, compute an exact SVD of each mode unfolding $A_{(k)}$. Let $U_k$ consist of the first $q_k=\min (r_k,\mathrm{rank}{A}_{(k)})$ left singular vectors, with any orthonormal choice at a tied cutoff. Define $P_k=U_k{U}_k^{\ast }$, the orthogonal projection onto their span; for $q_k=0$, set $P_k=0$.

For auxiliary cores and intermediate arrays in this procedure, allow mode sizes $m_k\ge 0$: an array of shape $(m_1,\dots ,m_d)$ is a function from ${\prod }_{k=1}^d\{1,\dots ,m_k\}$ to $\mathbb{F}$. If a mode size is zero, this is the unique empty array. Extend the mode-product entry formula of Tucker format, multilinear rank, and mode products to these arrays, taking every empty sum to be zero.

Return the factors $U_k\in {\mathbb{F}}^{n_k\times q_k}$, the core $G=A{\times }_1{U}_1^{\ast }{\times }_2\cdots {\times }_d{U}_d^{\ast }$ of shape $(q_1,\dots ,q_d)$, and reconstruction $\widehat{A}=G{\times }_1{U}_1{\times }_2\cdots {\times }_d{U}_d=A{\times }_1{P}_1{\times }_2\cdots {\times }_d{P}_d\mathrm{.}$ If any $q_k=0$, return the corresponding $n_k\times 0$ empty factor, the empty core of the stated shape, and the zero reconstruction of the original physical shape, using the same formulas and empty-sum convention. The algorithm makes no finite-precision claim.

Work in exact arithmetic over $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$. Inputs are a tensor $A\in {\mathbb{F}}^{n_1\times \cdots \times n_d}$, a proposed CP component count $R\in {\mathbb{N}}_0$, initial factor matrices $F_k\in {\mathbb{F}}^{n_k\times R}$, and a finite sweep budget $N_{\max }\in {\mathbb{N}}_0$. The objective is $\mathrm{\Phi }(F_1,\dots ,F_d)={\parallel A-{\sum }_{j=1}^R{F}_1(:,j)\otimes \cdots \otimes F_d(:,j)\parallel }_F^2\mathrm{.}$ On every exit, return the tuple $(F_1,\dots ,F_d,\widehat{A},\text{status})$, where $\widehat{A}={\sum }_{j=1}^R{F}_1(:,j)\otimes \cdots \otimes F_d(:,j)$ is evaluated from the factor matrices as they stand at that exit. If $R=0$, return the empty factor matrices, the zero model, and status “rank-zero-model” immediately. If $N_{\max }=0$, return the current factors and model with status “budget-exhausted”. Otherwise, for each of at most $N_{\max }$ sweeps, visit modes $k=1,\dots ,d$ in that order. With the other factors fixed, form $Z_k$ whose rows are indexed by all tuples $(i_{\mathrm{\ell }}{)}_{\mathrm{\ell }\mathrm{\ne }k}$ and whose column $j$ is $(Z_k{)}_{(i_{\mathrm{\ell }}{)}_{\mathrm{\ell }\mathrm{\ne }k},j}={\prod }_{\mathrm{\ell }\mathrm{\ne }k}(F_{\mathrm{\ell }}{)}_{i_{\mathrm{\ell }},j}\mathrm{.}$ The mode-$k$ unfolding model is $A_{(k)}\approx X{Z}_k^{\mathsf{T}}$. If $Z_k$ is not full column rank, halt and return the current factors and model with status “rank-deficient-design”; no factor has changed at this block. If it has full column rank, solve the equivalent adjoint problem ${\min }_{Y\in {\mathbb{F}}^{R\times n_k}}\mathrm{\parallel }{A}_{(k)}^{\ast }-\overline{Z_k}Y{\mathrm{\parallel }}_F$ and replace $F_k$ by $Y^{\ast }$. The matrix $\overline{Z_k}$ has full column rank, so the minimizer is unique by Full-column-rank matrix least squares has a unique minimizer. After each completed sweep, increment the sweep counter. Return the current factors and model with status “budget-exhausted” after the $N_{\max }$th completed sweep. This finite-budget procedure guarantees neither convergence nor a global best CP approximation.

Let $A\in {\mathbb{F}}^{n_1\times \cdots \times n_d}$, $d\ge 2$, and let $A^{⟨k⟩}$ denote its cut-$k$ unfolding. For sequential TT-SVD, let $r_k$ be its retained bond size and ${\delta }_k$ its discarded singular-value tail at cut $k$. For rounding, let the input TT represent $A$ and use the same notation for the output bond sizes and recorded tails. Then both procedures satisfy $\mathrm{\parallel }A-\widehat{A}{\mathrm{\parallel }}_F^2\le {\sum }_{k=1}^{d-1}{\delta }_k^2\mathrm{.}$ If no positive singular value is discarded, the output is exactly $A$. In full-rank TT-SVD, $r_k=\mathrm{rank}(A^{⟨k⟩})$ for every cut, and these are the minimal possible TT bond sizes among exact representations.

Let $A\in {\mathbb{F}}^{n_1\times \cdots \times n_d}$ and let $\widehat{A}$ be the truncated HOSVD with mode-rank caps $r_1,\dots ,r_d$. Then $\mathrm{\parallel }A-\widehat{A}{\mathrm{\parallel }}_F\le \sqrt{d}{\inf }_{B\in {\mathcal{T}}_r}\mathrm{\parallel }A-B{\mathrm{\parallel }}_F,$ where ${\mathcal{T}}_r$ is the set of tensors whose $k$th unfolding has rank at most $r_k$.

During budgeted CP-ALS, each successful exact block update does not increase the squared Frobenius residual. A rank-deficient-design halt leaves the factor matrices unchanged, so it leaves the objective unchanged. Consequently, the objective is nonincreasing over every sequence of completed exact block updates.