L1-norm Tucker Tensor Decomposition

Dimitris G. Chachlakis, Ashley Prater-Bennette, Panos P. Markopoulos

TL;DR

This paper introduces L1-Tucker, a new formulation of the standard Tucker decomposition that uses an L1-norm instead of the L2-norm. This makes the decomposition significantly more robust to corrupted data, while performing comparably to standard Tucker on clean data. The authors propose two algorithms, L1-HOSVD and L1-HOOI, to solve this new formulation and demonstrate their effectiveness in tensor reconstruction and classification tasks.

What Problem Does This Paper Address?

Tensor decomposition, particularly the Tucker decomposition, is a powerful tool for analyzing multi-way data across various fields like signal processing and machine learning. However, the standard Tucker decomposition relies on an L2-norm (or Frobenius norm) formulation. This L2-norm penalizes large errors quadratically, making it highly sensitive to outliers or corrupted entries in the data. These corrupted entries can disproportionately influence the decomposition, leading to inaccurate results. This problem is analogous to the sensitivity of standard Principal Component Analysis (PCA) to outliers, which can be mitigated by using an L1-norm formulation (L1-PCA). This paper addresses the need for a similar robust tensor decomposition method by proposing L1-Tucker.

Methods

The core innovation is the reformulation of the Tucker decomposition objective from minimizing the L2-norm of the residual to maximizing the L1-norm of the Tucker core. This is achieved by replacing the L2-norm in the standard Tucker decomposition objective with an L1-norm.

To solve this L1-Tucker problem, the authors propose two algorithms:

  • L1-HOSVD (L1-norm Higher-Order Singular Value Decomposition): This method extends the standard HOSVD by optimizing each mode's basis individually. For each mode $n$, it solves an L1-PCA problem on the mode-$n$ unfolding of the tensor. This approach is computationally efficient but might not yield the globally optimal solution.
  • L1-HOOI (L1-norm Higher-Order Orthogonal Iterations): This is an iterative refinement algorithm that builds upon L1-HOSVD. It starts with an initialization (e.g., from L1-HOSVD) and iteratively updates all bases. In each iteration, it optimizes each mode's basis by solving an L1-PCA problem, but crucially, it considers the jointly optimized bases of the other modes. This iterative approach is shown to converge to a better L1-Tucker metric than L1-HOSVD.

Both algorithms are accompanied by formal complexity and convergence analyses.

Datasets

The paper uses synthetic datasets for its numerical studies. These datasets are generated to mimic real-world scenarios with varying levels of noise and outliers.

  • Tensor Reconstruction: A 5-way tensor is generated with a Tucker structure, then corrupted with additive white Gaussian noise (AWGN) and high-magnitude outliers.
  • Classification: The MNIST dataset of handwritten digits is used. Specifically, order-2 tensors (images) from 5 digit classes are considered, and these images are further corrupted with heavy-tail noise and pixel corruption.

No new benchmarks are introduced; the focus is on comparing the proposed methods against existing ones on standard tasks.

Key Insights and Ideas

  • L1-norm for Robustness: The fundamental insight is that replacing the L2-norm with the L1-norm in tensor decomposition directly addresses the sensitivity to outliers, mirroring the success of L1-PCA in matrix decomposition.
  • Decoupled vs. Coupled Optimization: L1-HOSVD offers a computationally simpler, decoupled approach, while L1-HOOI provides a more sophisticated, coupled iterative refinement that leads to better results.
  • L1-Tucker as a Generalization: The paper shows how L1-Tucker naturally extends L1-PCA for the N=2 case and L1-Tucker2 for the N=3 case, unifying these robust decomposition concepts.
  • Performance Trade-off: The L1-Tucker methods achieve robustness without sacrificing performance on clean data, making them a versatile alternative to standard Tucker.

Key Results

  • Tensor Reconstruction: In the presence of outliers, L1-HOSVD and L1-HOOI demonstrate significantly lower Mean Squared Error (MSE) compared to standard HOSVD and HOOI. For instance, L1-HOSVD's performance with 400 outliers was better than HOSVD's with only 40 outliers. L1-Tucker methods remained robust even with a small fraction of corrupted entries.
  • Classification: L1-Tucker methods consistently achieved higher classification accuracy than standard Tucker and PCA methods across various corruption levels (both image corruption probability and pixel corruption probability). For example, L1-HOSVD and L1-HOOI achieved around 87% accuracy with image corruption, while HOSVD and HOOI achieved only 75% and 71%, respectively. L1-Tucker methods also attained the highest classification accuracy overall, reaching about 89%.

Limitations and Future Work

  • Computational Cost: While comparable to standard HOOI, L1-HOOI's iterative nature can still be computationally intensive, especially for very large tensors. The paper mentions that the number of iterations can be set to be linear in one of the dimensions for practical purposes.
  • Tunable Parameters: Unlike standard Tucker methods, L1-PCA solvers (used within L1-HOSVD and L1-HOOI) can sometimes involve tunable parameters (e.g., sparsity penalty $\lambda$ in HORPCA). However, the proposed L1-Tucker methods, when using specific L1-PCA solvers like the alternating optimization method, do not depend on tunable parameters beyond the desired mode ranks $\{d_n\}$.
  • Exact Solution Difficulty: The paper notes that finding an exact solution for L1-Tucker, even in special cases, is hard, which is similar to the challenge for standard Tucker decomposition. This motivates the development of approximate algorithms.

Future work could explore more efficient L1-PCA solvers to further reduce the computational cost of L1-HOOI and investigate its application to even larger and more complex real-world datasets.

Summary updated

Abstract

Tucker decomposition is a common method for the analysis of multi-way/tensor data. Standard Tucker has been shown to be sensitive against heavy corruptions, due to its L2-norm-based formulation which places squared emphasis to peripheral entries. In this work, we explore L1-Tucker, an L1-norm based reformulation of standard Tucker decomposition. After formulating the problem, we present two algorithms for its solution, namely L1-norm Higher-Order Singular Value Decomposition (L1-HOSVD) and L1-norm Higher-Order Orthogonal Iterations (L1-HOOI). The presented algorithms are accompanied by complexity and convergence analysis. Our numerical studies on tensor reconstruction and classification corroborate that L1-Tucker, implemented by means of the proposed methods, attains similar performance to standard Tucker when the processed data are corruption-free, while it exhibits sturdy resistance against heavily corrupted entries.
BibTeX
@inproceedings{chachlakis2019l,
  author = {Dimitris G. Chachlakis and Ashley Prater-Bennette and Panos P. Markopoulos},
  title = {{L1-norm Tucker Tensor Decomposition}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=3dRsqjBsZ8C},
}
Figure