10.3 Tensor decompositions

Tensor decompositions are powerful tools for analyzing multi-dimensional data in data science and statistics. They extend matrix decompositions to higher-order tensors, allowing for the extraction of meaningful patterns and latent factors from complex datasets.

These techniques, including CP, Tucker, and Tensor-train decompositions, offer unique advantages for dimensionality reduction, anomaly detection, and multiway data analysis. Understanding tensor basics and decomposition methods is crucial for effectively applying these tools to real-world problems.

Tensor basics

• Tensors are multi-dimensional arrays that generalize vectors and matrices to higher orders
• Understanding tensor basics is crucial for effectively applying tensor decompositions in data science and statistics

Tensor definition

Top images from around the web for Tensor definition

• 

  vector analysis - Introducing new indices with tensor/index notation - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Data Science — WRD R&D Documentation View original

  Is this image relevant?

• 

  Tensor – AnthroWiki View original

  Is this image relevant?

• 

  vector analysis - Introducing new indices with tensor/index notation - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Data Science — WRD R&D Documentation View original

  Is this image relevant?

1 of 3

Top images from around the web for Tensor definition

• 

  vector analysis - Introducing new indices with tensor/index notation - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Data Science — WRD R&D Documentation View original

  Is this image relevant?

• 

  Tensor – AnthroWiki View original

  Is this image relevant?

• 

  vector analysis - Introducing new indices with tensor/index notation - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Data Science — WRD R&D Documentation View original

  Is this image relevant?

1 of 3

• A tensor is a mathematical object that extends the concept of scalars, vectors, and matrices to higher dimensions
• Scalars are 0th-order tensors, vectors are 1st-order tensors, and matrices are 2nd-order tensors
• An $N$-th order tensor is an element of the tensor product of $N$ vector spaces, each of which has its own coordinate system

Tensor order and dimensions

• The order of a tensor, also known as its way or mode, refers to the number of dimensions or indices needed to describe its elements
• For an $N$-th order tensor $\mathcal{X} \in \mathbb{R}^{I_1 \times I_2 \times \cdots \times I_N}$, the dimensions are denoted by $I_1, I_2, \ldots, I_N$
• Example: A 3rd-order tensor $\mathcal{X} \in \mathbb{R}^{3 \times 4 \times 2}$ has dimensions $I_1 = 3$, $I_2 = 4$, and $I_3 = 2$

Tensor notation and operations

• Tensors are typically denoted using calligraphic letters ($\mathcal{X}, \mathcal{Y}, \mathcal{Z}$)
• Elements of a tensor are accessed using subscripts, e.g., $x_{i_1,i_2,\ldots,i_N}$ for an $N$-th order tensor $\mathcal{X}$
• Tensor operations include addition, subtraction, multiplication by a scalar, and various forms of tensor products (Kronecker, Khatri-Rao, Hadamard)
  • Example: The Kronecker product of two matrices $\mathbf{A} \in \mathbb{R}^{I \times J}$ and $\mathbf{B} \in \mathbb{R}^{K \times L}$ results in a 4th-order tensor $\mathcal{X} \in \mathbb{R}^{I \times K \times J \times L}$

Tensor decomposition overview

• Tensor decompositions are powerful tools for analyzing and simplifying complex multi-dimensional data
• They extend the concept of matrix decompositions to higher-order tensors, enabling a wide range of applications in data science and statistics

Motivation for tensor decompositions

• Many real-world datasets are naturally represented as tensors, such as multi-way arrays or higher-order moments
• Tensor decompositions allow for the extraction of meaningful patterns, latent factors, and low-dimensional representations from these datasets
• They can help in noise reduction, data compression, and uncovering hidden structures in the data

Applications in data science and statistics

• Multiway data analysis: Tensor decompositions enable the joint analysis of multiple data sources or modalities (e.g., EEG signals, fMRI data, social networks)
• Dimensionality reduction: Tensor decompositions can be used to find low-dimensional representations of high-dimensional tensor data
• Tensor regression and classification: Decompositions can be employed to develop predictive models for tensor-valued inputs or outputs
• Anomaly detection: Tensor decompositions can identify unusual patterns or outliers in multi-dimensional data

Comparison vs matrix decompositions

• Matrix decompositions (SVD, PCA, NMF) are widely used for two-way data, but they cannot directly capture higher-order interactions
• Tensor decompositions extend matrix decompositions to handle multi-way data, preserving the intrinsic structure and dependencies
• Some tensor decompositions (CP, Tucker) can be seen as higher-order generalizations of matrix decompositions (SVD, PCA)

CP decomposition

• The CP (CANDECOMP/PARAFAC) decomposition is one of the most fundamental and widely used tensor decompositions
• It expresses a tensor as a sum of rank-one tensors, providing a compact and interpretable representation

CP decomposition definition

• Given an $N$-th order tensor $\mathcal{X} \in \mathbb{R}^{I_1 \times I_2 \times \cdots \times I_N}$, the CP decomposition factorizes it into a sum of $R$ rank-one tensors: $\mathcal{X} \approx \sum_{r=1}^R \lambda_r \mathbf{a}_r^{(1)} \circ \mathbf{a}_r^{(2)} \circ \cdots \circ \mathbf{a}_r^{(N)}$
• $\lambda_r$ are scalar weights, $\mathbf{a}_r^{(n)} \in \mathbb{R}^{I_n}$ are factor vectors, and $\circ$ denotes the outer product

CP rank and low-rank approximation

• The CP rank of a tensor is the minimum number of rank-one tensors needed to express it exactly
• In practice, the CP decomposition is often used to find a low-rank approximation of a tensor, where $R$ is chosen to balance accuracy and complexity
• Low-rank CP approximations can reveal underlying patterns and reduce noise in the data

Computing the CP decomposition

• The CP decomposition is typically computed by minimizing the Frobenius norm of the difference between the original tensor and its CP approximation: $\min_{\lambda_r, \mathbf{A}^{(n)}} \|\mathcal{X} - \sum_{r=1}^R \lambda_r \mathbf{a}_r^{(1)} \circ \mathbf{a}_r^{(2)} \circ \cdots \circ \mathbf{a}_r^{(N)}\|_F^2$
• This optimization problem is non-convex, but effective algorithms exist for finding good approximate solutions

CP decomposition algorithms

• Alternating least squares (ALS): Iteratively updates each factor matrix while keeping the others fixed
• Gradient-based methods: Use first-order (e.g., stochastic gradient descent) or second-order (e.g., Newton, quasi-Newton) optimization techniques
• Tensor power method: Generalizes the matrix power method to tensors, iteratively updating the factor vectors
• Randomized algorithms: Employ random projections or sampling to reduce computational complexity

Tucker decomposition

• The Tucker decomposition is another fundamental tensor decomposition that generalizes the CP decomposition
• It expresses a tensor as a core tensor multiplied by factor matrices along each mode, providing a more flexible and expressive representation

Tucker decomposition definition

• Given an $N$-th order tensor $\mathcal{X} \in \mathbb{R}^{I_1 \times I_2 \times \cdots \times I_N}$, the Tucker decomposition factorizes it into a core tensor $\mathcal{G} \in \mathbb{R}^{R_1 \times R_2 \times \cdots \times R_N}$ and factor matrices $\mathbf{A}^{(n)} \in \mathbb{R}^{I_n \times R_n}$: $\mathcal{X} \approx \mathcal{G} \times_1 \mathbf{A}^{(1)} \times_2 \mathbf{A}^{(2)} \times_3 \cdots \times_N \mathbf{A}^{(N)}$
• $\times_n$ denotes the n-mode product between a tensor and a matrix

Tucker core tensor and factor matrices

• The core tensor $\mathcal{G}$ captures the interactions between the latent factors along each mode
• The factor matrices $\mathbf{A}^{(n)}$ represent the principal components or basis vectors for each mode
• The Tucker decomposition allows for different ranks $(R_1, R_2, \ldots, R_N)$ along each mode, providing flexibility in modeling complex interactions

Higher-order SVD (HOSVD)

• The Higher-order SVD (HOSVD) is a specific Tucker decomposition where the factor matrices are obtained by applying SVD to the n-mode unfoldings of the tensor
• HOSVD provides an initial solution for the Tucker decomposition, which can be further refined using optimization techniques

Computing the Tucker decomposition

• The Tucker decomposition is typically computed by minimizing the Frobenius norm of the difference between the original tensor and its Tucker approximation: $\min_{\mathcal{G}, \mathbf{A}^{(n)}} \|\mathcal{X} - \mathcal{G} \times_1 \mathbf{A}^{(1)} \times_2 \mathbf{A}^{(2)} \times_3 \cdots \times_N \mathbf{A}^{(N)}\|_F^2$
• This optimization problem is non-convex, but effective algorithms exist for finding good approximate solutions

Tucker decomposition algorithms

• Alternating least squares (ALS): Iteratively updates the core tensor and each factor matrix while keeping the others fixed
• Higher-order orthogonal iteration (HOOI): Iteratively updates the factor matrices using SVD and the core tensor using least squares
• Riemannian optimization: Exploits the manifold structure of the parameter space to develop efficient optimization algorithms
• Randomized algorithms: Employ random projections or sampling to reduce computational complexity

Tensor-train (TT) decomposition

• The Tensor-train (TT) decomposition is a compact and numerically stable representation for high-order tensors
• It expresses a tensor as a chain of lower-order tensors, called TT-cores, which allows for efficient storage and computation

TT decomposition definition

• Given an $N$-th order tensor $\mathcal{X} \in \mathbb{R}^{I_1 \times I_2 \times \cdots \times I_N}$, the TT decomposition represents it as a chain of 3rd-order tensors $\mathcal{G}_1, \mathcal{G}_2, \ldots, \mathcal{G}_N$, called TT-cores: $\mathcal{X}(i_1, i_2, \ldots, i_N) = \mathcal{G}_1(i_1) \cdot \mathcal{G}_2(i_2) \cdots \mathcal{G}_N(i_N)$
• Each TT-core $\mathcal{G}_n \in \mathbb{R}^{R_{n-1} \times I_n \times R_n}$ is a 3rd-order tensor, with $R_0 = R_N = 1$

TT-ranks and TT-cores

• The dimensions $R_1, R_2, \ldots, R_{N-1}$ are called TT-ranks and control the complexity of the TT representation
• Lower TT-ranks lead to more compact representations, while higher TT-ranks allow for more expressive models
• The TT-cores capture the interactions between adjacent modes and can be interpreted as "compressed" versions of the original tensor

Computing the TT decomposition

• The TT decomposition can be computed using the TT-SVD algorithm, which sequentially applies SVD to the unfoldings of the tensor
• TT-SVD guarantees that the resulting TT-cores have optimal TT-ranks for a given approximation accuracy
• Other algorithms, such as TT-cross and TT-DMRG, can also be used to compute the TT decomposition

TT decomposition algorithms

• TT-SVD: Sequentially unfolds the tensor and applies SVD to obtain the TT-cores
• TT-cross: Approximates the TT decomposition using a sampling-based approach, which is more efficient for large-scale tensors
• TT-DMRG: Employs the density matrix renormalization group (DMRG) technique from quantum physics to compute the TT decomposition
• Riemannian optimization: Exploits the manifold structure of the TT-cores to develop efficient optimization algorithms

Other tensor decompositions

• Several other tensor decompositions have been proposed to address specific challenges or to provide alternative representations
• These decompositions offer unique advantages and can be used in combination with the more common CP, Tucker, and TT decompositions

Block term decompositions

• Block term decompositions (BTD) generalize the CP decomposition by allowing for a sum of low-rank terms, each being the outer product of matrices
• BTD can model more complex interactions than CP and is particularly useful for analyzing multi-view or multi-set data

Tensor SVD

• Tensor SVD generalizes the matrix SVD to higher-order tensors, expressing a tensor as the product of orthogonal matrices and a diagonal tensor
• Tensor SVD provides a unique decomposition, but its computation is generally NP-hard

Hierarchical Tucker decomposition

• The Hierarchical Tucker (HT) decomposition represents a tensor using a binary tree of lower-order tensors
• HT decomposition allows for an even more compact representation than TT and can handle tensors with high dimensionality and complex structures

Tensor completion and recovery

• Tensor completion and recovery are important problems in data science, where the goal is to estimate missing or corrupted entries in a tensor
• Tensor decompositions play a crucial role in solving these problems by exploiting the low-rank structure of the data

Low-rank tensor completion problem

• The low-rank tensor completion problem aims to recover a low-rank tensor from a subset of its entries
• This problem arises in various applications, such as recommender systems, image inpainting, and multi-way missing data analysis
• Tensor decompositions, such as CP, Tucker, and TT, can be used to formulate the completion problem as a low-rank approximation task

Tensor recovery from partial observations

• Tensor recovery is a more general problem, where the goal is to estimate a tensor from partial or corrupted observations
• This includes the completion problem as a special case, but also covers scenarios with noisy or transformed measurements
• Tensor decompositions can be combined with optimization techniques, such as convex relaxation or Bayesian inference, to solve the recovery problem

Algorithms for tensor completion and recovery

• Alternating minimization: Iteratively updates the factors of a tensor decomposition to minimize the reconstruction error on the observed entries
• Nuclear norm minimization: Relaxes the low-rank constraint using the tensor nuclear norm and solves a convex optimization problem
• Riemannian optimization: Exploits the manifold structure of low-rank tensors to develop efficient optimization algorithms
• Bayesian methods: Employ probabilistic models and inference techniques, such as variational Bayes or MCMC, to estimate the posterior distribution of the tensor

Applications of tensor decompositions

• Tensor decompositions have found numerous applications in various fields, including signal processing, computer vision, neuroscience, and recommender systems
• They provide powerful tools for analyzing and extracting insights from multi-dimensional data

Multiway data analysis

• Tensor decompositions enable the joint analysis of data from multiple sources, modalities, or views
• Examples include EEG/MEG signal processing, fMRI data analysis, and multi-view learning
• Tensor decompositions can identify shared and unique patterns across different modes, facilitating data fusion and integration

Dimensionality reduction for tensors

• Tensor decompositions can be used to find low-dimensional representations of high-dimensional tensor data
• This is particularly useful for visualizing and exploring large-scale multi-dimensional datasets
• Tensor-based dimensionality reduction techniques, such as multilinear PCA and tensor CCA, extend classical methods to handle tensor data

Tensor regression and classification

• Tensor decompositions can be employed to develop predictive models for tensor-valued inputs or outputs
• Tensor regression methods, such as CP regression and Tucker regression, extend linear models to handle tensor covariates
• Tensor-based classifiers, such as support tensor machines and tensor logistic regression, can directly operate on tensor data without vectorization

Anomaly detection with tensors

• Tensor decompositions can identify unusual patterns or outliers in multi-dimensional data
• By modeling the normal behavior using a low-rank tensor representation, anomalies can be detected as deviations from this model
• Tensor-based anomaly detection methods have been applied in network monitoring, fraud detection, and industrial process control

Computational considerations

• Tensor decompositions involve computationally intensive operations, especially for large-scale and high-order tensors
• Efficient algorithms and implementations are crucial for applying tensor decompositions to real-world problems

Efficient tensor decomposition algorithms

• Exploiting sparsity: Many real-world tensors are sparse, and algorithms that leverage this sparsity can significantly reduce computational complexity
• Randomized algorithms: Employing random projections or sampling can accelerate tensor decompositions while maintaining good approximation quality
• Adaptive rank selection: Dynamically adjusting the rank of the decom