Tensor-train storage and inner-product costs

Core $G_k$ contains $r_{k-1}{n}_k{r}_k$ entries, so storing all cores requires the stated sum. The corresponding dense tensor would have ${\prod }_k{n}_k$ entries; the TT formula counts its actual core storage and by itself asserts no savings unless that sum is smaller.

Set $E_0=[1]$ and recursively define $(E_k{)}_{{\alpha }_k,{\beta }_k}={\sum }_{{\alpha }_{k-1}=1}^{r_{k-1}}{\sum }_{{\beta }_{k-1}=1}^{s_{k-1}}{\sum }_{i_k=1}^{n_k}(E_{k-1}{)}_{{\alpha }_{k-1},{\beta }_{k-1}}\overline{G_k({\alpha }_{k-1},i_k,{\alpha }_k)}{H}_k({\beta }_{k-1},i_k,{\beta }_k)$. Induction on $k$ expands $E_k$ as the sum over indices $i_1,\dots ,i_k$ and bonds ${\alpha }_k,{\beta }_k$ of the conjugate prefix contraction of $A$ times the prefix contraction of $B$. At $k=d$, the terminal bonds each have size one, so this is exactly $⟨A,B{⟩}_F$ by [F1] and [F2].

At step $k$, each of the $r_k{s}_k$ output entries accumulates $n_k{r}_{k-1}{s}_{k-1}$ terms. Thus its arithmetic is bounded by a fixed constant times $n_k{r}_{k-1}{s}_{k-1}{r}_k{s}_k$. Summing over modes gives the displayed cost. The recurrence stores the previous and next environments, of sizes $r_{k-1}{s}_{k-1}$ and $r_k{s}_k$, so its additional workspace is bounded by a constant times their maximum over $k$.