Low-Rank and Sparse Enhanced Tucker Decomposition for Tensor Completion

Chenjian Pan, Ling Chen, Hongjin He, Liqun Qi, Yanwei Xu

Abstract

Tensor completion refers to the task of estimating the missing data from an incomplete measurement or observation, which is a core problem frequently arising from the areas of big data analysis, computer vision, and network engineering. Due to the multidimensional nature of high-order tensors, the matrix approaches, e.g., matrix factorization and direct matricization of tensors, are often not ideal for tensor completion and recovery. In this paper, we introduce a unified low-rank and sparse enhanced Tucker decomposition model for tensor completion. Our model possesses a sparse regularization term to promote a sparse core tensor of the Tucker decomposition, which is beneficial for tensor data compression. Moreover, we enforce low-rank regularization terms on factor matrices of the Tucker decomposition for inducing the low-rankness of the tensor with a cheap computational cost. Numerically, we propose a customized ADMM with enough easy subproblems to solve the underlying model. It is remarkable that our model is able to deal with different types of real-world data sets, since it exploits the potential periodicity and inherent correlation properties appeared in tensors. A series of computational experiments on real-world data sets, including internet traffic data sets, color images, and face recognition, demonstrate that our model performs better than many existing state-of-the-art matricization and tensorization approaches in terms of achieving higher recovery accuracy.

Introduction

In the era of big data, information is increasingly multidimensional, represented as high-order tensors (e.g., video data as height $\times$ width $\times$ time). These tensors often suffer from missing entries due to sensor failures or transmission errors. The challenge of tensor completion lies in accurately estimating these missing values while preserving the inherent multidimensional structures.

Traditional approaches often rely on "flattening" tensors into matrices. However, this matricization destroys critical structural information, such as periodicity in traffic data or self-similarity in facial images. While existing tensor-based methods like CP or standard Tucker decomposition offer improvements, they often struggle with computational efficiency or fail to fully exploit the "low-rank + sparse" nature of real-world signals, where data exhibits both global structure and fine-grained details.

Methodology: The LR-SETD Model

To address these limitations, we introduce the Low-Rank and Sparse Enhanced Tucker Decomposition (LR-SETD) model. This framework leverages dual regularization to capture the complex properties of multidimensional data.

Tucker decomposition of a third-order tensor into a core tensor and factor matrices.

The key innovations of LR-SETD include:

  1. Dual Regularization: Unlike standard models, LR-SETD applies an $\ell_1$-norm to the core tensor to promote sparsity and a nuclear norm to the factor matrices to induce low-rankness. This dual approach preserves textures while maintaining global structure.
  2. Computational Efficiency: By enforcing low-rankness on the smaller factor matrices rather than the massive unfolded tensor, the model significantly reduces the cost of Singular Value Decompositions (SVDs).
  3. Structural Priors: For data with temporal stability, such as traffic flow, the model incorporates a Toeplitz matrix constraint to characterize hidden periodic structures.
  4. Customized ADMM: We developed a specific Alternating Direction Method of Multipliers (ADMM) algorithm that decomposes the non-convex optimization problem into several "easy" subproblems, most of which have closed-form solutions.

Experimental Evaluation

The model was evaluated across three distinct domains: internet/urban traffic (Abilene, GEANT, Guangzhou datasets), color images (baboon, sailboat, lena, etc.), and face recognition (ORL and MultiPIE databases).

Visual recovery results for baboon and lena images under different truncation levels.

Key Results

  • Recovery Accuracy: In image inpainting tasks, LR-SETD consistently achieved higher Peak Signal-to-Noise Ratio (PSNR) and lower Relative Squared Error (RSE) compared to state-of-the-art methods like HaLRTC and TCTF.
  • Robustness to Missing Data: Even with only 5%–10% of the original data available, the model reconstructed recognizable images and accurate traffic patterns.
  • Handling Structural Loss: In scenarios with "structurally missing" data (e.g., a sensor failing for an entire day), LR-SETD outperformed competitors by a wide margin by utilizing Toeplitz matrices to bake in periodicity.
  • Convergence: The customized ADMM proved highly competitive, often reaching convergence in fewer iterations than traditional matricization approaches.

Discussion and Conclusion

A crucial insight of this work is that core tensors of natural images are naturally sparse (often >60% of entries are near zero). Explicitly regularizing for this sparsity preserves image quality while improving recovery. Furthermore, regularizing the smaller factor matrices serves as an effective and computationally "cheap" proxy for regularizing the entire tensor.

While LR-SETD shows significant promise, it relies on hyperparameters that may require manual tuning for new data types. Future work could involve extending the model to handle streaming data or integrating it with deep learning architectures to automatically learn structural matrices rather than pre-defining them as Toeplitz.

Summary updated

Abstract

Tensor completion refers to the task of estimating the missing data from an incomplete measurement or observation, which is a core problem frequently arising from the areas of big data analysis, computer vision, and network engineering. Due to the multidimensional nature of high-order tensors, the matrix approaches, e.g., matrix factorization and direct matricization of tensors, are often not ideal for tensor completion and recovery. In this paper, we introduce a unified low-rank and sparse enhanced Tucker decomposition model for tensor completion. Our model possesses a sparse regularization term to promote a sparse core tensor of the Tucker decomposition, which is beneficial for tensor data compression. Moreover, we enforce low-rank regularization terms on factor matrices of the Tucker decomposition for inducing the low-rankness of the tensor with a cheap computational cost. Numerically, we propose a customized ADMM with enough easy subproblems to solve the underlying model. It is remarkable that our model is able to deal with different types of real-world data sets, since it exploits the potential periodicity and inherent correlation properties appeared in tensors. A series of computational experiments on real-world data sets, including internet traffic data sets, color images, and face recognition, demonstrate that our model performs better than many existing state-of-the-art matricization and tensorization approaches in terms of achieving higher recovery accuracy.
BibTeX
@misc{pan2020low,
  author = {Chenjian Pan and Ling Chen and Hongjin He and Liqun Qi and Yanwei Xu},
  title = {{Low-Rank and Sparse Enhanced Tucker Decomposition for Tensor Completion}},
  year = {2020},
  eprint = {2010.00359},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2010.00359},
}
Figure