Abstract
Exact recovery of tensor decomposition (TD) methods is a desirable property in both unsupervised learning and scientific data analysis. The numerical defects of TD methods, however, limit their practical applications on real-world data. As an alternative, convex tensor decomposition (CTD) was proposed to alleviate these problems, but its exact-recovery property is not properly addressed so far. To this end, we focus on latent convex tensor decomposition (LCTD), a practically widely-used CTD model, and rigorously prove a sufficient condition for its exact-recovery property. Furthermore, we show that such property can be also achieved by a more general model than LCTD. In the new model, we generalize the classic tensor (un-)folding into reshuffling operation, a more flexible mapping to relocate the entries of the matrix into a tensor. Armed with the reshuffling operations and exact-recovery property, we explore a totally novel application for (generalized) LCTD, i.e., image steganography. Experimental results on synthetic data validate our theory, and results on image steganography show that our method outperforms the state-of-the-art methods.
Introduction
Tensor Decomposition (TD) is a fundamental tool for discovering hidden structures in multidimensional data. However, traditional non-convex methods like CP or Tucker decomposition often suffer from numerical instability, local minima, and the requirement to pre-specify the tensor rank. While Convex Tensor Decomposition (CTD) was introduced to mitigate these optimization issues, its ability to guarantee exact recovery of true low-rank components remained theoretically unproven. A significant bottleneck in standard CTD is "unfolding," which flattens tensors into often unbalanced matrices, mathematically limiting recovery capacity.
Reshuffled Tensor Decomposition
To bridge the gap between convex optimization and exact recovery, this work introduces Reshuffled Tensor Decomposition (Reshuffled-TD). The core innovation is replacing standard mode-based unfolding with a flexible reshuffling operation. Reshuffling is a generalized mapping that relocates the entries of a matrix into a tensor without altering their values, allowing for the creation of perfectly balanced matrices.
The model decomposes an observed tensor into a sum of latent components, each associated with a unique reshuffling operator. Recovery is achieved by minimizing the sum of matrix nuclear norms using an Augmented Lagrangian method. The authors define a new metric, Reshuffled-low-rank incoherence, and prove that exact recovery is guaranteed if the reshuffling operations are sufficiently "incoherent"—meaning they scramble data in fundamentally different ways.
Empirical Validation and Results
The theoretical guarantees were validated using synthetic data, focusing on phase transitions across varying ranks ($r$), matrix sizes ($n$), and component counts ($N$).
As shown in Figure 3, the empirical results align closely with the theoretical bounds (indicated by the red lines). Exact recovery is highly reliable when the matrix size is large relative to the rank and the number of components. The method also demonstrates significant robustness to noise and model over-specification.
Figure 4 illustrates that the algorithm maintains high performance (tSIR) for SNR $\ge$ 20dB and accurately determines the number of components even when the initial rank estimate is high. In real-world steganography tests on the FVC+FIVEK dataset, Reshuffled-TD achieved a Signal-to-Interference Ratio (SIR) of 20.25 dB on the cover image and 12.80 dB on the secret image, significantly outperforming traditional methods like LSB, which achieved only 3.32 dB on the cover image.
Key Insights and Applications
A primary insight of this work is that incoherence is the key to demixing. The exact recovery of a tensor's components depends heavily on how "separated" their tangent spaces are. By breaking free from rigid mode-n unfolding, researchers can explore richer, more balanced low-rank structures.
This property makes Reshuffled-TD ideal for image steganography. By treating secret image channels as low-rank components and reshuffling them with a secret key, they can be embedded into a cover image. The receiver can then perfectly extract the hidden data without needing pre-trained neural networks.
Conclusion and Future Work
This paper establishes the first rigorous proof for exact recovery in LCTD through the lens of reshuffling. While highly effective, the current model assumes strict equality, leading to performance drops in high-noise environments (SNR < 20dB). Future research will explore low-tensor-rank assumptions and the potential for learning optimal reshuffling operations directly from data rather than relying on random permutations.
Summary updated