Abstract
In this paper, we consider compressed sensing (CS) of block-sparse signals, i.e., sparse signals that have nonzero coefficients occurring in clusters. An efficient algorithm, called zero-point attracting projection (ZAP) algorithm, is extended to the scenario of block CS. The block version of ZAP algorithm employs an approximate $l_{2,0}$ norm as the cost function, and finds its minimum in the solution space via iterations. For block sparse signals, an analysis of the stability of the local minimums of this cost function under the perturbation of noise reveals an advantage of the proposed algorithm over its original non-block version in terms of reconstruction error. Finally, numerical experiments show that the proposed algorithm outperforms other state of the art methods for the block sparse problem in various respects, especially the stability under noise.
Introduction
In the field of Compressed Sensing (CS), the objective is to reconstruct a high-dimensional sparse signal from a limited number of linear measurements. While standard CS focuses on signals with randomly scattered non-zero entries, many practical signals—such as those in MRI, wireless communications, and sensor networks—exhibit block sparsity, where non-zero coefficients appear in clusters.
Reconstructing these signals involves solving an NP-hard $l_0$ norm minimization problem. Existing solutions typically fall into two categories: convex relaxations (like $l_{2,1}$ optimization), which are accurate but computationally intensive, and greedy pursuits (like Block Orthogonal Matching Pursuit, or BOMP), which are fast but sensitive to noise. This paper introduces the Block Zero-point Attracting Projection (BZAP) algorithm to bridge this gap, offering a solution that is both computationally efficient and robust to noise.
The BZAP Algorithm
The BZAP algorithm extends the "Zero-point Attracting Projection" framework to exploit block structures. It utilizes a two-step iterative process:
- Cost Function Approximation: BZAP replaces the discrete $l_{2,0}$ norm with a smooth, differentiable function $F_\alpha$. This function is designed to be linear near zero to "attract" small values toward zero while remaining constant for larger values.
- Zero-Point Attraction and Projection: In each iteration, the estimate moves along the negative gradient of the cost function to push small blocks toward zero. Subsequently, a projection step maps the estimate back onto the feasible solution space defined by the measurements $y = Ax$.
Unlike the original ZAP, which treats signal elements individually, BZAP treats each block as a single unit. The attraction is based on the $l_2$ norm of the entire block, allowing the algorithm to leverage the underlying cluster structure of the signal.
Experimental Evaluation
The algorithm was evaluated using synthetic datasets with a $40 \times 100$ Gaussian measurement matrix and signals with a block size of $D=4$. Performance was compared against BOMP, $l_{2,1}$ optimization, and the standard ZAP algorithm.
Recovery Capacity
In noiseless simulations, BZAP demonstrated a significantly higher recovery capacity than its counterparts. As the number of non-zero blocks ($K$) increases, BZAP maintains a high probability of exact reconstruction long after other methods begin to fail.
Noise Robustness and Stability
A key theoretical and empirical finding is BZAP's superior stability under noise. Theoretical analysis suggests that BZAP's reconstruction error bound is lower than that of the original ZAP by a factor of approximately $1/\sqrt{D}$. Numerical results confirm that BZAP's Mean Square Deviation (MSD) closely tracks the "oracle estimator"—the theoretical limit achievable if the support of the signal were known a priori.
Conclusion
BZAP provides an efficient and robust framework for block-sparse signal recovery. By utilizing a smooth approximation of the $l_0$ norm and exploiting block structures, it achieves oracle-like performance in noisy environments and higher recovery rates than standard greedy or convex methods. Future work will focus on addressing potential local minima through global optimization strategies and validating the algorithm on real-world structured matrices found in radar and medical imaging.
Summary updated