Block-Sparse Tensor Recovery

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

Introduction

In modern signal processing applications such as MIMO channel estimation and spectrum sensing, data is increasingly represented as high-dimensional tensors. A common characteristic of these tensors is that their non-zero elements are not randomly distributed but are instead clustered into structured "blocks." While Compressed Sensing (CS) has matured for vector recovery, extending these principles to block-sparse tensors presents significant theoretical and computational challenges.

The primary hurdle in tensor recovery is the lack of computable performance metrics. The Restricted Isometry Property (RIP), while theoretically powerful, is NP-hard to compute. Conversely, the Mutual Incoherence Property (MIP) is computable but has historically been limited to single-matrix systems. This paper introduces a generalized MIP framework for multi-matrix systems, providing the first tight and computable recovery guarantees for greedy tensor algorithms.

The Block-Sparse Tensor Model

The authors propose a holistic model for recovering high-dimensional tensors from compressed measurements. In this framework, a tensor $\mathcal{X}$ is measured through a set of mode-wise measurement matrices $\mathbf{D}_n$.

Block-sparse tensor model with measurement matrices $\mathbf{D}_n$ and the definition of a tensor block.

To analyze this model, the authors introduce Mutual Block Coherence and Sub-coherence. These metrics quantify the similarity across the set of measurement matrices, enabling the optimization of the entire measurement system. This shift from analyzing individual matrices to the system as a whole is a key innovation of the paper.

Shadow Block Sparsity and T-GBOMP

A central contribution of this work is the concept of Shadow Block Sparsity. Traditional sparsity metrics often fail to capture the internal structure of a tensor. Shadow block sparsity instead quantifies how many non-zero blocks "block the field of view" along each dimension (mode) of the tensor.

The shadow extraction process used to define shadow block sparsity across different tensor modes.

This metric reveals that the arrangement of blocks significantly impacts recovery: regular arrangements are generally easier to reconstruct than scattered ones. To perform the actual recovery, the authors utilize the Tensor Generalized Block Orthogonal Matching Pursuit (T-GBOMP) algorithm. T-GBOMP serves as a theoretical benchmark to derive Exact Recovery Conditions (ERC) and noise-robustness bounds.

Experimental Validation and Key Results

The paper relies on synthetic simulations using block-sparse Gaussian and 2-PAM tensors to validate the theoretical bounds. The analytical comparisons show that the new recovery conditions are significantly tighter than existing vector-based results.

Key findings include:

  • The Power of Modes: Counter-intuitively, increasing the number of tensor modes ($n$) improves recovery robustness. High-dimensional structures provide additional "instrumental correlation" that aids in noise filtering.
  • Computable Interpretability: Unlike RIP-based theories, the MIP results are practically applicable. Engineers can use these bounds to determine the maximum sparsity level a specific measurement system can handle.
  • Performance and Convergence: In noiseless scenarios, the T-GBOMP algorithm exhibits exponential convergence. In noisy environments, the paper establishes clear Signal-to-Noise Ratio (SNR) thresholds. Simulations show that the Normalized Mean Square Error (NMSE) drops sharply once the SNR exceeds approximately 10 dB, matching the theoretical predictions.

Conclusion and Future Work

This research provides a rigorous foundation for block-sparse tensor recovery using greedy algorithms. While the results are universal and can be extended to other variants like CoSaMP, some limitations remain. The current guarantees are specific to iterative greedy methods; future work is needed to apply these MIP concepts to convex optimization-based recovery. Additionally, while the framework handles irregular block lengths, the most elegant results assume regular structures. Addressing the "curse of dimensionality" in high-mode implementations also remains a priority for future optimization.

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 Zhen 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