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$.
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.
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