Generalized Higher-Order Orthogonal Iteration for Tensor Decomposition and Completion

Yuanyuan Liu, Fanhua Shang, Wei Fan, James Cheng, Hong Cheng

TL;DR

This paper introduces a scalable framework for tensor decomposition and completion by shifting the computational focus from a massive original tensor to its much smaller "core." By proving that the Schatten 1-norm of a low-rank tensor is equivalent to that of its core tensor, the authors developed the gHOI (generalized Higher-Order Orthogonal Iteration) algorithm. This approach is orders of magnitude faster and more accurate than previous state-of-the-art methods.

What Problem Does This Paper Address?

Tensors—multi-dimensional arrays—are the natural way to represent complex data like videos (3D), medical scans, and multi-channel signals. However, real-world tensor data is often incomplete due to sensor failure, corruption, or high acquisition costs.

To fill in these gaps (a process known as Tensor Completion), researchers typically use Schatten 1-norm minimization (SNM), which encourages the recovered tensor to be "low-rank." The primary bottleneck is that standard SNM requires performing Singular Value Decompositions (SVDs) on massive matrices "unfolded" from the tensor. For an $N$-th order tensor of size $I$, the complexity is $O(N I^{N+1})$, which becomes computationally impossible as dimensions grow. Furthermore, many existing methods are brittle; they fail if the underlying rank of the data is not guessed perfectly.

Methods

The authors propose a "divide and conquer" approach based on the Tucker decomposition, which represents a large tensor as a small core tensor multiplied by several factor matrices.

  1. Core Tensor Regularization: The key theoretical contribution is a proof that the Schatten 1-norm of a low-rank tensor is exactly equal to the Schatten 1-norm of its core tensor. This allows the authors to perform optimization on the tiny core instead of the giant original tensor.
  2. gHOI Algorithm: They develop a generalized version of the Higher-Order Orthogonal Iteration (HOOI). Using the Alternating Direction Method of Multipliers (ADMM), they break the problem into smaller sub-problems that can be solved iteratively.
  3. Rank-Increasing Scheme: To solve the "rank-guessing" problem, the algorithm starts with a very low rank and dynamically increases it during the optimization process. This makes the method robust to initial parameters.
  4. Reduced Complexity: Because SVDs are only performed on the core tensor, the computational cost drops from $O(N I^{N+1})$ to $O(\sum R_n^2 \times \prod R_j)$, where $R$ (the core size) is much smaller than $I$.

Datasets

The researchers evaluated their method on two main types of data:

  • Synthetic Tensors: Randomly generated low-rank tensors of orders 3, 4, and 5, with sizes ranging up to $100 \times 100 \times 100$.
  • BRAINIX Dataset: A real-world medical imaging dataset consisting of MRI scans. They tested the algorithm's ability to perform "inpainting" (recovering images) where only 10% to 50% of the pixels were known.
MRI scan reconstructions showing the original, missing data, and various recovery methods.

Key Insights and Ideas

  • The "Core" Equivalence: The most significant insight is the realization that the global structure (the Schatten norm) of a massive tensor is entirely captured by its compressed core. This justifies ignoring the "big" data during the heavy lifting of optimization.
  • Efficiency through Sparsity: By using a rank-increasing scheme, the algorithm avoids the "local minima" that trap fixed-rank methods. It effectively "grows" into the correct complexity of the data.
  • Mathematical Rigor: Unlike some heuristic-based speedups, the authors provide a convergence guarantee and a theoretical bound on the Root Mean Square Error (RMSE), proving that their recovered tensor stays "close" to the ground truth even with noisy data.

Key Results

  • Massive Speedups: On the BRAINIX dataset with 10% sampling, gHOI was 20x faster than WTucker and FaLRTC, and over 90x faster than the Latent method.
  • Superior Accuracy: In synthetic tests, gHOI consistently achieved a lower Relative Square Error (RSE) than all competitors. For example, on a 5D tensor with 50% missing data, gHOI's error was roughly one-third that of the next best method.
  • Scalability: As the size of the tensors increased, the runtime of traditional methods exploded exponentially, while gHOI’s runtime increased only slightly, demonstrating its readiness for "Big Data" applications.
Graph comparing the runtime of gHOI against other methods as tensor size increases.
  • Robustness: The method remained accurate even when the initial rank parameter was poorly estimated, whereas methods like WCP and WTucker saw their error rates spike.

Limitations and Future Work

While the paper presents a major leap in efficiency, a few areas remain for exploration:

  • Parameter Sensitivity: While more robust than others, the algorithm still relies on a penalty parameter ($\lambda$) and a rank-increase threshold ($\epsilon$) that may require tuning for specific types of data.
  • Beyond Tucker: The current work focuses on the Tucker decomposition. The authors suggest that future work could extend this "core-centric" logic to other formats like Tensor Train or Hierarchical Tucker.
  • Robustness to Outliers: The authors mention that future versions could incorporate "Robust PCA" techniques to handle not just missing data, but also data corrupted by heavy outliers or "spiky" noise.

Summary updated

Abstract

Low-rank tensor estimation has been frequently applied in many real-world problems. Despite successful applications, existing Schatten 1-norm minimization (SNM) methods may become very slow or even not applicable for large-scale problems. To address this difficulty, we therefore propose an efficient and scalable core tensor Schatten 1-norm minimization method for simultaneous tensor decomposition and completion, with a much lower computational complexity. We first induce the equivalence relation of Schatten 1-norm of a low-rank tensor and its core tensor. Then the Schatten 1-norm of the core tensor is used to replace that of the whole tensor, which leads to a much smaller-scale matrix SNM problem. Finally, an efficient algorithm with a rank-increasing scheme is developed to solve the proposed problem with a convergence guarantee. Extensive experimental results show that our method is usually more accurate than the state-of-the-art methods, and is orders of magnitude faster.
BibTeX
@inproceedings{liu2014generalized,
  author = {Yuanyuan Liu and Fanhua Shang and Wei Fan and James Cheng and Hong Cheng},
  title = {{Generalized Higher-Order Orthogonal Iteration for Tensor Decomposition and Completion}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure