PaperlayerView exact revision on arXiv

Source-linked AI summary

Era of Big Data Processing: A New Approach via Tensor Networks and Tensor Decompositions

Andrzej Cichocki

arXiv:1403.2048v4cs.ET

TL;DR

The paper addresses how to process massive, multidimensional, multimodal, and coupled datasets when standard approaches do not readily scale or capture their structure. It develops and surveys tensor decompositions and tensor networks as low-rank, multiway representations with scalable algorithms and applications. The paper presents these methods as enabling compression, distributed processing, and discovery of hidden multi-aspect relationships, while identifying further challenges in low-rank tensor approximation.

  • Problem

    Massive multidimensional data require scalable methods that can capture multiway relationships and process coupled datasets within tolerable elapsed times.

  • Method

    The paper develops and discusses tensor decompositions and tensor networks that represent data using factor matrices and interconnected lower-order cores, including low-rank and quantized formats.

  • Results

    Tensor networks provide strong compression and support distributed and parallel processing, with potential applications across regression, source separation, feature extraction, classification, clustering, and data assimilation.

  • Takeaways & Limitations

    Tensor networks offer a framework for analyzing large-scale multidimensional data while preserving multiway interactions and supporting tera- or even peta-byte-scale computations.

  • Takeaways & Limitations

    Many challenging problems related to low-rank tensor approximations remain to be addressed.

Abstract

from arXiv · show

Many problems in computational neuroscience, neuroinformatics, pattern/image recognition, signal processing and machine learning generate massive amounts of multidimensional data with multiple aspects and high dimensionality. Tensors (i.e., multi-way arrays) provide often a natural and compact representation for such massive multidimensional data via suitable low-rank approximations. Big data analytics require novel technologies to efficiently process huge datasets within tolerable elapsed times. Such a new emerging technology for multidimensional big data is a multiway analysis via tensor networks (TNs) and tensor decompositions (TDs) which represent tensors by sets of factor (component) matrices and lower-order (core) tensors. Dynamic tensor analysis allows us to discover meaningful hidden structures of complex data and to perform generalizations by capturing multi-linear and multi-aspect relationships. We will discuss some fundamental TN models, their mathematical and graphical descriptions and associated learning algorithms for large-scale TDs and TNs, with many potential applications including: Anomaly detection, feature extraction, classification, cluster analysis, data fusion and integration, pattern recognition, predictive modeling, regression, time series analysis and multiway component analysis. Keywords: Large-scale HOSVD, Tensor decompositions, CPD, Tucker models, Hierarchical Tucker (HT) decomposition, low-rank tensor approximations (LRA), Tensorization/Quantization, tensor train (TT/QTT) - Matrix Product States (MPS), Matrix Product Operator (MPO), DMRG, Strong Kronecker Product (SKP).

I. Introduction and Motivations

Massive, heterogeneous big data creates scalability, integration, and multiway-relationship challenges that standard matrix-based methods may not capture adequately. The paper motivates tensor decompositions and tensor networks as scalable representations and analysis tools for such data.

  • Big-data challenges: Big data combines high volume, velocity, veracity, and variety, requiring scalable, near-real-time, robust, and integrative processing methods.The motivating examples include neuroscience recordings, neuroimages, time series, genetic data, and behavior data.
  • Tensor representations: Tensor decompositions factor tensors into component matrices, while tensor networks represent higher-order tensors through interconnected lower-order tensors.These methods extend blind source separation and two-way component analysis to multiway component analysis and support dimensionality reduction and missing-data handling.
  • Research objective: The paper develops linked low-rank tensor approximations, scalable algorithms, and software for analyzing coupled tensors with millions or billions of nonzero entries.The stated objective is to identify core relations among tensor modes while scaling to extremely large datasets.
  • Scope and novelty: The paper extends prior TD reviews by connecting tensor methods explicitly to big-data processing, coupled multi-block analysis, and tensor networks.It aims to clarify the flexibility of tensor networks for discovering hidden structures in multidimensional, multimodal, and multi-block data.
  • Limits of two-way analysis: Existing matrix factorizations can be inappropriate for data with multiple couplings and cross-correlations because they provide a flattened two-way view.Higher-order models are presented as a way to capture multiple interactions rather than only pairwise relationships.
  • Basic operations: Tensor notation treats higher-order tensors as multiway arrays whose modes can encode dimensions such as space, time, frequency, trials, classes, or dictionaries.Subtensors include fibers, formed by fixing all but one index, and matrix slices, formed by fixing all but two indices; unfolding flattens tensors into matrices.

III. Tensor Networks

Tensor networks represent higher-order tensors using sparsely interconnected lower-order cores, with network structure determined by contracted and free indices. Tree networks yield hierarchical Tucker-type structures, while cyclic networks address cases where tree ranks grow rapidly.

  • Tensor-network structure: Tensor networks decompose higher-order tensors into sparsely interconnected lower-order tensors, typically matrices and third-order cores.This structure is presented as a way to alleviate or avoid the curse of dimensionality.
  • Tensor-network diagrams: Contracted edges connect tensor modes, while free edges represent uncontracted physical indices and determine the order of the entire network.Network diagrams use nodes for tensors and edges for modes, contractions, and free indices.
  • Tree networks and HT: In a tree tensor network, each edge partitions the data modes into two groups associated with a tensor matricization.A tree whose nodes have degree three or less corresponds to a Hierarchical Tucker decomposition.
  • Tree-network choices: For sixth-order tensors there are two such HT networks, whereas tenth-order tensors admit eleven possible HT decompositions.These alternatives arise from different tree organizations of the tensor modes.
  • Distributed networks: Distributed tensor networks replace large cores with internal and external cores, reducing core sizes while retaining links to physical indices.In the distributed Tucker construction, a core is replaced by lower-order sparsely interconnected cores, producing an HT network.
  • Beyond tree networks: When tree-network ranks increase rapidly with tensor order or approximation accuracy, cyclic networks such as PEPS and MERA can be used.These networks contain cycles and hierarchical structures for very high-order tensors.

IV. Basic Tensor Decompositions and their Representation via Tensor Networks Diagrams

Tensor decompositions extend constrained two-way component analysis to multidimensional data by representing tensors through factor matrices, cores, and interconnected lower-order structures. These models capture latent components and cross-mode interactions while supporting distributed representations.

  • Tensor decomposition models: Tensor decompositions factorize data into component matrices and a core tensor that models links among components across modes.The component matrices can represent latent variables, while the core can represent their mixing process or hidden multidimensional signal.
  • Tensor-network representations: Hierarchical Tucker models replace one Tucker core with sparsely interconnected lower-order cores, with only some cores directly associated with factor matrices.The resulting network distributes the representation across interconnected cores.
  • Constrained component analysis: Two-way component analysis uses constraints such as orthogonality, sparsity, independence, nonnegativity, and smoothness to identify meaningful components.These constraints encode prior knowledge about the characteristics or morphology of latent variables.
  • Interpretation and ambiguity: Matrix factorizations have an inherent symmetry that permits interchanging the roles of sources and the mixing process.The factorization can equivalently be written for the transposed data matrix, which swaps these interpretations.
  • Matrix foundations: SVD is a special factorization with orthonormal factor matrices and a diagonal matrix of nonnegative singular values.It provides explicit notions of the data matrix's range and null space for low-rank approximation.

B. The Canonical Polyadic Decomposition (CPD)

The CPD represents a tensor as a sum of rank-1 outer products, estimating factor matrices and the tensor rank. In noisy settings, it is commonly fitted with least-squares-based optimization, often using ALS and optional constraints.

  • Model definition: CPD factorizes an Nth-order tensor into a sum of rank-1 tensors formed from corresponding vectors across all modes.Its diagonal core contains the component weights, with nonzero entries only on the main diagonal.
  • Algebraic representation: In matrix form, each mode-n unfolding is expressed through its factor matrix, diagonal weights, and the Khatri-Rao product of the remaining factor matrices.This structure supports mode-wise computational updates.
  • Estimation: With noise, CPD is estimated by minimizing a least-squares or least-absolute-error cost function.The least-squares objective uses the Frobenius norm of the reconstruction residual.
  • Model definition: The CPD objective is to estimate the factor matrices and tensor rank, defined as the smallest exact number of rank-1 terms.The rank is the minimum R for which the CPD holds exactly.
  • Estimation: ALS updates factor matrices sequentially while holding the others fixed and requires pseudoinverses of small R × R matrices.The update exploits the Khatri-Rao structure after absorbing the diagonal weights into one component matrix.
  • Algorithmic conditions: ALS is attractive for simple, well-separated, non-collinear components and high signal-to-noise ratio, whereas ill-conditioned problems motivate more advanced methods.Alternative methods exploit the rank-1 structure to compute and store Jacobians and Hessians efficiently.
  • Constraints: Constraints can improve CPD accuracy, stability, and physical interpretability while relaxing uniqueness conditions when component properties are known.Examples include nonnegativity, orthogonality, statistical independence, and sparsity.

C. The Tucker Decomposition

The Tucker decomposition represents a tensor through mode-specific component matrices and a core tensor that captures interactions among their components. Its constrained and partial forms extend this representation to multiway component analysis and structured models.

  • Model definition: Tucker decomposition represents a data tensor with a core tensor multiplied by a factor matrix in each mode.The factor matrices contain mode-specific components, while the core captures their interactions.
  • Algebraic representation: Tucker's mode-n unfolding combines the mode-n factor matrix, the unfolded core, and the Kronecker product of the remaining factor matrices.This gives a matrix representation of the multilinear model.
  • Model definition: The Tucker multilinear rank is the tuple (R1, R2, . . . , RN) for which the decomposition holds exactly.Typically, each component dimension Rn is smaller than the corresponding data dimension In.
  • Relation to CPD: CPD is a special Tucker case whose core has nonzero entries only on the main diagonal, whereas Tucker is generally nonunique.Constraints on factor matrices or the core can reduce indeterminacies to column-wise permutation and scaling.
  • Structured Tucker models: Tucker-(K, N) models set N − K factor matrices to identity matrices, leaving selected modes explicitly factorized.PARALIND/CONFAC-(K, N) further uses constrained interaction matrices to define its core tensor.
  • Multiway component analysis: Constrained Tucker decompositions provide multiple sets of essential unique components with desired physical interpretation, extending two-way component analysis to multiway component analysis.The Tucker-N approach can apply different constrained component-analysis algorithms independently to each mode.
  • Multiway component analysis: In constrained Tucker analysis, either factor matrices represent latent variables and the core represents their mixing links, or the core represents a hidden multidimensional signal.The appropriate interpretation depends on the application.
  • Computation: The Tucker-N model can be computed by reducing and unfolding each mode, applying constrained component-analysis algorithms, and then estimating the core with an inversion formula.The core-estimation step illuminates complex interactions among the mode-wise components.

V. Block-wise Tensor Decompositions for Very Large-Scale Data

Very large tensors require block-wise storage and computation because their dimensions can exceed memory and make direct processing too slow. The paper presents distributed, out-of-core HOSVD strategies and low-rank subtensor methods to compute decompositions without loading full tensors.

  • Block-wise processing: Large-scale tensors are partitioned into smaller blocks so tensor operations can be performed block-wise using a suitable tensor format.Blocks can be stored on disks or distributed memory, with each block sized for the available machine memory.
  • Block-wise processing: A block-based workflow chooses a tensor representation, partitions the tensor into memory-fitting blocks, and adapts algorithms to preserve the original approximation.The blocks support random or sequential access during tensor-decomposition and tensor-network computations.
  • CPD at scale: Block-wise techniques applied to CPD can process out-of-core data while achieving high computation speed and good performance.The paper reports successful application of these techniques to CPD.
  • Large-scale HOSVD: For HOSVD, orthogonal factor matrices are obtained from SVD or truncated SVDs of unfolded mode-n matrices, followed by multilinear products that compute the core tensor.The reconstruction uses the core and factor matrices through mode-wise products.
  • Large-scale HOSVD: Partitioning an unfolding into slices allows singular-vector computations to match available memory without loading the entire matrix at once.The approach accesses the dataset sequentially and permits an effectively unbounded complementary unfolding dimension.
  • Core computation: HOSVD core computation can be organized as sequential multilinear products or accelerated through distributed matrix-by-matrix multiplication.The core is computed as G = X ×1 U(1)T ×2 U(2)T · · · ×n U(n)T.
  • Distributed computation: For very large tensors, divide-and-conquer computation partitions both data tensors and transposed factor matrices into corresponding blocks.The resulting core can be computed sequentially or in parallel from these blocks.
  • Low-rank acceleration: When multilinear rank is low, CUR-based fiber sampling identifies a smaller subtensor with the same multilinear rank, enabling HOSVD from smaller unfoldings.The sampled subtensor W has dimensions Pn satisfying Pn ≥ Rn, with Rn much smaller than In.

VII. CUR Tucker Decomposition for Dimensionality Reduction and Compression of Tensor Data

CUR-based tensor methods represent large, low-rank data using selected fibers and a smaller core, extending matrix CUR to Tucker-style decompositions. Fiber Sampling Tucker Decomposition can reconstruct suitable tensors from limited fiber access, including tensors with missing entries.

  • Matrix CUR: CUR represents large matrices through selected columns and rows plus a core chosen to minimize approximation error.The selected columns and rows are intended to provide a low-rank fit, typically with C ≪ J and R ≪ I.
  • Tensor CUR: Fiber Sampling Tucker Decomposition produces a low-rank Tucker model directly from a relatively small number of tensor fibers.The method simultaneously accounts for the linear structure in every mode and is motivated by the prevalence of good low-multilinear-rank approximations in real data.
  • Tensor CUR: Tensor CUR generalizes this idea by using factor matrices formed from fibers across all tensor modes.The factor matrices contain columns, rows, and tubes, while the core is computed from an intersection subtensor.
  • Exact reconstruction: For a tensor of low multilinear rank, exact reconstruction is possible when the selected intersection subtensor has sufficient mode-wise sizes and matching multilinear rank.The condition requires P_n ≥ R_n for every mode and the intersection subtensor to have multilinear rank {R_1, R_2, . . . , R_N}.
  • Practical computation: Sequential fiber selection based on maximum-modulus entries enables FSTD to operate with partial data access and to handle missing fibers or entries.The strategy is designed for very large-scale, relatively low-order tensors.

VIII. Analysis of Coupled Multi-Block Tensor Data – Linked Multiway Component Analysis (LMWCA)

Linked Multiway Component Analysis jointly analyzes coupled tensor blocks to identify components shared across blocks alongside distinctive components. It extends multi-block component-analysis frameworks to data with differing modalities and dimensions.

  • Constraints: Additional constraints can make common components sparse, smooth, non-negative, or orthogonal, depending on the analysis objective.With orthogonality constraints, the optimization can be transformed into a generalized eigenvalue problem and solved by the power method.
  • Data setting: LMWCA is designed for multi-modal data whose blocks may differ in dimensions except for a shared mode.The motivating examples include EEG, MEG, and fMRI data collected across subjects, trials, or tasks.
  • Model: LMWCA models multiple tensor blocks through approximate joint Tucker-(1,N) decompositions.The formulation links the blocks through their common mode while allowing block-specific tensor structure.
  • Shared and distinctive structure: The framework separates components common to all blocks from independent or uncorrelated components specific to individual blocks.Common components correspond to identical or maximally correlated components across blocks.
  • Relation to existing methods: The framework supplements group ICA, population value decomposition, and CCA/PLS by estimating common and independent components jointly across tensor blocks.Its purpose is to identify links, correlations, and variability among hidden components in multi-block data.

3 G(2) ×1 3 G(3) ×1 3 G(4) = ∑R1

Tensor Train decompositions represent high-order tensors as chains of lower-order cores, with equivalent scalar, tensor, matrix, and strong-Kronecker formulations. TT/MPO extends the chain structure to multidimensional matrices, while ALS, MALS, and DMRG provide optimization procedures.

  • Equivalent forms: TT/MPS entries can be expressed as products of slice matrices or as sums of rank-1 tensor outer products.These are equivalent representations of the same chain of cores.
  • TT/MPS structure: A Tensor Train decomposes an Nth-order tensor into 3rd-order cores and boundary factor matrices.The internal dimensions of the cores define the TT-rank tuple {R_1, R_2, . . . , R_{N−1}}.
  • Strong Kronecker form: Vectorizing the tensor allows its TT representation to be written as a strong Kronecker product of unfolded core block matrices.The strong Kronecker product contracts matching block indices across consecutive cores.
  • TT/MPO: TT/MPO represents a 2N-th-order tensor as a chain of 3rd-order and 4th-order cores, yielding a matrix after separating odd and even modes.Its unfolding matrix is expressed through strong Kronecker products of core block matrices.
  • Cross approximation: TT-Cross-Approximation interpolates a tensor using selected entries with storage and algorithmic complexity that depend linearly on tensor order.This avoids the curse of dimensionality for the interpolation procedure.
  • Algorithms: ALS optimizes one core at a time with orthogonalization, whereas MALS or DMRG jointly optimizes neighboring cores before splitting them by low-rank factorization.The two-core optimization is more expensive, but it uses a merged supercore and truncated SVD or another low-rank factorization.

X. Hierarchical Outer Product Tensor Approximation (HOPTA) and Kronecker Tensor Decompositions

HOPTA and Kronecker Tensor Decomposition organize high-order tensors through nested products and recursively decomposable component tensors. HOPTA uses relatively few cores while retaining flexibility for complex, high-order data structures.

  • Nested models: HOPTA and KTD express tensor models in nested hierarchical forms built from component tensors and Kronecker products.The Kronecker product combines equal-order tensors into a higher-dimensional tensor whose entries are pairwise products.
  • HOPTA: HOPTA generalizes Block Term Decomposition to higher-order tensors by allowing component tensors to be further decomposed with tensor networks.Its components can be recursively represented using suitable network models.
  • Model relationships: KTD can generate multiple tensor-decomposition models by changing the structures and orders of its factor tensors.Special cases include rank-1 constructions, Block Term Decomposition, and nested Kronecker decompositions.
  • Model relationships: Tensor Train decomposition appears as a particular case of nested Kronecker Tensor Decomposition.The recursive formulation can therefore generate TT decompositions within the broader KTD family.
  • Advantages: HOPTA can approximate very high-order tensors with a relatively small number of cores while modeling more complex data structures than BTD and KTD.The paper identifies this flexibility as an advantage of HOPTA over those models.

A. Curse of Dimensionality

High-order tensors suffer from exponential growth in storage, while CP representations can reduce parameter counts substantially but may become numerically unstable at high order.

  • A. Curse of Dimensionality: An Nth-order tensor with equal mode size I contains I^N elements, so storage grows exponentially with tensor order.The Tucker decomposition can also retain an exponentially scaling core tensor.
  • A. Curse of Dimensionality: CP computation reduces storage from I^N raw entries to NRI parameters, scaling linearly in N and I.This reduction effectively bypasses the curse of dimensionality when computations remain in CP format.
  • A. Curse of Dimensionality: High-order CP approximations may face numerical problems because existing algorithms are not stable in that regime.The storage advantage therefore comes with an algorithmic stability concern.

B. Quantized Tensor Networks

Quantized tensor networks reshape large vectors, matrices, and tensors into many small virtual modes, then compress them with low-rank tensor-network decompositions. QTT and related formats provide highly compressed, distributed representations whose ranks are often moderate, while QTT-Tucker addresses rank growth by tensor-train representations of both cores and factor matrices.

  • B. Quantized Tensor Networks: Quantized tensor networks represent very high-order tensors through sparsely interconnected low-order cores and tensor contractions.The approach yields efficient, highly compressed low-rank data-tensor representations.
  • B. Quantized Tensor Networks: Tensorization reshapes lower-order data into higher-order tensors so suitable tensor decompositions can achieve super-compression.Very large vectors or matrices can first be tensorized and then compressed with TT decomposition.
  • B. Quantized Tensor Networks: A vector of size I = 2^K can be reshaped into an order-K tensor with mode size 2, which often admits low-rank approximations.The resulting tensor-network representation preserves the number of elements while exposing low-rank structure.
  • B. Quantized Tensor Networks: Quantizing each mode replaces a physical dimension I_n = q^K_n with K_n virtual modes of small size q.Fine quantization such as q = 2, 3, or 4 creates many virtual modes for low-rank approximation.
  • B. Quantized Tensor Networks: QTT applies TT decomposition to quantized tensors and typically uses ranks below 10, with storage often scaling logarithmically in the original dimension.The cited super-compression reduces storage as O(I^N) → O(N log_q(I)).
  • B. Quantized Tensor Networks: Compared with unquantized TT, QTT can capture deeper structure through virtual dimensions when the quantized tensor has suitable separability.Its compressibility is attributed to separability properties introduced by quantization.
  • B. Quantized Tensor Networks: TT/QTT low-rank problems are well-posed, supporting efficient multilinear algebra, while their ranks are often constant, linearly growing in N, or logarithmically growing in I.The rank behavior is important for big-data analytics but has been addressed mostly experimentally.
  • B. Quantized Tensor Networks: QTT-Tucker represents both the Tucker core and large factor matrices as tensor trains, enabling distributed computing and often bounded ranks.The format was developed to address cases where TT or QTT ranks grow substantially with approximation accuracy.

XII. Conclusions and Future Directions

Tensor decompositions and tensor networks offer compressed, flexible, distributed approaches for analyzing massive multidimensional data, while coupled networks extend analysis across datasets. The field still requires advances in computation, interpretability, rank estimation, uniqueness, storage, and visualization.

  • Tensor networks support strong compression, distributed and parallel processing, and potential tera- or peta-byte scaling with fault-tolerant computations.These capabilities motivate their use for big-data analysis.
  • Low-rank tensor formats provide compact representations that preserve spatio-temporal and spectral dependencies in structurally rich data.
  • Multiway analysis can establish statistical links among cores, factors, components, or latent variables across data blocks.
  • Low-rank tensor and matrix approximations can accommodate noisy, incomplete, and missing data while extending component analysis to multidimensional settings with diverse constraints.
  • Coupling several tensor networks operating on different datasets creates an additional research area for linked multi-dataset analysis.
  • Open challenges include more efficient iterative algorithms, meaningful core constraints, reliable rank estimation under noise and outliers, uniqueness analysis, distributed ultra-large-scale processing, and visualization.
Loading 1403.2048v4…