🧮Advanced Matrix Computations Unit 9 – Tensor Computations

Introduction to Tensors

• Tensors are multidimensional arrays that generalize vectors and matrices to higher dimensions
• Provide a powerful framework for representing and manipulating complex, high-dimensional data
• Tensors have found applications in various fields, including physics, engineering, and computer science
• Order of a tensor refers to the number of dimensions or modes it possesses
  • Scalar is a tensor of order 0
  • Vector is a tensor of order 1
  • Matrix is a tensor of order 2
• Tensors can efficiently represent and analyze multidimensional data structures (e.g., images, videos, and graphs)
• Enable the discovery of hidden patterns and relationships in data that may not be apparent in lower-dimensional representations

Tensor Notation and Representation

• Tensors are typically denoted using boldface letters (e.g., $\mathbf{X}$) or calligraphic letters (e.g., $\mathcal{X}$)
• Elements of a tensor are accessed using subscripts, with each index corresponding to a specific mode
  • For example, $x_{ijk}$ represents the element at position $(i, j, k)$ in a third-order tensor $\mathbf{X}$
• Tensor fibers are one-dimensional subarrays obtained by fixing all but one index
  • Mode-$n$ fibers are obtained by fixing all indices except the $n$-th index
• Tensor slices are two-dimensional subarrays obtained by fixing all but two indices
• Matricization (unfolding) of a tensor involves rearranging its elements into a matrix format
  • Mode-$n$ matricization arranges the mode-$n$ fibers as columns of the resulting matrix
• Tensor rank refers to the minimum number of rank-one tensors needed to express the tensor as their sum

Basic Tensor Operations

• Tensor addition and subtraction are performed element-wise, requiring tensors to have the same size and shape
• Tensor Hadamard product (element-wise multiplication) is also performed element-wise, requiring tensors to have the same size and shape
• Tensor-matrix multiplication involves multiplying a tensor by a matrix along a specific mode
  • The mode-$n$ product of a tensor $\mathbf{X}$ and a matrix $\mathbf{A}$ is denoted as $\mathbf{X} \times_n \mathbf{A}$
• Tensor-vector multiplication is a special case of tensor-matrix multiplication, where the matrix is replaced by a vector
• Tensor contraction is a generalization of matrix multiplication, involving the summation of products of tensor elements over specified indices
• Tensor permutation reorders the modes of a tensor according to a given permutation of the indices
• Tensor reshaping changes the shape of a tensor while preserving its elements, similar to matrix reshaping

Tensor Decompositions

• Tensor decompositions aim to represent a tensor as a combination of simpler, lower-rank tensors
• CANDECOMP/PARAFAC (CP) decomposition expresses a tensor as a sum of rank-one tensors
  • Rank-one tensors are outer products of vectors
  • CP decomposition is unique under certain conditions and has found applications in signal processing and data mining
• Tucker decomposition represents a tensor as a core tensor multiplied by factor matrices along each mode
  • Core tensor captures the interactions between different modes
  • Factor matrices represent the principal components of each mode
• Tensor-train (TT) decomposition represents a tensor as a chain of third-order tensors, called TT-cores
  • TT decomposition allows for efficient storage and manipulation of high-dimensional tensors
• Hierarchical Tucker (HT) decomposition organizes the tensor into a tree-like structure, with each node representing a tensor
  • HT decomposition provides a compact representation and enables efficient tensor operations
• Tensor singular value decomposition (t-SVD) generalizes matrix SVD to third-order tensors
  • t-SVD computes tensor singular values and singular vectors, which can be used for tensor compression and denoising

Tensor Networks

• Tensor networks are graphical representations of tensors and their contractions
• Nodes in a tensor network represent tensors, while edges represent contractions between tensor modes
• Matrix product state (MPS) is a tensor network representation of a high-dimensional tensor as a chain of tensors
  • MPS is equivalent to the tensor-train decomposition
• Projected entangled pair state (PEPS) generalizes MPS to two or more dimensions
  • PEPS captures the entanglement structure of quantum many-body systems
• Tree tensor network (TTN) represents a tensor using a tree-like structure, similar to the hierarchical Tucker decomposition
• Tensor network renormalization (TNR) is a technique for coarse-graining and compressing tensor networks
  • TNR allows for efficient simulation of quantum many-body systems and lattice models
• Tensor networks have found applications in quantum physics, condensed matter physics, and machine learning

Applications in Machine Learning

• Tensors provide a natural representation for multi-modal and multi-relational data in machine learning
• Tensor completion aims to fill in missing entries of a partially observed tensor
  • Applications include recommendation systems and image inpainting
• Tensor regression extends linear regression to higher-order tensors
  • Enables the modeling of complex relationships between input features and output variables
• Tensor factorization techniques (e.g., CP and Tucker decompositions) are used for dimensionality reduction and feature extraction
  • Tensor factorization has been applied to image and video analysis, social network analysis, and brain data analysis
• Tensor-based neural networks incorporate tensor operations and decompositions into deep learning architectures
  • Examples include tensor-train neural networks and tensor regression layers
• Tensor methods have been used for multi-view learning, where data is represented from multiple perspectives or modalities
• Tensor-based approaches have shown promise in handling high-dimensional and sparse data in machine learning tasks

Computational Challenges and Optimization

• Tensor computations can be computationally expensive, especially for high-order and large-scale tensors
• Curse of dimensionality: the number of tensor elements grows exponentially with the tensor order
• Tensor sparsity can be exploited to reduce storage and computational requirements
  • Sparse tensor formats (e.g., coordinate format, compressed sparse fiber) store only non-zero elements
• Tensor decompositions can be computed efficiently using optimization algorithms
  • Alternating least squares (ALS) is a popular algorithm for CP and Tucker decompositions
  • Gradient-based optimization methods (e.g., stochastic gradient descent) are used for tensor completion and regression
• Parallel and distributed computing techniques can be employed to speed up tensor computations
  • MapReduce framework has been used for distributed tensor decompositions
• Randomized algorithms (e.g., randomized SVD) can provide efficient approximations of tensor decompositions
• Tensor network algorithms (e.g., tensor network renormalization) can efficiently contract and manipulate large-scale tensor networks

Advanced Topics and Future Directions

• Tensor-based deep learning architectures continue to be developed and refined
  • Tensor regression layers, tensor-train layers, and tensor ring layers have shown promising results
• Quantum tensor networks are being explored for simulating quantum systems and designing quantum algorithms
• Tensor methods are being applied to graph neural networks (GNNs) for learning on graph-structured data
  • Graph convolutional networks (GCNs) and graph attention networks (GATs) incorporate tensor operations
• Tensor-based approaches are being investigated for reinforcement learning and decision-making problems
• Tensor networks are being used for probabilistic modeling and inference tasks
  • Tensor network models can efficiently represent and manipulate high-dimensional probability distributions
• Integration of tensor methods with other machine learning techniques (e.g., kernel methods, Bayesian inference) is an active area of research
• Scalability and efficiency of tensor algorithms remain important challenges, particularly for large-scale and real-time applications
• Interpretability and explainability of tensor-based models are crucial for their adoption in various domains