Algebraic Operations on Tensor Trains

Technical Summary: Algebraic Operations on Tensor Trains

Problem Statement
High-dimensional tensors frequently arise in applications such as quantum chemistry, system identification, and dynamic programming. The exponential growth of tensor elements with respect to dimension (the "curse of dimensionality") makes storing and manipulating full tensors impractical. The Tensor Train (TT) format, also known as Matrix Product State (MPS), addresses this by representing tensors as a sequence of low-rank cores (wagons) with manageable bond dimensions.

However, performing algebraic operations on tensors already in TT format presents significant challenges. Specifically:

1. Summation: Adding multiple TTs (e.g., a Sum of Tensor Trains or SOTT) often results in a single TT with excessively large bond dimensions if converted naively.
2. Hadamard Product: The elementwise product of two TTs theoretically results in a bond dimension equal to the product of the individual bond dimensions ($B_{prod} = B_1 B_2$). For large bond dimensions (e.g., $B=1000$), the intermediate wagons become too large to store ($10^6$ elements per core, leading to $10^{12}$ total elements).
3. Matrix-Vector Product: Computing $y = Hx$ where both the operator $H$ (Matrix Product Operator, MPO) and the vector $x$ (MPS) are in TT format similarly leads to a massive expansion of bond dimensions.

Existing methods for "tensor rounding" (reducing bond dimensions) often face a tradeoff: traditional algorithms (like TT-SVD) offer high accuracy but are computationally expensive, while faster randomized or Khatri-Rao product (KRP) based methods often suffer from reduced accuracy in lossy scenarios.

Methodology
The paper proposes a generalized and improved variant of the TTSVDTT (Tensor Train SVD applied to TT) algorithm. The core methodology relies on avoiding the explicit construction of large intermediate tensors. Instead, it operates on the products of these tensors using matrix decompositions.

1. Strangulation and SVD: The approach utilizes "strangulation," where a tensor is reshaped into a matrix and decomposed via Singular Value Decomposition (SVD) to truncate the bond dimension.
2. Implicit Matrix Operations: For the TTSVDTT algorithm, instead of forming the large matrix $X_n$ (which would contain the full product tensor wagons), the algorithm computes the product $X_n X_n^T$ implicitly. It derives the left singular vectors of $X_n$ as eigenvectors of $X_n X_n^T$.
3. Cholesky Decomposition and Truncated SVD: A key innovation is decomposing the matrix $M_n = X_n X_n^T$ as $S_n S_n^T$ (e.g., via Cholesky decomposition). The algorithm then computes the desired wagon $y_n$ by performing a truncated SVD on a smaller auxiliary tensor $Y_n$ (derived from $z_n$ and $S_n$) rather than on the full $X_n$.
4. Specialized Variants: The paper extends this framework to three specific input formats without explicitly forming the full product:
   • SOTT (Sum of TTs): For a sum of $M$ trains, the algorithm exploits the block-diagonal structure of the combined wagons, storing only diagonal blocks to avoid $O(M^2)$ memory complexity.
   • Hadamard Product (TTSVDHP): For the elementwise product of two TTs, the algorithm avoids the Kronecker product of the full wagons. It utilizes the identity $\text{vec}(ABC) = (C^T \otimes A)\text{vec}(B)$ to compute products with the large Kronecker structure by multiplying with the smaller constituent matrices ($f_n$ and $g_n$) separately.
   • MPO-MPS Product (TTSVDHX): For the product $y=Hx$, the algorithm computes auxiliary tensors ($z_n, V_n, Y_n$) that are significantly smaller than the full product wagons, allowing for efficient truncation.

Key Contributions

1. Generalized TTSVDTT: The paper presents a generalization of the TTSVDTT algorithm capable of handling inputs that are not single TTs but rather sums of TTs, Hadamard products of TTs, or MPO-MPS products.
2. Memory Efficiency: The proposed algorithms (TTSVDHP and TTSVDHX) allow for the rounding of tensor products without ever evaluating the full product tensor or storing the massive intermediate arrays that would result from a naive expansion.
3. Accuracy-Speed Tradeoff: The paper introduces an alternative to the "Successive Randomized Compression" (SRC) and KRP-based rounding methods. While randomized methods are faster, the proposed TTSVDTT variants offer a better tradeoff between computational efficiency and accuracy, particularly in lossy rounding scenarios where precision is critical.
4. CPD to TT Conversion: The methodology enables the conversion of tensors from Canonical Polyadic Decomposition (CPD) format to TT format (and vice versa) without evaluating all tensor elements, by treating CPD as a special case of SOTT with bond dimension 1.

Results
Numerical experiments were conducted on synthetic data and real-world quantum chemistry problems:

• SOTT/CPD: In converting a CP model (rank 1000) to TT, the specialized TTSVDCP algorithm was competitive in speed with the fastest methods while maintaining the high accuracy of traditional TT rounding.
• Hadamard Product: In experiments involving the elementwise product of two TTs (bond dimension 20), the proposed TTSVDHP algorithm achieved fitting errors comparable to TTSVDTT and traditional rounding but was significantly faster than traditional rounding. It successfully handled higher dimensions where other methods failed due to memory constraints.
• MPO-MPS Product: In computing $y=Hx$, the TTSVDHX algorithm demonstrated nearly identical accuracy to traditional TT rounding and TTSVDTT, outperforming the SRC and KRP methods in accuracy. Its computational complexity grew at a lower rate with increasing bond dimensions compared to traditional methods.
• Quantum Chemistry Application: The algorithms were applied to minimize the quadratic form of a Hamiltonian (finding the ground state energy) for cyclic aromatic molecules (benzene, [10]annulene, [18]annulene). The TTSVDHX algorithm successfully computed minimum energies that were confirmed by the Density Matrix Renormalization Group (DMRG) algorithm, demonstrating practical viability.

Significance and Claims
The paper claims that the proposed algorithms achieve an improved tradeoff between computational efficiency and accuracy compared to state-of-the-art methods. Specifically:

• Unlike randomized or KRP-based algorithms, which can be up to 50× faster but less accurate in lossy scenarios, the proposed TTSVDTT variants maintain the high accuracy of the original TT-SVD approach while offering speed improvements.
• The algorithms solve the "memory bottleneck" problem inherent in tensor algebra (sums, Hadamard products, and matrix-vector products) by operating on compressed representations without explicit expansion.
• The work provides a robust tool for high-dimensional applications, particularly in quantum chemistry, enabling the solution of constrained quadratic optimization problems (eigenvalue problems) for large Hamiltonians that would otherwise be intractable due to memory limitations.