PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1

A. Cichocki, N. Lee, I. V. Oseledets, A. -H. Phan, Q. Zhao, D. Mandic

arXiv:1609.00893v3math.NA

TL;DR

Large, high-dimensional tensor data challenge standard analysis because their volume and complexity grow exponentially with tensor order. This monograph reviews tensor networks, especially Tucker and Tensor Train formats, and shows how they support compression and large-scale data analytics and optimization.

  • Problem

    Modern datasets have excessive volume and structural complexity, while tensor size grows exponentially with order, making scalable analysis and storage difficult.

    Source: §1.1 · p. 6, §1.3.1 · p. 16

  • Method

    The monograph provides mathematical, graphical, and interpretive guidance on tensor networks, emphasizing Tucker and Tensor Train decompositions and their applications to large-scale analytics and optimization.

    Source: Introduction and Motivation · p. 6, §1.6 · p. 23

  • Results

    Tensor networks enable super-compression of massive datasets, while Tensor Train formats provide stable quasi-optimal rank reduction with controllable approximation error.

    Source: Introduction and Motivation · p. 6, §1.4 · p. 20

  • Takeaways & Limitations

    Tensor networks offer a unified framework for analyzing linked tensor blocks and large-scale data with millions or billions of non-zero entries.

    Source: §1.6 · p. 23

    Tensor Train and hierarchical Tucker ranks can increase rapidly with tensor order or desired approximation accuracy, limiting the effectiveness of low-rank compression.

    Source: §2.5 · p. 54

Abstract

from arXiv · show

Machine learning and data mining algorithms are becoming increasingly important in analyzing large volume, multi-relational and multi--modal datasets, which are often conveniently represented as multiway arrays or tensors. It is therefore timely and valuable for the multidisciplinary research community to review tensor decompositions and tensor networks as emerging tools for large-scale data analysis and data mining. We provide the mathematical and graphical representations and interpretation of tensor networks, with the main focus on the Tucker and Tensor Train (TT) decompositions and their extensions or generalizations. Keywords: Tensor networks, Function-related tensors, CP decomposition, Tucker models, tensor train (TT) decompositions, matrix product states (MPS), matrix product operators (MPO), basic tensor operations, multiway component analysis, multilinear blind source separation, tensor completion, linear/multilinear dimensionality reduction, large-scale optimization problems, symmetric eigenvalue decomposition (EVD), PCA/SVD, huge systems of linear equations, pseudo-inverse of very large matrices, Lasso and Canonical Correlation Analysis (CCA) (This is Part 1)

Introduction and Motivation

This section presents tensor networks as compressed, scalable representations for high-dimensional and multidimensional data, introducing unified notation, graphical operations, and low-rank formats. It covers their use in multiway analysis, dimensionality reduction, latent-variable extraction, and optimization for extremely large datasets, while noting approximation errors and format-specific limitations.

Introduction and Motivation

  • The monograph unifies tensor decompositions and tensor networks as interconnected low-order cores that compress large tensors while improving interpretation and computational tractability.Representations can compress datasets with up to 10^50 entries to approximately 10^7 or fewer entries.Source: Introduction and Motivation · pp. 5–6

1.1 Challenges in Big Data Processing

  • Modern big data combines extreme volume, velocity, veracity, and variety, making standard methods inadequate for scalable, robust, near-real-time, and multimodal analysis.Tensor networks provide sparse, distributed representations for massive tensor datasets and support tensor-based representations and optimization.Source: §1.1 · pp. 6, 8

1.2 Tensor Notations and Graphical Representations

  • Tensor notation treats higher-order arrays through modes, fibers, slices, block tensors, and graphical network diagrams whose edges encode indices and operations.Diagrammatic changes visualize tensor manipulations, including multiplication and contraction, while block and hierarchical matrices can be represented as tensors.Source: §1.2 · pp. 8, 12, 14, 15

1.3.1 Curse of Dimensionality

  • The curse of dimensionality makes an Nth-order tensor with mode size I require I^N entries, causing prohibitive computational and memory demands as order increases.Low-rank tensor networks alleviate this problem through manageable core tensors and efficient decomposition algorithms, including for raw, incomplete, and noisy datasets.Source: §1.3.1 · p. 16

1.4 Separation of Variables and Tensor Formats

  • Tensor networks exploit generalized (full or partial) separability, reducing computational costs and storage requirements through low-rank approximations, which incur compression error except for very special data structures.Source: §1.4 · pp. 17–18
  • TT formats offer stable, quasi-optimal rank reduction and controllable approximation error, motivating their extensive use alongside HT and TTNS for low-rank tensor-network approximations.CP algorithms can be ill-posed at high order, while Tucker cores scale exponentially with order; tensorization also converts huge optimization problems into smaller interconnected subproblems.Source: §1.4 · pp. 20–21
  • Executing computations solely with tensor-network cores scales linearly, or sub-linearly for quantized networks, in tensor order N, reducing computational complexity and distributed-memory requirements.This scaling principle motivates tensor-network formats for large-scale analysis.Source: §1.4 · p. 21

1.5 Advantages of Multiway Analysis via Tensor Networks

  • Tensor-network formats support tractable mathematical operations and intuitive graphical representations of contractions and reshaping, while distributed representations capture complex data and optimization structures.Tensor-network operations can be performed using core tensors without explicit complex mathematical expressions.Source: §1.5 · p. 22
  • Low-rank tensor decompositions provide compressed representations, robustness to noisy or missing data, flexible constraints, and analysis of coupled blocks separating shared from independent components.These advantages support tensor-network treatment of structurally rich data and complex optimization tasks.Source: §1.5 · p. 22

1.6 Scope and Objectives

  • Tensor networks extend beyond standard Tucker and CP models to analyze coupled tensor blocks with millions or billions of non-zero entries and uncover hidden structures.The monograph positions tensor networks as a mathematical backbone for extremely large-scale data analytics.Source: §1.6 · p. 23
  • Tensor networks generalize matrix component analysis to multiway component analysis, extracting components from multidimensional and multimodal data with linear or sub-linear dataset scaling.The approach targets core relations among tensor modes while maintaining scalable computation.Source: §1.6 · p. 23
  • The monograph covers tensor-network methods for dimensionality reduction and optimization, including EVD/PCA, GEVD, SVD, linear systems, pseudo-inverses, Lasso, CCA, and PLS.These problems may involve structured matrices and vectors with over a billion entries and are reformulated as manageable constrained subproblems through tensor-network transformations.Source: §1.6 · pp. 23–24

Tensor Operations and Tensor Network Diagrams

This section introduces multilinear tensor operations and tensor-network diagrams, establishing notation, representations, and hierarchical models for high-order tensors. It also examines tensor-train and generalized network formats, including their transformations, storage and computational trade-offs, distributed architectures, and operator-based extensions.

Tensor Operations and Tensor Network Diagrams

  • Basic multilinear operations are defined with explicit notation and graphical illustrations, including reshaping, outer, Kronecker, Khatri–Rao, direct-sum, concatenation, convolution, and Hadamard products.The presentation avoids ambiguity from tensor reshaping by expressing operations directly in multilinear contexts and supports them with tables and figures.Source: Tensor Operations and Tensor Network… · p. 25, §2.1 · pp. 25, 33, Figure 2.1 · p. 27

2.1 Basic Multilinear Operations

  • Little-endian and big-endian multi-index conventions determine tensor element ordering, so matricization, vectorization, and Kronecker definitions must remain consistent with the chosen convention.The monograph adopts little-endian notation unless otherwise stated, consistent with Fortran and MATLAB usage.Source: §2.1 · pp. 27–28
  • Matricization unfolds a tensor into matrices, with mode-n matricization producing In rows and all remaining mode dimensions as columns, whose columns are mode-n fibers.Canonical mode-(1,2,...,n) matricization instead groups the first n modes into rows and the remaining modes into columns.Source: §2.1 · p. 28
  • The outer product builds higher-order tensors from factors, while rank-1 tensors are single outer products and CP decomposition expresses tensors as finite sums of such terms.Tensor rank is the minimum number of rank-1 terms in an exact CP decomposition; symmetric tensors admit analogous sums of symmetric rank-1 terms.Source: §2.1 · pp. 33, 36, 37
  • The best rank-R CP approximation may fail to exist, although rank-R tensors can be approximated arbitrarily well by tensors with strictly smaller CP ranks, motivating border rank.Border rank is defined as the minimum number of rank-1 tensors needed to approximate a tensor with arbitrary accuracy.Source: §2.1 · pp. 36–37
  • Mode-n tensor-times-matrix products reduce to C(n) = BA(n), enabling established matrix multiplication routines, while full multilinear products yield the Tucker format.Efficient optimized TTM algorithms remain an active development area [11].Source: §2.1 · pp. 37–39
  • Multilinear products reshape tensors, reduce their order, and support dimensionality reduction, random projections, and sketching while preserving basic tensor properties.Mode-n multiplication by a matrix preserves tensor order, whereas multiplication by vectors removes the corresponding modes.Source: §2.1 · p. 39
  • Tensor contractions generalize matrix multiplication and inner or outer products, but their high computational cost—especially in loopy networks—often necessitates approximate algorithms.Contractions may combine tensors across selected or all common modes and are generally neither associative nor commutative.Source: §2.1 · pp. 39, 41, 42

2.2 Graphical Representation of Fundamental Tensor Networks

  • Tensor networks represent high-order tensors as sparsely interconnected low-order cores, with internal edge weights encoding network rank and dangling edges representing physical modes.The number of free edges determines tensor order, while internal branches encode bond dimensions or tensor-network rank.Source: §2.2 · p. 43

2.3 Hierarchical Tucker (HT) and Tree Tensor Network State (TTNS) Models

  • Hierarchical Tucker decompositions organize modes through a binary dimension tree, distribute a large Tucker core across smaller cores, and generalize through tree tensor network states.The tree topology is chosen a priori; the linear unbalanced tree yields TT, while TTNS extends HT/TT with third-order-or-higher nodes.,,Source: §2.3 · pp. 44, 45, 49

2.4 Tensor Train (TT) Network

  • Tensor Train is a cascade-structured special case of HT whose cores encode vectors, functions, matrices, and tensors, while TT/MPS operations scale with tensor order through stored low-order cores.TT avoids choosing a binary tree, supports addition, matrix products, matrix-vector products, and Hadamard products, and generally increases TT-ranks after these operations; in physics it is MPS with open boundary conditions.Source: §2.4 · pp. 50, 52
  • Tensor-train ranks determine memory and complexity, depend on mode ordering, and motivate low-rank approximations; mutual-information ordering can optimize the cores through a three-step reordering procedure.In the worst case, TT ranks can grow to I^(N/2), making mode permutation an important representation challenge.Source: §2.4 · pp. 53–54

2.5 Tensor Networks with Cycles: PEPS, MERA and Honey-Comb Lattice (HCL)

  • MERA reduces core order, free parameters, and distributed-storage costs relative to PEPS/PEPO while modeling more complex variable interactions, at the expense of contraction complexity from cycles.PEPS/PEPO can keep ranks smaller using higher-order cores, whereas HCL and MERA provide further rank control through specialized architectures.Source: §2.5 · pp. 54–55

2.6 Concatenated (Distributed) Representation of TT Networks

  • Distributed tensor networks replace large cores with networks of smaller internal and external nodes, improving distributed storage and often reducing parameters, but loops make contraction more difficult.External nodes retain free edges associated with physical data-tensor indices, while internal nodes have no free edges.Source: §2.6 · pp. 55, 57

2.8 Changing the Structure of Tensor Networks

  • Graph representations make tensor operations and topology optimization intuitive, while transforming cyclic networks into HT/TT trees can reduce contraction complexity and improve algorithmic stability.Topology changes can also produce similar structures across diverse tensors, supporting comparison and joint analysis of interconnected data tensors.Source: §2.8 · p. 58
  • Tensor-network transformations use sequential contractions, matricization, truncated SVD, and reshaping to alter architectures, including conversions from Honey-Comb lattices or tensor chains to TT/MPS.These operations provide a general mechanism for changing network structure while preserving the represented tensor approximately.Source: §2.8 · pp. 58–59, Figure 2.24 · p. 59, Figure 2.25 · p. 60

2.9 Generalized Tensor Network Formats

  • Generalized tensor networks connect cores through outer, Kronecker, Hadamard, convolution, or nonlinear products; HOPTA flexibly approximates very high-order tensors with relatively few low-order cores.BTD and KTD encompass families including CP, nested BTD, NKTD, and TT, while Tucker and TT remain the principal prototype models for this monograph.Source: §2.9 · pp. 63–64

Constrained Tensor Decompositions: From Two-way to Multiway Component Analysis

Component analysis applies constrained matrix factorization to mixed signals to extract components with desired properties or estimate mixing matrices. It uses prior knowledge about latent-variable statistics and diversities, such as sparsity or statistical independence, to improve well-posedness and uniqueness.

Constrained Tensor Decompositions: From Two-way to Multiway Component Analysis

3.1 Constrained Low-Rank Matrix Factorizations

Constrained low-rank matrix factorizations model observed data through latent components under structural constraints, with SVD providing a central optimal approximation and tensor decompositions extending these models to multilinear data.

3.1 Constrained Low-Rank Matrix Factorizations

  • 2-way component analysis factorizes observed matrices into low-rank mixing and component factors, optionally scaled diagonally and constrained by orthogonality, sparsity, independence, nonnegativity, or smoothness.The factors represent basis vectors, latent variables, hidden sources, and residual or noise structure.Source: §3.1 · pp. 65–66
  • PCA, RPCA, ICA, NMF, SCA, and SmCA apply these factorizations to blind source separation, feature extraction, and classification, selecting constraints such as independence, sparsity, smoothness, or nonnegativity.The columns of the component matrix encode the corresponding latent components.Source: §3.1 · p. 66
  • SVD is a special factorization with orthogonal factors and nonnegative, ordered singular values; its truncated form gives the least-squares optimal low-rank matrix approximation by the Eckart–Young theorem.This makes SVD a backbone of low-rank matrix and tensor approximation.Source: §3.1 · p. 66
  • Simultaneous factorizations analyze linked data matrices through shared or interrelated constrained components, supporting group PCA/ICA and joint multi-block analysis of latent correlations, variability, and consistency [38].Efficient algorithms have emerged for sparse or functional PCA/SVD, ICA, NMF, and SCA.Source: §3.1 · p. 67
  • Tensor decompositions generalize 2-way component analysis and blind source separation to multilinear models, allowing components to combine independence, smoothness, sparsity, nonnegativity, and physical spatial, spectral, or temporal constraints.The section introduces CP and Tucker decompositions as extensions of constrained matrix factorizations.Source: §3.1 · p. 67

3.2 The CP Format

The CP decomposition represents an Nth-order tensor as a sum of rank-1 terms weighted by nonzero scaling coefficients, with tensor rank defined as the smallest exact number of terms. Its computation commonly uses least-squares or least-absolute-error optimization and ALS, while randomized, distributed, and constrained methods address scalability, conditioning, uniqueness, and interpretability.

Definition

  • CP decomposes an Nth-order tensor into a linear combination of rank-1 tensors with factor matrices and nonzero weights λ_r.The tensor rank is the smallest R for which the CP representation is exact.Source: §3.2 · pp. 67–68

Algorithms

  • CP estimation for noisy data minimizes Frobenius-norm least-squares or least-absolute-error objectives, commonly through ALS updates that optimize one factor matrix while fixing the others.ALS exploits Khatri–Rao structure, but its bottlenecks include matricized-tensor/Khatri–Rao multiplication and pseudo-inverses of R × R matrices [35,171].Source: §3.2 · pp. 68, 70
  • ALS is simple and often effective for high-SNR, well-separated, non-collinear components, whereas ill-conditioned problems require advanced Jacobian/Hessian methods and distributed implementations [35].For huge tensors, ALS or gradient descent can remain computationally expensive, motivating tensor-to-matrix reductions and randomized approaches.Source: §3.2 · pp. 70–71

Random projections

  • O(log R) random projections can preserve tensor spectral information, avoid eigen-gap dependence, and often outperform standard CP-ALS despite possible difficulties with spiky tensors [31,56].These projections transform a tensor CP problem into constrained matrix factorizations solvable by simultaneous matrix diagonalization.Source: §3.2 · pp. 71–72

Constraints and applications

  • CP is generally unique under mild conditions without extra factor constraints, while nonnegativity, orthogonality, independence, or sparsity can improve stability, accuracy, and interpretability.It is used for blind signal separation, exploratory data analysis, wireless communications, harmonic retrieval, and direction-of-arrival problems [189] [207].Source: §3.2 · p. 72

3.3 The Tucker Tensor Format

The Tucker format factorizes a tensor into a smaller core tensor and mode-specific factor matrices, with the core modeling cross-mode interactions. The section defines multilinear rank, establishes key rank and norm properties, and extends Tucker representations to efficient operations and hierarchical tensor networks.

Tucker Tensor Format

  • Tucker factorization represents an Nth-order tensor using a relatively small core tensor and factor matrices whose columns model mode-specific components and interactions.Typically, each core dimension R_n is much smaller than the corresponding tensor dimension I_n; this model is called Tucker-N.Source: §3.3 · p. 73

Multilinear Rank

  • The multilinear rank is the tuple of ranks of the tensor’s mode unfoldings, and Tucker norms can be computed in O(R^N) rather than O(I^N), with R=max{R_1,…,R_N}.Rank selection may use information criteria or dominant eigenvalues under a specified approximation accuracy or noise level.Source: §3.3 · pp. 75–76

Independent Tucker Format

  • For an independent Tucker format, the tensor’s CP rank equals the core’s CP rank, while R_1 ≤ rankCP(X) ≤ R_2R_3⋯R_N when R_1 ≤ R_2 ≤ ⋯ ≤ R_N.For symmetric tensors, the core is also symmetric and has the same CP rank; orthonormal factors additionally preserve Frobenius and Schatten p-norms.Source: §3.3 · pp. 75–76

Tucker Variants

  • The unconstrained Tucker decomposition is not unique, but constraints can reduce indeterminacies, while Tucker-(K,N) models use identity matrices for N−K factor matrices.For third-order tensors, Tucker-2 is equivalent to the TT model, and nonnegative factors and cores define NTD-2.Source: §3.3 · p. 76

Generalized Tucker Format and TTNS

  • Generalized Tucker replaces factor matrices with higher-order tensors, and its nested hierarchical form yields Tree Tensor Networks State models with potentially varying core orders.TTNS efficiency depends strongly on choosing an appropriate tree; rank-adaptive cross-approximation can seek tree structures from tensor entries without prior tree knowledge.Source: §3.3 · p. 79

Operations in the Tucker Format

  • Tucker representations support direct addition, Kronecker and Hadamard products, inner products, norms, convolution, and Fourier transforms using smaller cores and factor matrices.For low multilinear-rank tensors, applying FFTs to the factor matrices rather than the full data tensor substantially reduces computational complexity.Source: §3.3 · p. 80

3.4 Higher Order SVD (HOSVD) for Large-Scale Problems

HOSVD is an orthogonal Tucker model whose core has mutually orthogonal slices with decreasing norms analogous to matrix singular values. Truncated, randomized, sequential, and blockwise procedures enable large-scale computation, while HOSVD supports dimensionality reduction, clustering, and anomaly detection.

HOSVD structure

  • HOSVD constrains Tucker factors to be orthogonal and the core to be all-orthogonal, with slice norms acting like singular values.Core slices are mutually orthogonal, and their Frobenius norms decrease with the running index.Source: §3.4 · pp. 82, 84

Truncated HOSVD

  • Truncated HOSVD computes mode-wise singular vectors from unfolded tensors, forms the core by multilinear projection, and discards components associated with small multilinear singular values.Standard or randomized truncated SVD can be used, producing a Tucker approximation with orthogonal factors.Source: §3.4 · pp. 82, 84, 85

Large-scale computation

  • For tensors exceeding memory, divide-and-conquer partitions unfoldings into memory-sized slices, enabling sequential access and separate eigenvalue computations without loading the full matrix.Randomized SVD further reduces large low-rank matrices through random sketching and can use oversampling or multiple sketches, although slowly decaying singular values reduce accuracy.Source: §3.4 · pp. 84–85

Optimization and limitations

  • HOSVD is well-posed but quasi-best rather than optimal, so HOOI can iteratively improve the Tucker approximation using orthogonal factor updates.Sequential truncation, smaller intermediate unfoldings, MapReduce, randomized HOOI, and blockwise multilinear products provide additional scalability strategies.Source: §3.4 · pp. 85–86

Applications

  • HOSVD generalizes PCA for compression, feature extraction, classification, blind source separation, clustering, and anomaly detection by monitoring factor changes across sampled tensor blocks.It can jointly perform subspace selection and K-means clustering, while anomaly detection fixes the core and selected factors as blocks slide across the tensor.Source: §3.4 · pp. 89, 91, Figure 3.6 · p. 91

3.5 Tensor Sketching Using Tucker Model

This section presents tensor sketching as replacing huge tensors with substantially smaller approximations to enable feasible large-scale analysis, and reviews sparsification, random projections, and fiber subset selection.

Tensor Sketching Using Tucker Model

  • Tensor sketching replaces a huge tensor with one or more substantially smaller sketch tensors that approximate the original.This reduction addresses processor and memory limits that make handling entire datasets and standard all-in-one SVD algorithms infeasible.Source: §3.5 · p. 91
  • Sparsification stores tensors more efficiently by reducing nonzero entries and can accelerate multiplication by factor matrices.Element-wise sparsification zeros sufficiently small elements, retains large ones, and samples remaining elements with probabilities proportional to squared magnitudes.Source: §3.5 · p. 92
  • Random-projection sketching combines tensor fibers across selected or all modes and relates to randomized subspace embeddings for numerical linear algebra.The approach is described as randomly combining fibers of a data tensor.Source: §3.5 · p. 92
  • Fiber subset selection, or tensor cross approximation, approximates a tensor using a small subset of its fibers and generalizes matrix column/row subset selection and CUR methods.The matrix counterpart has been extensively studied with algorithms having almost matching lower bounds [64] [82].Source: §3.5 · p. 92

3.6 Tensor Sketching via Multiple Random Projections

Tensor sketching uses independent random projections to obtain much smaller mode-wise sketches of a tensor for structured low-rank approximation and large-scale multilinear applications [28]. When the tensor has sufficiently low multilinear rank, these sketches can support perfect reconstruction [28].

3.6 Tensor Sketching via Multiple Random Projections

  • The sketches are substantially smaller subtensors, enabling dimensionality reduction for structured low-rank approximation and large-scale numerical multilinear algebra and optimization [28].For a third-order tensor, examples include sizes I_1R_2R_3 and R_1R_2R_3 instead of I_1I_2I_3.Source: §3.6 · pp. 92, 95, Figure 3.7 · p. 93
  • The framework computes a full sketch and N leave-one-mode-out sketches by multiplying each tensor mode with an independent random sensing matrix Ω_n ∈ R^(R_n×I_n), where R_n < I_n.The full sketch is Z = X ×_1 Ω_1 ×_2 Ω_2 ... ×_N Ω_N, while Z_n omits projection along mode n.Source: §3.6 · p. 92
  • The test-matrix distribution trades off randomization, storage, computation, communication, numerical stability, and reconstruction-error guarantees.Gaussian and orthonormal-column projections offer strong practical performance or stability, while Rademacher variants reduce storage and computational costs; subsampled randomized Fourier transforms use randomized diagonal, transform, and sampling factors.Source: §3.6 · pp. 92, 94
  • Low-multilinear-rank tensors can be reconstructed perfectly from mode-wise sketch tensors formed by random projections [28].For a third-order tensor, sketches may reduce one or more modes from I_n to R_n, with R_n < I_n; reconstruction is possible when the multilinear rank is below (R_1, R_2, ..., R_N).Source: §3.6 · p. 95

3.7 Matrix/Tensor Cross-Approximation (MCA/TCA)

Matrix/tensor cross-approximation reduces large-scale data using selected rows, columns, and fibers plus a small core, exploiting low-rank redundancy. Its tensor generalization supports Tucker representations, exact reconstruction under rank conditions, and scalable approximation from limited entries or random projections.

Matrix cross-approximation

  • MCA approximates huge matrices with a few meaningful original rows and columns, reducing dimensionality and computational complexity while incurring marginal information loss.The approach assumes large datasets are highly redundant and therefore well represented by low-rank matrices.Source: §3.7 · p. 95
  • MCA decomposes X into selected-column and selected-row matrices with a small core U chosen to minimize approximation error, as illustrated in Figure 3.8.CR factorization absorbs U into either the column or row basis; optimal selections seek high statistical leverage and low error.Source: §3.7 · pp. 95–96, Figure 3.8 · p. 96
  • MCA is exact when rank(X) ≤ min{C, R}; maximum-volume intersections yield near-optimal SVD approximations, whereas finding them is exponential and greedy algorithms provide suboptimal alternatives [4,144,179,222].Using the intersection matrix W as the core avoids requiring all entries of X, unlike the globally optimal core.Source: §3.7 · p. 96

Tensor cross-approximation

  • TCA generalizes MCA by applying cross-approximation to matricized tensors or directly sampling tensor fibers for low-rank Tucker models.The Fiber Sampling Tucker Decomposition (FSTD) expresses structured low-multilinear-rank data using relatively few fibers [28].Source: §3.7 · pp. 96–97
  • For an Nth-order tensor of multilinear rank {R1, R2, …, RN}, FSTD can fully reconstruct X from fiber-built factor matrices and a core when the sampled subtensor has Pn ≥ Rn and the same rank.For third-order tensors, selected fibers form an intersection subtensor whose derived core and factors produce an exact Tucker representation.Source: §3.7 · pp. 97, 99
  • FSTD scales to very large, relatively low-order tensors, including missing fibers or entries, by sequentially selecting high-modulus entries; random projections offer an alternative using Pn ≥ Rn.The projection matrices are independent, and the approximating multilinear rank is chosen somewhat larger than the target rank for accuracy.Source: §3.7 · p. 99

3.8 Multiway Component Analysis (MWCA)

Multiway component analysis (MWCA) extends constrained component extraction to tensors through Tucker representations, allowing physically meaningful, mode-specific constraints [42]. Its Tucker-N computation reduces and matricizes each mode, applies suitable two-way analyses, computes the core tensor, and optionally fine-tunes the factors.

3.8.1 Multilinear Component Analysis Using Constrained Tucker Decomposition

  • MWCA uses constrained Tucker representations to impose different constraints across tensor modes, enabling physically meaningful components beyond unconstrained matrix factorizations.Possible constraints include orthogonality, statistical independence, sparsity, smoothness, and nonnegativity [42].Source: §3.8.1 · pp. 99–100
  • The Tucker-N MWCA procedure sequentially reduces and matricizes data in each mode, then applies potentially different two-way component-analysis or blind-source-separation algorithms and constraints.This modewise flexibility allows each unfolding matrix to use an appropriate algorithm and constraint set.Source: §3.8.1 · p. 100
  • After modewise factor extraction, the core tensor is computed, modeling complex links among components from different modes.The core can be obtained using an inversion formula involving the data tensor and factor matrices.Source: §3.8.1 · p. 100
  • An optional ALS minimization step fine-tunes the factor matrices and core tensor under the imposed constraints.The refinement minimizes a suitable Tucker reconstruction cost function subject to specific constraints.Source: §3.8.1 · p. 100

3.9 Analysis of Coupled Multi-block Matrix/Tensors – Linked Multiway Component Analysis (LMWCA)

Tensor decompositions extend blind source separation and component analysis to coupled multi-block datasets, including missing or noisy data. LMWCA jointly extracts shared and block-specific latent components and generalizes group ICA, PVD, CCA/PLS, and tensor-network analysis.

MWCA

  • Tensor decompositions extend blind source separation and matrix component analysis to multiway component analysis (MWCA).Source: §3.9 · p. 100

Population Value Decomposition

  • PVD jointly factorizes many matrices using common factors A and B with block-specific reduced matrices G^(k), while encompassing Tucker-2, CP, and RESCAL special cases.The model supports very large numbers of data matrices and can impose sparsity, nonnegativity, smoothness, or orthogonality constraints.Source: §3.9 · pp. 101–102
  • PVD/Tucker-2 applies to higher-order tensors after reshaping and optionally permuting them into skinny third-order tensors.Source: §3.9 · p. 101, Figure 3.12 · p. 102

Linked Multiway Component Analysis

  • LMWCA analyzes similarly collected multimodal blocks jointly because they may share latent components while retaining independent features.The motivating examples include EEG, MEG, and fMRI data recorded across subjects, trials, and common experimental tasks.Source: §3.9 · p. 105
  • LMWCA formulates coupled tensors as simultaneous Tucker-(1,N) decompositions with common components shared across blocks and individual components representing block-specific processes.The number of common components is constrained by the block ranks and is generally unknown, requiring estimation.Source: §3.9 · pp. 105, 107

Extensions

  • LMWCA complements group component analysis and feature extraction, extends group ICA, PVD, and CCA/PLS, and generalizes to linked tensor-train and hierarchical Tucker networks.Source: Figure 3.14 · p. 106, §3.9 · p. 107

3.10 Nonlinear Tensor Decompositions – Infinite Tucker

Infinite Tucker and Distributed Infinite Tucker extend Tucker decomposition to infinite-dimensional feature spaces through kernel and Bayesian approaches, modeling nonlinear latent-factor interactions with tensor-variate Gaussian processes. The section also presents scalable alternatives for large sparse tensors, including distributed variational inference with sparse Gaussian processes and MapReduce.

3.10 Nonlinear Tensor Decompositions – Infinite Tucker

  • Infinite Tucker and DinTucker generalize standard Tucker decomposition to infinitely dimensional feature spaces using kernel and Bayesian approaches.Source: §3.10 · p. 107
  • Kernelized covariance matrices replace standard factor-matrix covariances, enabling nonlinear interactions among latent factors in an infinite feature space through tensor-variate Gaussian processes.Source: §3.10 · p. 108
  • DinTucker improves scalability by splitting an observed noisy tensor into subtensors modeled by separate Gaussian-process models and merging their factor matrices through a similarity-controlling prior.Source: §3.10 · p. 108
  • A further nonlinear decomposition avoids explicitly or implicitly exploiting Kronecker covariance structure when full covariance matrices are prohibitively large and sparse.Source: §3.10 · p. 109
  • For tensors with millions of nonzero and billions of zero entries, distributed variational inference combines sparse Gaussian processes, MapReduce, and inducing points to reduce otherwise intractable exact inference [204,233].Source: §3.10 · p. 109

Tensor Train Decompositions: Graphical Interpretations and Algorithms … 4.4 Quantized Tensor Train (QTT) – Blessing of Dimensionality

This section presents mathematical and graphical representations, conversions, and algorithms for Tensor Train and Quantized Tensor Train formats, focusing on compact representations and operations for large tensors and matrices. It covers quantization, compressed low-rank approximations, distributed computation, and QTT-Tucker for addressing rank growth.

Tensor Train Decompositions: Graphical Interpretations and Algorithms

  • TT representations are developed in mathematical and graphical forms to support compact, understandable implementations of tensor-train operations [39].The section motivates these representations through their theoretical and practical advantages.Source: Tensor Train Decompositions: Graphical… · p. 110

4.1 Tensor Train Decomposition – Matrix Product State

  • An Nth-order tensor train/MPS representation has equivalent forms, including contraction of 3rd-order cores and vector forms expressed through Kronecker products of fibers or block matrices.The cores G(n) have dimensions Rn−1 × In × Rn for n = 1, 2, …, N, with boundary ranks R0 = RN = 1.Source: §4.1 · pp. 110, 115

4.2 Matrix TT Decomposition – Matrix Product Operator

  • Matrix TT/MPO reshapes a huge matrix into a 2N-th-order tensor and represents it with 4th-order cores, equivalently forming a vector TT after merging each index pair (in, jn).Strong Kronecker products of block matrices allow operations to be performed without explicitly constructing core tensors.Source: §4.2 · pp. 116, 117, 121
  • TT/MPO compression relies on low-rank unfolding matrices, so it works well for many structured matrices but is not generally guaranteed when their singular values do not rapidly decay.The representation compresses linked block matrices rather than applying a global standard low-rank matrix approximation.Source: §4.2 · p. 121

4.3 Links Between CP, BTD Formats and TT/TC Formats

  • Any specific tensor-network format can be converted into TT; CP converts to TT/MPS with diagonal lateral slices, while BTD converts to TT/MPO with repeated TT ranks and block diagonal matrices.Source: §4.3 · pp. 121, 123

4.4 Quantized Tensor Train (QTT) – Blessing of Dimensionality

  • Quantization reshapes vectors, matrices, or lower-order tensors into higher-order tensors with mode sizes typically 2, 3, or 4, enabling high-compression low-rank tensor-network approximations.This reshaping is distinguished from general tensorization by the very small mode sizes used in quantization.Source: §4.4 · p. 124
  • QTT quantizes modes into many small virtual modes, applying TT decomposition to obtain a higher-order low-rank representation of huge vectors and tensors.For binary quantization, an Nth-order tensor with mode sizes 2^K1,...,2^KN becomes order K1+...+KN with the same number of elements.Source: §4.4 · p. 125
  • QTT ranks are usually below 20 and nearly independent of data size, reducing storage from O(I^N) to O(NR^2 log_q(I)) through super-compression.Table 4.4 compares storage complexities across tensor formats for an Nth-order tensor.Source: §4.4 · p. 126, Table 4.4 · p. 126
  • QTT exposes deep data structure through virtual dimensions, with high compressibility arising from improved separability of the quantized tensor.Compared with unquantized TT, QTT can represent highly structured data more compactly.Source: §4.4 · pp. 126, 129
  • Moderate or low QTT ranks support efficient multilinear algebra and big-data analytics, including eigenanalysis, fast Fourier transforms, and huge linear-system solution.These benefits rely on well-posed low-rank TT approximations and have been used in very large-scale scientific-computing problems [70].Source: §4.4 · p. 129
  • QTT ranks can grow dramatically with data size as approximation accuracy increases, motivating QTT-Tucker, which represents both Tucker cores and factor matrices in TT form.QTT-Tucker supports distributed computation, often yields bounded ranks, and helps avoid the curse of dimensionality.Source: Figure 4.8 · p. 128, §4.4 · p. 129

4.5 Basic Operations in TT Formats

TT formats enable efficient large-scale tensor operations by manipulating relatively small core tensors instead of raw tensor entries. The section covers arithmetic, products, transforms, inner products, and matrix applications, including TT formulations for Ax and AX.

4.5 Basic Operations in TT Formats

  • Basic TT operations—including addition, inner products, norms, Hadamard and Kronecker products, and matrix multiplications—use block matrices of relatively small cores.These operations are performed directly in TT formats for large tensors.Source: §4.5 · p. 129
  • Tensor addition preserves a compact core-level construction, with the resulting TT rank equal to rZ = rX + rY.The sum is expressed through lateral slices of the resulting TT cores, including specialized border-core forms.Source: §4.5 · p. 130
  • The Hadamard product raises TT ranks to at most Rn ˜Rn while reducing complexity from O(IN) to O(IN(R ˜R)2).The element-wise product is formed by combining corresponding core slices for tensors with matching order and size.Source: §4.5 · p. 130
  • Fourier, wavelet, DCT, and related linear transformations can be applied to small TT cores, yielding super fast transforms when the tensor has a low-rank TT approximation.The same core-wise strategy also supports N-dimensional convolution in TT format.Source: §4.5 · pp. 130–131
  • Inner products can be computed by sequentially contracting small core matrices, reducing complexity from raw-format O(IN) to O(NI(R2 ˜R + R ˜R2)).The contractions move TT cores from left to right and accumulate intermediate matrices.Source: §4.5 · p. 131

P2 P1 Pn Pn-1 A{ A( ) N A( ) n A(2) A(1)

  • Matrix-by-vector multiplication Ax = y is realized core-wise through the C product, with output TT ranks satisfying Qn = Pn Rn.The construction represents matrices and vectors in tensorized or strong-Kronecker block forms.Source: §4.5 · pp. 132–133

Y – AX, (4.32)

4.6 Algorithms for TT Decompositions … 4.10 Orthogonalization of Tensor Train Network

These sections present efficient TT-decomposition algorithms based on low-rank factorizations, sequential SVD/LRMF, or Tucker-2/PVD, then address rank control through rounding and orthogonalization. Together, they support accurate, scalable manipulation of TT representations while managing computational complexity.

4.6 Algorithms for TT Decompositions

  • TT decompositions admit efficient exact or prescribed-accuracy approximate algorithms, primarily based on low-rank matrix factorizations or constrained Tucker-2 decompositions.The TT framework also supports matrix-by-vector products directly in TT format and provides a quasi-best approximation property for TT-SVD.Source: §4.6 · pp. 138–139

4.7 Sequential SVD/LRMF Algorithms

  • TT-SVD sequentially applies truncated SVD to unfolding matrices, reshaping factors into successive TT-cores; alternative LRMF methods, including randomized SVD, can replace SVD.The procedure extracts cores recursively for tensors of arbitrary order, while TT-Cross-Approximation uses adaptive cross-approximation and has complexity linear in tensor order N.Source: §4.7 · pp. 139–141, Figure 4.12 · p. 140

4.8 Tucker-2/PVD Algorithms for Large-scale TT Decompositions

  • Tucker-2/PVD algorithms reshape an Nth-order tensor into third-order tensors, extract the first and last TT-cores, and recursively continue on reshaped intermediate tensors.The recursive procedure can use efficient Tucker-2/PVD or nonnegative Tucker-2 algorithms, while LRMF variants such as CUR and RPCA provide approximate core extraction.Source: §4.8 · pp. 141, 143

4.9 Tensor Train Rounding – TT Recompression

  • TT rounding is necessary because TT operations can increase ranks beyond computationally tractable levels; it recompresses cores to meet a prescribed tolerance or maximum-rank bound.The rounded tensor satisfies the stated Frobenius-error condition relative to the input tolerance and norm.Source: §4.9 · pp. 143–144
  • TT rounding is mathematically equivalent to TT-SVD but more efficient in TT format, using QR/SVD on small matricized cores to obtain minimum possible TT-ranks.Its complexity is O(NIR^3), because SVDs are computed only for relatively small core matrices.Source: §4.9 · p. 144

4.10 Orthogonalization of Tensor Train Network

  • Recursive QR and LQ decompositions efficiently produce left-, right-, or n-orthogonal TT networks, with cores on opposite sides orthogonalized around the selected core.Orthogonalization is described as essential for many TT algorithms [67,70,97,120,158,196,197].Source: §4.10 · pp. 145–146
  • Orthogonalization divides a TT network into sub-trains and interface matrices, defining n-orthogonality through orthonormal left and right interface structures.Left-orthogonal and right-orthogonal forms correspond to n = N and n = 1, respectively.Source: §4.10 · p. 145

L P RRm´1ImˆRm

The section describes TT-core orthogonalization and introduces ASCU, which sequentially optimizes individual cores while maintaining orthogonality and controlling TT-ranks. ASCU uses tensor contractions and Tucker-2 or truncated-SVD updates, with two-sided and one-sided rank-adjustment variants.

L P RRm´1ImˆRm

  • The preceding orthogonalization procedure replaces TT cores through QR decompositions to return left-orthogonal and right-orthogonal cores satisfying identity-Gram conditions.Left orthogonalization is applied for m = 1, 2, . . . , n − 1, and right orthogonalization for m = N, N − 1, . . . , n + 1.Source: L P RRm´1ImˆRm · p. 146

4.11 Improved TT Decomposition Algorithm – Alternating Single Core Update (ASCU)

  • ASCU sequentially optimizes one TT core while keeping the others fixed, updating two cores at a time through adjacent-core adjustment.The method proceeds in alternating left-to-right and right-to-left sweeps until a stopping criterion is met.Source: §4.11 · pp. 146, 149, 151
  • Each core update contracts the data tensor with all other TT cores, then solves a minimum-TT-rank Tucker-2 problem subject to left- and right-orthogonality constraints.The contracted tensor is efficiently formed from left and right contractions, while orthogonal factor matrices are embedded back into adjacent TT cores.Source: §4.11 · pp. 147–148, Figure 4.14 · p. 148
  • One-sided rank adjustment reduces the update to a truncated SVD of a matricized contracted tensor, whereas two-sided adjustment uses constrained Tucker-2 decomposition.The update order determines whether the left or right TT rank is changed, and the neighboring core is adjusted accordingly.Source: §4.11 · pp. 149–151
  • ASCU can be implemented more efficiently when the input tensor is already in TT format, and detailed implementations and variants are provided in.The stated use case is a TT representation whose ranks are non-optimal for the prescribed accuracy.Source: §4.11 · p. 151

Discussion and Conclusions

Part 1 presents tensor networks as compression-based tools for dimensionality reduction and extreme-scale multidimensional data analysis, while Part 2 extends them to scalable distributed optimization. Together, the monograph positions tensor networks as a bridge from numerical linear algebra to multilinear algebra for prohibitively large modern datasets.

Discussion and Conclusions

  • Tensor networks support linear and multilinear dimensionality reduction through intrinsic distributed compression, with applications spanning regression, compressed sensing, source separation, coding, feature extraction, classification, clustering, and data fusion.These applications target extreme-scale multidimensional data.Source: Discussion and Conclusions · p. 152
  • TNs model strong and weak couplings among multiple variables and accommodate multimodal, incomplete, and noisy data beyond the flat two-dimensional matrix view.Their mathematical backbone is multilinear algebra.Source: Discussion and Conclusions · p. 152
  • A scalable distributed framework transforms huge optimization problems into linked small-scale subproblems, enabling efficient standard numerical algorithms to solve them locally.This makes tensor networks a bridge between small-scale and very large-scale optimization paradigms.Source: Discussion and Conclusions · p. 152
  • Because tensors arise directly or through tensorization in modern applications, the monograph offers a foundation for machine learning on data with otherwise prohibitive volume, variety, or veracity.The authors also aim to support a seamless progression from numerical linear algebra to numerical multilinear algebra.Source: Discussion and Conclusions · pp. 152–153

Related papers

Loading 1609.00893v3…