Tensor-Train Decomposition

A d-dimensional tensor X of size n₁ × n₂ × ... × n_d is approximated by d core tensors, G_k, of size r_{k-1} × n_k × r_k. The boundary ranks r₀ and r_d are equal to 1. The element of the tensor is computed as a sequence of matrix products:

X(i₁, i₂, ..., i_d) ≈ G₁[:, i₁, :] G₂[:, i₂, :] ... G_d[:, i_d, :]

• Core Tensors: Each G_k is a 3D tensor. The indices r_{k-1} and r_k are the TT-ranks, controlling the approximation accuracy and compression ratio.
• Chain Product: The approximation is a product of matrices (slices of the core tensors), forming a "train" of cores.

The primary advantage of the TT format is its ability to represent high-dimensional data with storage that scales linearly with the dimension d, rather than exponentially.

• Exponential to Linear: A full tensor requires O(n^d) storage. The TT format requires O(d n r²), where r is the maximal TT-rank and n is the typical mode size.
• Parameter Efficiency: This makes it feasible to work with tensors in dozens or even hundreds of dimensions, which are otherwise computationally intractable. It is foundational for representing high-dimensional functions, quantum states (matrix product states), and weight tensors in neural networks.

The TT-ranks r₁, ..., r_{d-1} are the key hyperparameters that govern the trade-off between representation accuracy and compression.

• Lower Ranks: Increase compression but decrease approximation fidelity.
• Higher Ranks: Improve accuracy but reduce storage savings.
• Rank Determination: Ranks can be set manually, determined adaptively via algorithms like TT-SVD, or learned during optimization. The ranks are often much smaller than the tensor mode sizes (r << n), enabling massive compression.

Many essential tensor operations can be performed directly in the compressed TT format without full reconstruction, maintaining computational efficiency.

• Addition/Subtraction: Performed by concatenating cores, which may increase ranks.
• Element-wise Multiplication (Hadamard Product): Results in a TT format with ranks equal to the product of the input ranks.
• Contraction/Inner Product: Computed efficiently via sequential matrix products along the cores.
• Rounding: A crucial algorithm (TT-rounding or TT-recompression) reduces the ranks of a TT tensor to a desired accuracy, preventing rank growth from blowing up after successive operations.

The Tensor-Train format is mathematically identical to the Matrix Product State (MPS) representation used in quantum physics and condensed matter theory.

• Bridging Fields: This equivalence allows techniques from quantum many-body physics (e.g., Density Matrix Renormalization Group - DMRG) to be applied to machine learning problems like tensor completion and optimization.
• Canonical Forms: Borrowed from MPS theory, left- and right-orthogonalized forms of TT cores simplify algorithms and improve numerical stability for operations like SVD-based rounding.

The standard algorithm for converting a full tensor into TT format is the TT-SVD (also known as the TT-decomposition algorithm).

• Process: It is a sequential algorithm that performs a series of reshapings and truncated SVDs.
  1. Reshape the tensor into a matrix.
  2. Perform a truncated SVD, keeping the top r_k singular values.
  3. The left singular vectors form one core; the remainder is reshaped for the next step.
• Quasi-Optimality: For a given set of ranks, TT-SVD provides a quasi-optimal approximation in the Frobenius norm, analogous to the Eckart–Young theorem for matrices.

Tensor rank, specifically the CP rank, is the minimum number of rank-one tensors required to exactly represent a given tensor as their sum. This is a central but computationally challenging concept in tensor factorization, analogous to matrix rank but far more complex due to the curse of dimensionality. Determining the exact rank of a tensor is an NP-hard problem.

• Key Insight: Unlike matrices, the rank of a tensor can exceed its dimensions, and different notions of rank (e.g., CP rank, Tucker rank) exist.
• Role in TT: Tensor-Train decomposition defines a different, more tractable structure (TT-rank) that controls the sizes of the core tensors, offering a practical alternative to the elusive CP rank.

Tucker decomposition is a higher-order generalization of SVD for tensors, factorizing an N-dimensional tensor into a smaller core tensor multiplied by a factor matrix along each mode. It enables multilinear dimensionality reduction.

• Core Tensor: Captures the interactions between different modes.
• Factor Matrices: Orthogonal matrices that project each mode into a lower-dimensional subspace.
• Comparison to TT: While Tucker offers a flexible core, its storage grows exponentially with order for a dense core. TT decomposition avoids this by using a chain of low-dimensional cores, providing linear scaling with tensor order.

Canonical Polyadic Decomposition (CPD), also known as PARAFAC or CANDECOMP, expresses a tensor as a sum of rank-one tensors, defined by factor matrices for each mode. It is a fundamental and widely used tensor model.

• Structure: Each component is the outer product of N vectors (one from each factor matrix).
• Advantage: Extremely parameter-efficient.
• Challenge: Determining the optimal rank is difficult, and the best rank-k approximation may not exist. Tensor-Train provides a more stable and algebraically well-defined alternative, with robust algorithms for approximation.

Higher-Order SVD (HOSVD) is a specific algorithmic procedure for computing the Tucker decomposition. It provides a multilinear generalization of the matrix SVD by performing a standard SVD on each mode's unfolding (matricization) of the tensor.

• Process: For each mode, the factor matrix is obtained from the left singular vectors of the unfolded tensor.
• Core Tensor: Formed by projecting the original tensor onto the subspace defined by the factor matrices.
• Relation to TT: HOSVD can be used as an initialization step for computing a Tensor-Train decomposition, and the TT-ranks are bounded by the ranks of the Tucker core.

Matrix Product State (MPS) is the precise equivalent of Tensor-Train decomposition in quantum physics and condensed matter theory. It represents the wavefunction of a many-body quantum system as a product of local tensors, each associated with a lattice site.

• Origin: Developed to efficiently represent entangled quantum states, avoiding the exponential Hilbert space growth.
• Identical Formalism: The mathematical structure of an MPS is identical to a TT representation. The bond dimension in MPS corresponds directly to the TT-rank.
• Cross-Pollination: Algorithms like the Density Matrix Renormalization Group (DMRG) from physics are directly applicable for optimizing Tensor-Train networks in machine learning.

Alternating Least Squares (ALS) is the dominant optimization algorithm for fitting Tensor-Train and other tensor factorizations. It works by iteratively optimizing one core tensor at a time while keeping all others fixed, reducing a large non-convex problem to a sequence of convex linear least-squares subproblems.

• Mechanism: For a fixed TT-core, the optimization objective becomes linear in the other cores.
• TT-SVD vs. TT-ALS: A quasi-optimal TT can be initialized via a sequence of SVDs (TT-SVD). TT-ALS then refines this approximation to minimize a specific loss function (e.g., reconstruction error on observed entries).
• Scalability: Enables the decomposition of massive tensors where the full data cannot be loaded into memory.