Fast Guaranteed Tensor Recovery with Adaptive Tensor Nuclear Norm

Jiangjun Peng, Hailin Wang, Xiangyong Cao, Shuang Xu

Abstract

Multidimensional data recovery is a critical challenge in fields such as medical imaging, remote sensing, and video surveillance. Traditional Tensor Nuclear Norm (TNN) methods often struggle with a trade-off between computational efficiency, data adaptability, and theoretical guarantees. This paper introduces the Adaptive Tensor Nuclear Norm (ATNN) framework, which utilizes a learnable column-orthogonal matrix to perform dimensionality reduction in a data-specific subspace. ATNN provides the first rigorous mathematical guarantee for exact recovery using non-full-rank transformations while achieving significant speedups—often 5x to 10x faster than state-of-the-art methods—across diverse datasets including hyperspectral imagery and color video.

Introduction

In modern data science, information is naturally represented as tensors (multidimensional arrays). However, real-world data is frequently corrupted by noise or missing values due to sensor limitations or transmission errors. To recover the original signal, researchers exploit the low-rank property—the principle that high-dimensional data often resides on a much simpler underlying structure.

While the Tensor Nuclear Norm (TNN) is a standard tool for low-rank recovery, existing implementations face a "trilemma":

  1. Fixed transforms (e.g., Fourier or Cosine) are computationally efficient but fail to adapt to the specific characteristics of the data.
  2. Data-adaptive transforms (e.g., neural networks) offer high performance but lack rigorous mathematical "exact recovery" guarantees.
  3. Computational Weight: Most methods process data in its full dimensions, leading to prohibitive costs for high-resolution, large-scale datasets.

The ATNN Framework

The authors propose the Adaptive Tensor Nuclear Norm (ATNN) to bridge the gap between adaptability and theoretical rigor. The core innovation lies in using a Column-Orthogonal Matrix (COM) as a learnable transformation matrix $\mathbf{D}$.

Adaptive decomposition of hyperspectral and video tensors into a core tensor B and a learnable transform D, showing rapid singular value decay.

Dimensionality Reduction and Efficiency

Unlike traditional TNN variants that assume a full-rank transformation, ATNN explicitly models the low-rank structure of the third dimension (e.g., time in a video or spectral bands in an image). If a video has $n_3$ frames but only $r_3$ distinct types of movement (where $r_3 \ll n_3$), ATNN adaptively learns a smaller subspace. This reduces computational complexity from $O(n_1^2 n_2 n_3)$ to $O(n_1^2 n_2 r_3)$, enabling the algorithm to handle "deep" tensors with remarkable speed.

Theoretical Guarantees

A major contribution of this work is the mathematical proof of exact recovery. The authors demonstrate that as long as the data satisfies an "adjusted incoherence condition"—a measure of information distribution—the ATNN model is guaranteed to recover the original data perfectly, even when utilizing a compressed subspace. This provides a theoretical foundation for using non-square, learnable matrices in tensor recovery.

Phase transition plots showing the probability of exact recovery as a function of tubal rank and sparsity for different subspace dimensions r3.

As shown in the phase transition plots, the model maintains a high probability of successful recovery (yellow regions) across various levels of sparsity and tubal rank, validating the theoretical bounds empirically.

Experimental Evaluation

The authors evaluated ATNN against several benchmarks using diverse datasets:

  • Hyperspectral & Multispectral Images: paviaU, WDC, and CAVE collection (Beans, Cloth).
  • Video Data: Standard benchmarks (Akiyo, Foreman) and the Li surveillance dataset for background-foreground separation.

Key Results

  • Superior Accuracy: In tensor completion tasks with 95% missing values, ATNN significantly outperformed standard TNN. For the WDC dataset, it achieved a Peak Signal-to-Noise Ratio (PSNR) of 38.06, compared to 30.01 for TNN.
  • Exceptional Speed: In video denoising, ATNN was consistently 5x to 10x faster than high-performing competitors like TCTV or S2NTNN.
  • Robustness: On the Li surveillance dataset, ATNN achieved the highest average AUC (0.923) while processing the data in 2.32 seconds, nearly 7.5x faster than the CTNN method (17.39 seconds).

Conclusion

ATNN represents a significant step forward in tensor recovery by combining the efficiency of dimensionality reduction with the reliability of provable exact recovery. By learning a data-specific subspace, it bypasses the limitations of fixed mathematical transforms without sacrificing theoretical rigor.

Future work may focus on automating the estimation of the rank $r_3$ for highly volatile data and extending these mathematical guarantees to higher-order tensors ($N > 3$). Additionally, exploring performance under non-Gaussian noise distributions remains an open area for investigation.

Summary updated

Abstract

Real-world datasets like multi-spectral images and videos are naturally represented as tensors. However, limitations in data acquisition often lead to corrupted or incomplete tensor data, making tensor recovery a critical challenge. Solving this problem requires exploiting inherent structural patterns, with the low-rank property being particularly vital. An important category of existing low-rank tensor recovery methods relies on the tensor nuclear norms. However, these methods struggle with either computational inefficiency or weak theoretical guarantees for large-scale data. To address these issues, we propose a fast guaranteed tensor recovery framework based on a new tensor nuclear norm. Our approach adaptively extracts a column-orthogonal matrix from the data, reducing a large-scale tensor into a smaller subspace for efficient processing. This dimensionality reduction enhances speed without compromising accuracy. The recovery theories of two typical models are established by introducing an adjusted incoherence condition. Extensive experiments demonstrate the effectiveness of the proposed method, showing improved accuracy and speed over existing approaches. Our code and supplementary material are available at https://github.com/andrew-pengjj/adaptive_tensor_nuclear_norm.
BibTeX
@inproceedings{peng2025fast,
  author = {Jiangjun Peng and Hailin Wang and Xiangyong Cao and Shuang Xu},
  title = {{Fast Guaranteed Tensor Recovery with Adaptive Tensor Nuclear Norm}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/674},
}
Figure