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":
- Fixed transforms (e.g., Fourier or Cosine) are computationally efficient but fail to adapt to the specific characteristics of the data.
- Data-adaptive transforms (e.g., neural networks) offer high performance but lack rigorous mathematical "exact recovery" guarantees.
- 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}$.
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.
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