Overview of HOOI (High-Order Orthogonal Iteration) and examples of algorithms and implementations.

Overview of HOOI (High-Order Orthogonal Iteration)

High-Order Orthogonal Iteration (HOOI) can be one of the methods based on the high-dimensional singular value decomposition (SVD) as described in “Overview of Singular Value Decomposition (SVD) and examples of algorithms and implementations” of a tensor; HOOI iteratively applies the singular value decomposition in each mode of the tensor to obtain a low-rank approximation of the tensor. An overview of HOOI is given below.

1. determining the rank of the tensor: the first step in a HOOI is to determine the rank of the tensor. The rank is usually specified a priori, but there are other methods, such as cross-validation, for determining the rank.

2. initialisation: the HOOI algorithm starts with a random tensor as an initial value. This random initial value is the starting point for iterative optimisation.

3, Singular value decomposition in each mode: the HOOI applies the singular value decomposition iteratively in each mode (dimension). The singular value decomposition represents a partial singular value decomposition of the tensor in each mode.

4. iterative iteration: the steps of the singular value decomposition are iteratively repeated to improve the low-rank approximation of the tensor. The number of iterations is pre-specified or repeated until certain convergence criteria are met.

5. convergence decision: when the iterations converge, the algorithm terminates and the final low-rank approximated tensor is obtained. The convergence decision uses, for example, the approximation accuracy of the tensor and the number of iterations.

HOOI can be an iterative algorithm that can efficiently obtain a low-rank approximation of the tensor. This method exploits the high dimensionality of the tensor to provide an efficient data representation and has been widely applied in machine learning and signal processing.

Examples of HOOI (High-Order Orthogonal Iteration) implementations

The implementation of High-Order Orthogonal Iteration (HOOI) is based on iteratively applying the Singular Value Decomposition (SVD) of the tensor in each mode. A simple example of a HOOI implementation in Python is given below. This example uses the NumPy library.

import numpy as np

def hooi(tensor, rank, max_iter=100, tol=1e-6):
    """
    HOOI (High-Order Orthogonal Iteration) implementation
    :param tensor: Tensors applying the TT decomposition
    :param rank: List of TT ranks.
    :param max_iter: Maximum number of iterations
    :param tol: Tolerance for convergence decision
    :return: TT decomposed tensor sequence
    """
    # Number of dimensions of the tensor
    num_dims = len(rank)
    
    # Initialisation of tensor sequence
    tensor_list = []
    
    # Initialisation of singular vectors for each mode.
    u_matrices = [np.random.rand(tensor.shape[i], rank[i]) for i in range(num_dims)]
    
    # iteration
    for _ in range(max_iter):
        # Singular value decomposition in each mode.
        for i in range(num_dims):
            # Convolution of tensors in mode i.
            mode_products = np.tensordot(tensor, u_matrices[i], axes=(i, 0))
            
            # Singular value decomposition of mode i
            u, _, _ = np.linalg.svd(np.reshape(mode_products, (-1, rank[i])), full_matrices=False)
            u_matrices[i] = u[:, :rank[i]]
        
        # convergence judgment (judgement)
        # For simplicity, convergence is considered here when the change in the singular vector is less than the permissible error
        # The actual convergence decision depends on the problem.
        if np.all([np.linalg.norm(u_matrices[i] - u_matrices[i-1]) < tol for i in range(1, num_dims)]):
            break
    
    # Construction of tensor sequences
    for i in range(num_dims):
        tensor_list.append(u_matrices[i])
    
    return tensor_list

# Tensor example.
tensor = np.random.rand(2, 3, 4)

# Designation of TT ranks
rank = [2, 2, 2]

# Execution of HOOI
tt_tensors = hooi(tensor, rank)

# Display of tensor sequence obtained by HOOI.
for i, tt_tensor in enumerate(tt_tensors):
    print(f"Tensor {i + 1}:")
    print(tt_tensor)
    print()

The code performs a HOOI on the given tensor and displays the TT-decomposed tensor sequence.

The challenges of HOOI (High-Order Orthogonal Iteration) and how to deal with them.

High-Order Orthogonal Iteration (HOOI) is a powerful method, but it has several challenges. These challenges and their remedies are described below.

1. convergence to a local solution: HOOI starts with random initial values and may converge to a local solution.

Solution: start with several different initial values to see if the best results can be obtained. Methods to choose initial values more wisely are also being investigated.

2. increase in computational cost: as the number of dimensions and ranks of the tensor increases, the computational cost of HOOI increases rapidly.

Solution: approximate methods and parallel computations can be used to reduce the computational cost. Heuristics for rank selection can also be used to minimise computational costs.

3. convergence guarantees: convergence of HOOI is only guaranteed under certain conditions. In real problems, convergence may be slow or not converge.

Solution: set convergence criteria and a maximum number of iterations so that the algorithm is aborted if it does not converge. Also, improved algorithms and initialisation methods to improve convergence have been studied.

4. dealing with non-linearity: HOOI is a linear method and it can be difficult to approximate properly for non-linear tensor data.

Solution: non-linear tensor decomposition methods and pre-processing or transformations of tensor data may be used to improve the linearity of the data.

Reference Information and Reference Books

For more information on optimization in machine learning, see also “Optimization for the First Time Reading Notes” “Sequential Optimization for Machine Learning” “Statistical Learning Theory” “Stochastic Optimization” etc.

Reference books include Optimization for Machine Learning

“Machine Learning, Optimization, and Data Science“

“Linear Algebra and Optimization for Machine Learning: A Textbook“