Low-Rank Tensor Decomposition via Multiple Reshaping and Reordering Operations

Chao Li, Mohammad Emtiyaz Khan, Shengli Xie, Qibin ZhaoarXiv 2018 · OpenReview

Abstract

This paper introduces Reshuffled Tensor Decomposition (Reshuffled-TD), a novel framework that generalizes standard tensor unfolding into flexible "reshuffling" operations. We provide the first rigorous theoretical proof for the exact recovery property of Latent Convex Tensor Decomposition (LCTD) under these operations. By demonstrating that complex low-rank structures can be perfectly reconstructed when components are sufficiently incoherent, we establish a robust foundation for convex tensor models. Experimental results on synthetic data and image steganography benchmarks demonstrate that Reshuffled-TD achieves state-of-the-art performance in demixing high-dimensional data.

Introduction

Tensor Decomposition (TD) is essential for uncovering latent structures in high-dimensional datasets. A primary goal in TD is "exact recovery"—the ability to perfectly separate data into its original, physically meaningful components. Traditional approaches often struggle with this: non-convex models like CP or Tucker decomposition are prone to local minima and require prior knowledge of the data's rank, while convex models like Latent Convex Tensor Decomposition (LCTD) lacked a rigorous proof of their exact recovery capabilities.

Furthermore, standard TD methods rely on axis-aligned unfolding, a rigid operation that may fail to capture complex structural dependencies. This paper addresses these limitations by introducing a more flexible "reshuffling" operation and proving the conditions under which exact recovery is guaranteed.

Methods: Reshuffled Tensor Decomposition

The proposed Reshuffled-TD framework centers on two main innovations: the reshuffling operation and a convex optimization model.

The Reshuffling Operation

A reshuffling operation $R$ is defined as any mapping that relocates entries from a matrix into a tensor while preserving the values and total element count. Standard tensor unfolding is a specific subset of this broader class. This flexibility allows the model to capture a wider variety of low-rank structures that may not be apparent through traditional unfolding.

Convex Optimization Model

The model represents a tensor $\mathcal{X}$ as a sum of $N$ components: $\mathcal{X} = \sum_{i=1}^N R_i(\mathbf{A}_i)$. To recover the original components $\mathbf{A}_i$, the authors solve a convex optimization problem that minimizes the sum of the nuclear norms of the matrices $\mathbf{A}_i$. This approach leverages the nuclear norm as a convex proxy for rank, ensuring stable convergence to a global minimum.

Theoretical Breakthrough: Exact Recovery

The core contribution is a proof showing that if components are "incoherent"—meaning they appear structurally distinct after reshuffling—the optimization problem will recover the exact original matrices. The authors define a "Reshuffled-low-rank incoherence" measure to quantify this separation.

Phase transition of recovery for N=2 components, showing the alignment between experimental results and the theoretical bound.

The theoretical analysis establishes that recovery is unique if the matrix size $n$ is sufficiently large relative to the rank $r$ and the number of components $N$. Specifically, the bound is given by $n > (3N-2)^2 r$. As shown in the phase transition plot above, experimental results on synthetic data align closely with this theoretical red-line boundary.

Experimental Results

The framework was validated using synthetic datasets and real-world image steganography benchmarks.

Synthetic Validation and Noise Sensitivity

Experiments confirmed that recovery accuracy jumps to 100% once the theoretical conditions are met. However, the model's performance is sensitive to noise due to the strict equality constraint in the optimization.

Performance under Gaussian noise (tSIR vs SNR) and accuracy of component number determination.

As illustrated in the performance metrics, the Signal-to-Interference Ratio (SIR) improves linearly with the Signal-to-Noise Ratio (SNR) for lower ranks, but plateaus for higher-rank components. The model also demonstrates high accuracy in determining the number of components at higher SNR levels.

Image Steganography

The authors reframed image steganography as a tensor decomposition problem, where the "key" is the specific reshuffling pattern. Reshuffled-TD significantly outperformed traditional methods like LSB and DWT, as well as deep learning approaches. For instance, on the FVC+FIVEK dataset, it achieved a cover image SIR of 20.25dB and a secret image SIR of 12.80dB.

Conclusion and Future Work

Reshuffled-TD provides a theoretically grounded and flexible approach to tensor decomposition. While the current theory assumes known reshuffling operators and shows sensitivity to high noise, it sets the stage for future work in "learning" optimal operators. This would allow for the automatic discovery of efficient low-rank representations in completely unsupervised settings.

Summary updated

BibTeX
@misc{li2018low,
  author = {Chao Li and Mohammad Emtiyaz Khan and Shengli Xie and Qibin Zhao},
  title = {{Low-Rank Tensor Decomposition via Multiple Reshaping and Reordering Operations}},
  year = {2018},
  url = {https://openreview.net/forum?id=Jja1dGvd1wp},
}
Figure