Robust Tensor Decomposition via Orientation Invariant Tubal Nuclear Norms

Andong Wang, Chao Li, Zhong Jin, Qibin Zhao

Introduction

In modern signal processing and computer vision, data is frequently represented as high-dimensional tensors. Whether it is a 3D color image or a 4D video sequence, these structures often exhibit "low-rank" properties, where information is redundant and compressible. Recovering such signals from noise or missing values is a critical challenge. While the Tubal Nuclear Norm (TNN) has emerged as a state-of-the-art tool for this purpose, it suffers from a significant limitation: orientation sensitivity. Standard TNN typically captures low-rank patterns along only one predefined "tubal" dimension, potentially missing critical structures in other orientations.

Methodology: Orientation Invariance

To overcome the limitations of traditional TNN, this work introduces a framework that makes the norm orientation-invariant for any $K$-way tensor.

3d-Unfolding

The foundational innovation is the 3d-unfolding technique. This mathematical operation reshapes a high-dimensional tensor into a 3D tensor while preserving the tubal structure across various modes. By rotating and reshaping the data, the framework can apply TNN logic across all possible orientations simultaneously.

The 3d-unfolding process for high-dimensional tensors.

OITNN-O and OITNN-L

Building on 3d-unfolding, two new norms are proposed:

  1. OITNN-O (Overlapped): This norm assumes the tensor is low-rank across all orientations. It is calculated by summing the TNNs of all possible 3d-unfoldings.
  2. OITNN-L (Latent): A more flexible approach, OITNN-L assumes the tensor is a mixture of components, where each component is low-rank in at least one specific orientation. This is particularly effective for complex, non-symmetrical data.
Comparison of (a) OITNN-O and (b) OITNN-L frameworks.

Robust Tensor Decomposition

The proposed norms are integrated into a Robust Tensor Decomposition (RTD) framework designed to separate a low-rank signal from sparse "gross" corruptions and dense noise. The optimization problem is solved using the Alternating Direction Method of Multipliers (ADMM), providing a robust and efficient recovery algorithm. Unlike many empirical approaches, this framework provides non-asymptotic error bounds, predicting recovery accuracy based on noise levels and data rank.

Experimental Results

The models were rigorously tested across synthetic and real-world datasets, including standard benchmark images, YUV video sequences, and Unmanned Ground Vehicle (UGV) data (LiDAR and camera images).

  • Denoising Performance: In color image tasks, OITNN consistently outperformed Matrix Nuclear Norm and standard TNN in terms of Peak Signal-to-Noise Ratio (PSNR).
  • Structured Inpainting: A key success was observed in "Setting II" inpainting, where entire rows or columns were missing. Unlike traditional methods that failed to bridge these gaps, OITNN successfully leveraged correlations in alternative orientations to recover the missing data.
  • UGV Data: On LiDAR intensity tensors, OITNN-O achieved a PSNR of 23.31 dB, significantly higher than the 21.61 dB achieved by matrix-based methods.

Conclusion

By breaking the orientation barrier of traditional tensor norms, OITNN-O and OITNN-L provide a more comprehensive way to exploit low-rank structures in high-dimensional data. While future work remains in automating hyperparameter tuning and reducing computational overhead for massive tensors, this framework establishes a new benchmark for robust tensor recovery with strong theoretical foundations.

Summary updated

Abstract

Low-rank tensor recovery has been widely applied to computer vision and machine learning. Recently, tubal nuclear norm (TNN) based optimization is proposed with superior performance as compared to other tensor nuclear norms. However, one major limitation is its orientation sensitivity due to low-rankness strictly defined along tubal orientation and it cannot simultaneously model spectral low-rankness in multiple orientations. To this end, we introduce two new tensor norms called OITNN-O and OITNN-L to exploit multi-orientational spectral low-rankness for an arbitrary K-way (K ≥ 3) tensors. We further formulate two robust tensor decomposition models via the proposed norms and develop two algorithms as the solutions. Theoretically, we establish non-asymptotic error bounds which can predict the scaling behavior of the estimation error. Experiments on real-world datasets demonstrate the superiority and effectiveness of the proposed norms.
BibTeX
@inproceedings{wang2020robust,
  author = {Andong Wang and Chao Li and Zhong Jin and Qibin Zhao},
  title = {{Robust Tensor Decomposition via Orientation Invariant Tubal Nuclear Norms}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.6074},
}
Figure