Efficient Recovery of Block Sparse Signals via Zero-point Attracting Projection

Jingbo Liu, Jian Jin, Yuantao Gu

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:

  1. 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.
  2. 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.

Recovery rate vs. number of non-zero blocks (K)

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.

Empirical mean square deviation (MSD) vs. SNR

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

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.
BibTeX
@inproceedings{liu2012efficient,
  author = {Jingbo Liu and Jian Jin and Yuantao Gu},
  title = {{Efficient Recovery of Block Sparse Signals via Zero-point Attracting Projection}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2012},
  doi = {10.1109/icassp.2012.6288629},
}
Figure