Tensor Decomposition Methods

Understanding tensor decomposition techniques for multi-way data analysis and dimensionality reduction.

Tensor decomposition methods extend matrix factorization to handle multi-way arrays, enabling the analysis of higher-order data structures. These techniques are particularly useful for analyzing temporal, spatial, and multi-modal data.

Theoretical Foundation

Tensor Basics

A tensor is a multi-dimensional array. The order of a tensor is the number of dimensions:

  • 1st order: vector
  • 2nd order: matrix
  • 3rd order and higher: tensor

Tensor Operations

Key operations include:

  1. Mode-n product: Y=X×nU\mathcal{Y} = \mathcal{X} \times_n U
  2. Tensor matricization: Unfolding tensor along a mode
  3. Kronecker product: A⊗BA \otimes B
  4. Khatri-Rao product: A⊙BA \odot B

CP Decomposition (CANDECOMP/PARAFAC)

Mathematical Foundation

CP decomposition approximates a tensor as a sum of rank-one tensors:

X≈∑r=1Rar∘br∘cr\mathcal{X} \approx \sum_{r=1}^R a_r \circ b_r \circ c_r

where ∘\circ denotes the outer product.

Implementation

class CPDecomposition:
    def __init__(self, rank=2, max_iter=100, tol=1e-4):
        self.rank = rank
        self.max_iter = max_iter
        self.tol = tol
    
    def fit_transform(self, X):
        """Fit CP decomposition"""
        # Get tensor dimensions
        dims = X.shape
        n_modes = len(dims)
        
        # Initialize factors
        factors = [np.random.rand(dim, self.rank) 
                  for dim in dims]
        
        # Normalize factors
        for r in range(self.rank):
            for n in range(n_modes-1):
                norm = np.linalg.norm(factors[n][:, r])
                factors[n][:, r] /= norm
        
        # Alternating least squares
        for iteration in range(self.max_iter):
            for mode in range(n_modes):
                # Compute Khatri-Rao product of other factors
                kr_product = self._khatri_rao_product(
                    factors[:mode] + factors[mode+1:])
                
                # Update factor matrix
                X_n = self._matricize(X, mode)
                factors[mode] = np.dot(X_n, np.linalg.pinv(kr_product.T))
                
                # Normalize columns
                for r in range(self.rank):
                    norm = np.linalg.norm(factors[mode][:, r])
                    if norm > 0:
                        factors[mode][:, r] /= norm
        
        return factors
    
    def _khatri_rao_product(self, matrices):
        """Compute Khatri-Rao product of matrices"""
        result = matrices[0]
        for matrix in matrices[1:]:
            result = self._kr_product(result, matrix)
        return result
    
    def _kr_product(self, A, B):
        """Compute Khatri-Rao product of two matrices"""
        n_cols = A.shape[1]
        result = np.zeros((A.shape[0] * B.shape[0], n_cols))
        for i in range(n_cols):
            result[:, i] = np.kron(A[:, i], B[:, i])
        return result
    
    def _matricize(self, tensor, mode):
        """Matricize tensor along specified mode"""
        return np.reshape(np.moveaxis(tensor, mode, 0),
                        (tensor.shape[mode], -1))

Tucker Decomposition

Mathematical Foundation

Tucker decomposition factorizes a tensor into a core tensor and factor matrices:

X≈G×1U(1)×2U(2)×3U(3)\mathcal{X} \approx \mathcal{G} \times_1 U^{(1)} \times_2 U^{(2)} \times_3 U^{(3)}

Implementation

class TuckerDecomposition:
    def __init__(self, ranks, max_iter=100, tol=1e-4):
        self.ranks = ranks
        self.max_iter = max_iter
        self.tol = tol
    
    def fit_transform(self, X):
        """Fit Tucker decomposition"""
        # Get tensor dimensions
        n_modes = len(X.shape)
        
        # Initialize factor matrices
        factors = [np.random.rand(X.shape[n], self.ranks[n])
                  for n in range(n_modes)]
        
        # Higher-order orthogonal iteration (HOOI)
        for iteration in range(self.max_iter):
            for mode in range(n_modes):
                # Compute mode-n product with other factors
                Y = X.copy()
                for n in range(n_modes):
                    if n != mode:
                        Y = self._mode_n_product(
                            Y, factors[n].T, n)
                
                # Matricize intermediate result
                Y_n = self._matricize(Y, mode)
                
                # Update factor matrix using SVD
                U, _, _ = np.linalg.svd(Y_n, full_matrices=False)
                factors[mode] = U[:, :self.ranks[mode]]
        
        # Compute core tensor
        core = X.copy()
        for mode in range(n_modes):
            core = self._mode_n_product(
                core, factors[mode].T, mode)
        
        return core, factors
    
    def _mode_n_product(self, tensor, matrix, mode):
        """Compute mode-n product of tensor and matrix"""
        return np.moveaxis(
            np.tensordot(tensor, matrix, axes=(mode, 1)),
            -1, mode)
    
    def _matricize(self, tensor, mode):
        """Matricize tensor along specified mode"""
        return np.reshape(np.moveaxis(tensor, mode, 0),
                        (tensor.shape[mode], -1))

Tensor Train Decomposition

Mathematical Foundation

Tensor Train (TT) decomposition represents a tensor as a chain of 3D tensors:

X(i1,…,id)=G1[i1]G2[i2]⋯Gd[id]\mathcal{X}(i_1,\ldots,i_d) = G_1[i_1]G_2[i_2]\cdots G_d[i_d]

Implementation

class TensorTrain:
    def __init__(self, ranks, max_iter=100):
        self.ranks = ranks
        self.max_iter = max_iter
    
    def fit_transform(self, X):
        """Fit Tensor Train decomposition"""
        # Get tensor dimensions
        dims = X.shape
        n_dims = len(dims)
        
        # Initialize cores
        cores = []
        current = X.reshape(dims[0], -1)
        
        # Sequential SVD
        for i in range(n_dims - 1):
            # Reshape and compute SVD
            current_shape = (-1, 
                           dims[i+1] * 
                           np.prod(dims[i+2:]))
            current = current.reshape(current_shape)
            
            U, S, V = np.linalg.svd(current, full_matrices=False)
            
            # Truncate to desired rank
            rank = min(self.ranks[i], len(S))
            U = U[:, :rank]
            S = S[:rank]
            V = V[:rank, :]
            
            # Create core tensor
            core_shape = (-1, dims[i], rank)
            cores.append(U.reshape(core_shape))
            
            # Update current matrix
            current = np.diag(S) @ V
        
        # Add final core
        cores.append(current.reshape(-1, dims[-1], 1))
        
        return cores
    
    def reconstruct(self, cores):
        """Reconstruct tensor from TT-cores"""
        result = cores[0]
        for core in cores[1:]:
            # Contract along last and first modes
            result = np.tensordot(result, core, axes=([-1], [0]))
        
        return result.squeeze()

Applications

1. Temporal Data Analysis

def analyze_temporal_data(data, n_components=5):
    """Analyze temporal data using CP decomposition"""
    # Reshape data to tensor (time x features x samples)
    tensor = data.reshape((-1, data.shape[1], data.shape[2]))
    
    # Apply CP decomposition
    cp = CPDecomposition(rank=n_components)
    factors = cp.fit_transform(tensor)
    
    # Extract temporal patterns
    temporal_patterns = factors[0]
    feature_patterns = factors[1]
    sample_patterns = factors[2]
    
    return temporal_patterns, feature_patterns, sample_patterns

2. Multi-modal Data Fusion

def fuse_multimodal_data(modalities, ranks):
    """Fuse multi-modal data using Tucker decomposition"""
    # Stack modalities into tensor
    tensor = np.stack(modalities, axis=-1)
    
    # Apply Tucker decomposition
    tucker = TuckerDecomposition(ranks=ranks)
    core, factors = tucker.fit_transform(tensor)
    
    # Extract modality-specific patterns
    patterns = {f"modality_{i}": factor 
               for i, factor in enumerate(factors)}
    
    return core, patterns

Best Practices

1. Method Selection

  • Use CP for interpretable components
  • Choose Tucker for flexible decomposition
  • Apply TT for high-dimensional data
  • Consider computational resources

2. Parameter Selection

  • Choose ranks carefully
  • Monitor convergence
  • Consider multiple initializations
  • Validate results

3. Data Preparation

  • Handle missing values
  • Scale appropriately
  • Consider tensor structure
  • Remove noise if necessary

Common Challenges and Solutions

1. Computational Efficiency

  • Use randomized methods
  • Implement parallel processing
  • Consider online algorithms
  • Use sparse representations

2. Rank Selection

  • Use cross-validation
  • Monitor reconstruction error
  • Consider model complexity
  • Use rank estimation methods

3. Interpretability

  • Visualize components
  • Analyze factor matrices
  • Consider sparsity constraints
  • Validate with domain knowledge