PaperlayerView exact revision on arXiv

Source-linked AI summary

Pattern-Coupled Sparse Bayesian Learning for Recovery of Block-Sparse Signals

Jun Fang, Yanning Shen, Hongbin Li, Pu Wang

arXiv:1311.2150v1cs.ITcs.LGstat.ML

TL;DR

The paper tackles block-sparse recovery when block patterns are unknown. It introduces a pattern-coupled hierarchical Gaussian prior and EM learning procedure, reporting improved recovery performance over existing methods in experiments.

  • Problem

    Block-sparse signals contain clustered nonzero coefficients, but their block locations and sizes are often unknown during recovery.

  • Method

    A pattern-coupled hierarchical Gaussian prior links each coefficient's sparsity hyperparameter to those of its immediate neighbors, with EM learning the hyperparameters and signal.

  • Results

    The proposed algorithm achieves significant performance improvement over SBL and BP for β > 0 and lower estimation error than other methods under additive Gaussian noise.

  • Takeaways & Limitations

    The method can encourage structured-sparse solutions without requiring prior knowledge of exact block locations and sizes.

Abstract

from arXiv · show

We consider the problem of recovering block-sparse signals whose structures are unknown \emph{a priori}. Block-sparse signals with nonzero coefficients occurring in clusters arise naturally in many practical scenarios. However, the knowledge of the block structure is usually unavailable in practice. In this paper, we develop a new sparse Bayesian learning method for recovery of block-sparse signals with unknown cluster patterns. Specifically, a pattern-coupled hierarchical Gaussian prior model is introduced to characterize the statistical dependencies among coefficients, in which a set of hyperparameters are employed to control the sparsity of signal coefficients. Unlike the conventional sparse Bayesian learning framework in which each individual hyperparameter is associated independently with each coefficient, in this paper, the prior for each coefficient not only involves its own hyperparameter, but also the hyperparameters of its immediate neighbors. In doing this way, the sparsity patterns of neighboring coefficients are related to each other and the hierarchical model has the potential to encourage structured-sparse solutions. The hyperparameters, along with the sparse signal, are learned by maximizing their posterior probability via an expectation-maximization (EM) algorithm. Numerical results show that the proposed algorithm presents uniform superiority over other existing methods in a series of experiments.

I. INTRODUCTION

The paper addresses recovery of block-sparse signals when clustered support patterns are unknown, replacing independent coefficient modeling with a pattern-coupled Bayesian prior learned by EM.

  • Compressive sensing seeks to recover sparse signals from far fewer linear measurements, often represented as y = Ax + w with m < n.
  • Block-sparse signals arise when nonzero coefficients occur in clusters, as in multi-band, audio, and wavelet-transformed image signals.
  • Existing structured-recovery methods exploit known or modeled signal structures, but the exact block locations and sizes may be unavailable.
  • The proposed hierarchical Gaussian prior couples each coefficient's sparsity to its own and its immediate neighbors' hyperparameters, encouraging clusters and suppressing isolated coefficients.
  • An EM algorithm learns the coupled-model hyperparameters and estimates the signal, while the parameter β controls relevance between neighboring coefficients.
  • Unlike the proposed model, conventional sparse Bayesian learning associates hyperparameters independently with coefficients and therefore lacks a mechanism to encourage clustered sparse solutions.

III. PROPOSED BAYESIAN INFERENCE ALGORITHM

The proposed Bayesian inference method estimates block-sparse signals by learning coupled sparsity hyperparameters with an EM algorithm. Neighboring coefficients share hyperparameter dependencies, and an analytical sub-optimal update provides an efficient alternative to gradient search.

  • Posterior estimation: The MAP signal estimate is the mean of the Gaussian posterior determined by the current hyperparameters.The posterior mean and covariance are computed from the hierarchical model, with the MAP estimate equal to the posterior mean.
  • EM inference: EM learns the hyperparameters by maximizing the expected complete log-posterior, treating the signal as hidden variables.The E-step computes the Q-function from the posterior distribution of the signal.
  • M-step update: Coupled hyperparameters make the M-step nonseparable because log(α_i + βα_i+1 + βα_i−1) entangles neighboring parameters.Unlike conventional sparse Bayesian learning, the individual hyperparameter updates cannot be optimized independently.
  • M-step update: An analytical sub-optimal update replaces higher-complexity gradient search while retaining similar recovery performance in numerical results.The update uses the quantities defined through neighboring posterior means and variances and is iterated until the signal estimate changes by at most ǫ.
  • Algorithm procedure: The EM algorithm alternates posterior computation, MAP estimation, hyperparameter updating, and convergence checking.At each iteration it computes the posterior mean and covariance, updates α, and stops when ∥ˆx(t+1) −ˆx(t)∥2 ≤ǫ.
  • Interpretation: Large hyperparameters suppress corresponding signal values, supporting automatic selection of a simple sparse model through Bayesian Occam’s razor.The paper connects this mechanism to the success of conventional sparse Bayesian learning.

IV. BAYESIAN INFERENCE: UNKNOWN NOISE VARIANCE

The method is extended to unknown noise variance by jointly estimating the sparsity hyperparameters and the noise parameter within an alternating EM procedure. The resulting updates decouple the α and γ estimations.

  • Problem setting: Unknown noise variance is addressed by jointly estimating the hyperparameters α and the noise variance σ2, or equivalently γ.The known-variance assumption from the previous section is removed for this extension.
  • E-step: The alternating EM E-step computes the expected complete log-posterior of {α, γ} under the current posterior of x.The posterior remains Gaussian using the current estimates of α and γ.
  • M-step: The Q-function separates into an α-dependent term and a γ-dependent term, allowing their M-step estimations to be decoupled.The α term has the same form as in the known-variance case, with σ2 replaced by its current estimate.
  • Parameter updates: The α update uses the previously derived analytical rule, while γ is updated through the new noise-variance optimization.The paper notes that the γ update has a form similar to conventional sparse Bayesian learning but computes ρ_i differently.
  • Algorithm procedure: Each iteration computes the posterior and MAP estimate, updates α and γ, and continues until the signal estimates satisfy the prescribed tolerance.This produces the summarized sparse Bayesian learning algorithm for unknown noise variance.

A. Related Work

Prior block-sparse Bayesian models assign coefficients or groups to predefined hyperparameters, requiring structural knowledge or using expanded overlapping representations. The proposed coupled model instead relates coefficients through multiple hyperparameters and can learn block structure automatically.

  • Sparse Bayesian learning: Sparse Bayesian learning was developed to remove irrelevant basis vectors automatically and retain a small set for prediction.Earlier work applied the framework to regression, classification, sparse representation, and sparse recovery.
  • Prior block-sparse models: Block-sparse Bayesian models assign a common hyperparameter to coefficient groups sharing a sparsity pattern.A positive definite matrix can additionally capture within-group correlation.
  • Limitation of prior models: Those models require knowing the exact block sparsity pattern a priori because each coefficient is assigned to a specific hyperparameter.The requirement follows from their explicit coefficient-to-group assignment.
  • Proposed model: The proposed hierarchical model associates each coefficient with multiple related hyperparameters rather than imposing pre-specified block boundaries.This coupling has the potential to encourage block-sparse patterns while allowing the structure to be learned automatically.
  • Unknown-block prior work: An earlier unknown-block method used overlapping equal-sized blocks and an augmented measurement model with redundant columns.The prior was assigned to the augmented stacked signal rather than directly formulated for the original signal.

B. A Proposed Iterative Reweighted Algorithm

The paper also derives a reweighted ℓ1 method that couples neighboring coefficients’ weights to encourage block-sparse solutions without known block structure. Experiments report improved recovery over conventional reweighted ℓ1 and position the method as a comparison reference.

  • Motivation: Sparse Bayesian learning can be viewed as a non-separable reweighted strategy, motivating a reweighted ℓ1 method for unknown block patterns.The proposed method targets block-sparse recovery when the structure is unavailable.
  • Conventional reweighting: Conventional reweighted ℓ1 assigns weights from the previous coefficient estimates, giving larger weights to smaller estimated coefficients.This update tends to produce sparser solutions than conventional ℓ1 minimization.
  • Coupled reweighting: The modified weight for each coefficient depends on both its own previous estimate and neighboring coefficients’ previous estimates.This establishes coupling between neighboring sparsity patterns.
  • Results: Experiments show considerably improved block-sparse recovery results over the conventional reweighted ℓ1 method.The modified reweighted method also serves as a reference for comparison with the proposed Bayesian approach.

VI. SIMULATION RESULTS

The paper evaluates the proposed PC-SBL algorithm using synthetic and real data, with fixed hyperparameters a = 0.5 and b = 10^-4 throughout the experiments.

  • The experiments evaluate PC-SBL on both synthetic and real data.The proposed algorithm is also compared with existing methods in the performance studies.

A. Synthetic Data

Synthetic experiments evaluate PC-SBL across parameter choices, measurement settings, sparsity levels, noise, and comparisons with other recovery algorithms. The reported results show strong recovery performance, including the highest success rates and lower noisy-case estimation error.

  • Synthetic data generation: The synthetic signals contain K nonzero coefficients partitioned into L blocks with random sizes and locations.Nonzero blocks are placed within randomly generated super-blocks, while signal and measurement-matrix entries are randomly generated and normalized.
  • Evaluation metrics: Success rate measures noiseless recovery, while NMSE measures recovery accuracy under additive noise.A trial is successful when NMSE is no greater than 10^-4.
  • Parameter study: When β > 0, PC-SBL significantly improves performance over SBL and BP without knowing the locations or sizes of the nonzero blocks.When β = 0, PC-SBL reduces to SBL; positive β values produce similar success rates, so β = 1 is used subsequently.
  • Algorithm comparison: PC-SBL achieves the highest success rates among the compared algorithms by a considerable margin.The comparisons include EBSBL, BM-MAP-OMP, CluSS-MCMC, MRL1, and BSBL, with BSBL supplied the block size h.
  • Noisy recovery: Under additive Gaussian noise, PC-SBL yields lower estimation error than the other methods.The noisy experiments use 15 dB SNR, and the noise variance is unknown for the methods except BM-MAP-OMP.

B. Real Data

Real-image experiments reconstruct columns of the 128 × 128 Lena and Pirate images using random measurements. The proposed algorithm produces the finest image quality and reconstructed coefficients closest to ground truth among the compared methods.

  • Real data: Images are suitable evaluation data because their sparse wavelet or DCT representations tend to have clustered significant coefficients.The experiments use the Lena and Pirate images and process each image columnwise.
  • Experimental setup: Each 128 × 128 image column is sampled with a random matrix and recovered independently before image reconstruction.The experiments use m = 64 for Lena and m = 80 for Pirate.
  • Image reconstruction: The proposed algorithm presents the finest image quality among the compared reconstruction methods.The reported image comparisons are shown for the original and reconstructed Lena and Pirate images.
  • Coefficient recovery: The proposed algorithm produces reconstructed coefficients closest to the ground truth.This result is reported for the coefficient comparison in Fig. 6.

VII. CONCLUSIONS

The paper concludes that PC-SBL recovers block-sparse signals with unknown structures by coupling neighboring coefficient hyperparameters in a hierarchical Gaussian prior. EM estimation and numerical experiments support its improved recovery performance over conventional SBL.

  • The pattern-coupled hierarchical Gaussian prior models coefficient sparsity and statistical dependencies between neighboring coefficients.Each coefficient depends on its own hyperparameter and neighboring hyperparameters, encouraging clustered patterns and suppressing isolated coefficients.
  • An expectation-maximization algorithm estimates the hyperparameters together with the sparse signal by maximizing posterior probability.
  • Numerical results show significant performance improvement over conventional sparse Bayesian learning through exploitation of block-sparse structure.

NMSE

The figures present normalized MSE results and image reconstructions for evaluating recovery performance.

  • Normalized MSE is plotted against sparsity level K with m = 40, n = 100, and L = 3.
  • Together, the plots pair numerical NMSE evaluation with visual reconstruction results.
  • Fig. 4 compares the original image ‘Lena’ with reconstructed images produced by respective algorithms.
Loading 1311.2150v1…