Block-Sparse Tensor Recovery

Liyang Lu, Zhaocheng Wang, Z. Gao, Sheng Chen, H. Vincent Poor

Abstract

This work explores the fundamental problem of the recoverability of a sparse tensor being reconstructed from its compressed embodiment. We present a generalized model of block-sparse tensor recovery as a theoretical foundation, where concepts measuring holistic mutual incoherence property (MIP) of the measurement matrix set are defined. A representative algorithm based on the orthogonal matching pursuit (OMP) framework, called tensor generalized block OMP (T-GBOMP), is applied to the theoretical framework elaborated for analyzing both noiseless and noisy recovery conditions. Specifically, we present the exact recovery condition (ERC) and sufficient conditions for establishing it with consideration of different degrees of restriction. Reliable reconstruction conditions, in terms of the residual convergence, the estimated error and the signal-to-noise ratio bound, are established to reveal the computable theoretical interpretability based on the newly defined MIP, which we introduce. The flexibility of tensor recovery is highlighted, i.e., the reliable recovery can be guaranteed by optimizing MIP of the measurement matrix set. Analytical comparisons demonstrate that the theoretical results developed are tighter and less restrictive than the existing ones (if any). Further discussions provide tensor extensions for several classic greedy algorithms, indicating that the sophisticated results derived are universal and applicable to all these tensorized variants.

Introduction

In modern signal processing applications such as wireless communications (channel estimation) and medical imaging, reconstructing high-dimensional signals from limited measurements is a critical challenge. While traditional compressed sensing focuses on vectors or matrices, real-world data often exhibits multi-dimensional "block-sparse" structures, where non-zero values appear in clusters across different modes.

Existing theoretical guarantees, like the Restricted Isometry Property (RIP), are often NP-hard to calculate, limiting their practical utility. Furthermore, standard metrics like the Mutual Incoherence Property (MIP) were designed for single matrices and fail to capture the complex interactions between multiple measurement matrices in tensor recovery. This paper addresses these gaps by providing a computable theoretical framework specifically for block-sparse tensors.

Theoretical Framework and T-GBOMP

The authors introduce a new framework based on Mutual Block Coherence and Mutual Sub-coherence for a set of measurement matrices. These metrics quantify the distinguishability of columns when combined in a tensor product, providing a bridge between theoretical guarantees and practical engineering.

Tensor measurement model showing the relationship between the core tensor $\mathcal{X}$ and measurement matrices $\mathbf{D}_n$.

Central to this framework is the Tensor Generalized Block Orthogonal Matching Pursuit (T-GBOMP) algorithm. This greedy approach reconstructs the tensor by iteratively selecting the most likely signal blocks. T-GBOMP serves as a generalized version of several classic algorithms, including OMP, BOMP, and CoSaMP, adapted for the tensor domain.

Key Insights: Shadow Sparsity and the Power of N

A pivotal concept introduced is Shadow Block Sparsity, which quantifies how non-zero blocks overlap across different tensor dimensions. This structural property significantly influences the ease of recovery.

Illustration of shadow extraction and the concept of shadow block sparsity across tensor modes.

One of the most significant findings is the "Power of N": as the number of tensor modes ($n$) increases, the Signal-to-Noise Ratio (SNR) required for reliable recovery actually decreases. This suggests that high-dimensional tensor structures are inherently more robust to noise than their vector or matrix counterparts due to multi-dimensional correlations.

Results and Performance

The theoretical results were validated using synthetic simulations involving block-sparse Gaussian and 2-PAM tensors. Key findings include:

  • Tighter Bounds: The derived reconstructible sparsity levels are mathematically superior to previous 1D or 2D models.
  • Superior Performance: T-GBOMP consistently outperformed standard algorithms like BOMP and BOLS, particularly when measurement matrices had high coherence.
  • Convergence and Robustness: The authors proved exponential residual error decay and provided concrete lower bounds for SNR, showing reliable recovery even at 10 dB in 3-mode tensor simulations.

Conclusion

This work provides a rigorous yet computable foundation for tensor recovery. By shifting focus from RIP to MIP, the authors offer tools that engineers can use to verify system designs in seconds. Future work includes extending this framework to non-linear measurement models and applying these insights to hardware designs in massive MIMO and holographic radio.

Summary updated

Abstract

This work explores the fundamental problem of the recoverability of a sparse tensor being reconstructed from its compressed embodiment. We present a generalized model of block-sparse tensor recovery as a theoretical foundation, where concepts measuring holistic mutual incoherence property (MIP) of the measurement matrix set are defined. A representative algorithm based on the orthogonal matching pursuit (OMP) framework, called tensor generalized block OMP (T-GBOMP), is applied to the theoretical framework elaborated for analyzing both noiseless and noisy recovery conditions. Specifically, we present the exact recovery condition (ERC) and sufficient conditions for establishing it with consideration of different degrees of restriction. Reliable reconstruction conditions, in terms of the residual convergence, the estimated error and the signal-to-noise ratio bound, are established to reveal the computable theoretical interpretability based on the newly defined MIP, which we introduce. The flexibility of tensor recovery is highlighted, i.e., the reliable recovery can be guaranteed by optimizing MIP of the measurement matrix set. Analytical comparisons demonstrate that the theoretical results developed are tighter and less restrictive than the existing ones (if any). Further discussions provide tensor extensions for several classic greedy algorithms, indicating that the sophisticated results derived are universal and applicable to all these tensorized variants.
BibTeX
@article{lu2024block,
  author = {Liyang Lu and Zhaocheng Wang and Z. Gao and Sheng Chen and H. Vincent Poor},
  title = {{Block-Sparse Tensor Recovery}},
  journal = {IEEE Trans. Information Theory},
  year = {2024},
  doi = {10.1109/tit.2024.3447050},
}
Figure