PaperlayerView exact revision on arXiv

Source-linked AI summary

Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation

Zhilin Zhang, Bhaskar D. Rao

arXiv:1201.0862v5stat.MLstat.ME

TL;DR

Block-sparse recovery often lacks algorithms that exploit intra-block correlation and can work with little or no knowledge of block structure. The paper develops BSBL-based algorithm families for known and unknown partitions, showing that exploiting intra-block correlation improves recovery and that the framework can guide Group-Lasso extensions.

  • Problem

    Few existing algorithms consider intra-block correlation, despite its prevalence in signals and the limited prior information available to some block-sparse recovery methods.

  • Method

    The paper develops BSBL and expanded-BSBL algorithm families for known and unknown block structures, with adaptive correlation learning and a Group-Lasso hybrid.

  • Results

    The algorithms significantly outperform existing methods, and BSBL-ℓ1 exactly recovers signals with ρ = 1 for δ < 0.15 under high intra-block correlation.

  • Takeaways & Limitations

    Exploiting intra-block correlation is helpful for block-sparse recovery and suggests iterative reweighting as a promising way to enhance Group-Lasso type algorithms.

Abstract

from arXiv · show

We examine the recovery of block sparse signals and extend the framework in two important directions; one by exploiting signals' intra-block correlation and the other by generalizing signals' block structure. We propose two families of algorithms based on the framework of block sparse Bayesian learning (BSBL). One family, directly derived from the BSBL framework, requires knowledge of the block structure. Another family, derived from an expanded BSBL framework, is based on a weaker assumption on the block structure, and can be used when the block structure is completely unknown. Using these algorithms we show that exploiting intra-block correlation is very helpful in improving recovery performance. These algorithms also shed light on how to modify existing algorithms or design new ones to exploit such correlation and improve performance.

I. INTRODUCTION

The paper addresses block-sparse recovery by extending sparse Bayesian learning to exploit intra-block correlation and operate under known or unknown block structure.

  • Motivation: Existing block-sparse recovery algorithms generally require the block partition or other prior information, while few exploit intra-block correlation.Intra-block correlation is reported as common in physiological signals and images.
  • Contributions: The paper develops BSBL-based algorithms that adaptively explore and exploit intra-block correlation, with experiments showing significant improvement over competing algorithms.The authors also propose incorporating this correlation into Group-Lasso type algorithms.
  • Contributions: The proposed framework covers block-sparse signals with known block partitions and an expanded framework for completely unknown block structure.The unknown-partition algorithms are described as especially effective in noisy environments.
  • BSBL framework: Each block is modeled with a Gaussian prior whose nonnegative γi controls block sparsity and whose positive-definite Bi captures intra-block correlation.The prior assumes mutually uncorrelated blocks, while correlation is modeled within each block.
  • BSBL framework: The BSBL framework estimates γi, Bi, and λ; γi learning rules form the main algorithmic component and influence convergence speed and potential recovery performance.The noise parameter λ can strongly affect recovery when poorly estimated.
  • BSBL framework: In noiseless environments, the global minimum of the BSBL cost function leads to the true sparse solution regardless of Bi.The framework is also reported to recover less-sparse or non-sparse signals in prior work.

III. ALGORITHMS WHEN THE BLOCK PARTITION IS KNOWN

This section introduces three algorithms derived for recovery when the block partition is known.

  • Known block partition: Three algorithms are proposed under the requirement that the block partition is known.

A. BSBL-EM: the Expectation-Maximization Method

BSBL-EM derives expectation-maximization learning rules while constraining correlation matrices to improve robustness and avoid overfitting.

  • Algorithm design: BSBL-EM adapts an MMV-derived algorithm to block-sparse recovery and modifies the λ and Bi learning rules for greater robustness.
  • Noise learning: The λ learning rule sets off-block-diagonal elements of relevant matrices to zero because those elements disturb estimation in low-SNR settings.The resulting rule performs better than the earlier rule in generally noisy environments, such as SNR < 20dB.
  • Correlation learning: Parameter averaging constrains all equal-sized blocks to share one Bi, reducing overfitting from estimating a separate matrix for every block.
  • Correlation learning: A first-order AR model is used when sufficient for the application, producing a one-parameter Toeplitz correlation matrix determined by the AR coefficient and block size.The AR coefficient is estimated empirically from diagonal and sub-diagonal averages.
  • Correlation learning: For unequal block sizes, the algorithm estimates each Bi and averages the corresponding diagonal and sub-diagonal statistics across blocks.
  • Algorithm design: The resulting algorithm is called BSBL-EM.

B. BSBL-BO: the Bound-Optimization Method

BSBL-BO replaces the slow EM sparsity update with bound optimization, preserving comparable recovery performance while reducing iterations.

  • Motivation: BSBL-EM has satisfactory recovery performance but is slow because of its EM-based γi learning rule.
  • Method: BSBL-BO uses a bound-optimization γi learning rule while retaining the BSBL-EM learning rules for Bi and λ.
  • Method: The bound-optimization method upper-bounds the concave log-determinant term and minimizes a convex surrogate to decrease the original cost function.
  • Method: A second surrogate jointly optimizes γ and x through a function convex in both variables, yielding the same γ solution as the first surrogate.
  • Results: BSBL-BO requires far fewer iterations than BSBL-EM, while the two algorithms have comparable recovery performance.

C. BSBL-ℓ1: Hybrid of BSBL and Group-Lasso Type Algorithms

BSBL-ℓ1 transforms BSBL into an iterative reweighted procedure whose iterations are Group-Lasso-type problems, combining correlation learning with faster large-scale recovery.

  • BSBL-ℓ1 formulation: BSBL-ℓ1 transforms the BSBL cost function from γ-space to x-space, treating λ and Bi as fixed regularizers during the transformation.The resulting x-space formulation connects BSBL with Group-Lasso-type optimization.
  • Iterative optimization: Each BSBL-ℓ1 iteration is a standard Group-Lasso-type problem, while the overall algorithm is iterative reweighted optimization.The reweighting arises because γi depends on xi and zi, requiring repeated updates.
  • Regularizer learning: The iterative reweighted form supports automatic selection of λ and estimation of Bi from the previous block-sparse solution.Nonzero blocks from the previous iteration can be modeled as AR(1) processes for estimating correlation structure.
  • Algorithm properties: BSBL-ℓ1 adaptively learns and exploits intra-block correlation while using generally 2 to 5 iterations in noisy environments.Each iteration can be implemented with an efficient Group-Lasso-type algorithm.
  • Implementation condition: Averaging is important; without it, the algorithm may have poor performance.The passage states this as a concrete condition affecting the algorithm.

IV. ALGORITHMS WHEN THE BLOCK PARTITION IS UNKNOWN

The expanded BSBL framework handles unknown block partitions by using overlapping equal-size candidate blocks, then applies BSBL-derived algorithms to the expanded model.

  • Expanded framework: When the block partition is unknown, the expanded framework assumes equal block size h and arbitrarily located nonzero blocks.The equal-size assumption is described as not limiting for practical use, and performance is not very sensitive to h.
  • Overlapping block representation: The signal is represented using p = N − h + 1 overlapping candidate blocks, each modeled with covariance γiBi.Each candidate block begins at a successive element of x and spans h elements.
  • Expanded model: The expanded covariance construction produces a new block-sparse model that can be solved using the BSBL framework.The resulting algorithms are EBSBL-EM, EBSBL-BO, and EBSBL-ℓ1.
  • Block-size robustness: Nonzero blocks at least h elements long can be recovered through overlapping zi blocks, while shorter blocks can also be represented by an individual zi block.Thus, the assumed block size need not exactly match the true nonzero-block size.
  • Block-size robustness: Different h values lead to similar performance, although BSBL algorithms are generally more sensitive to block sizes than EBSBL algorithms.The experiments and cited prior work support this comparison.
  • Advantages: The expanded model simplifies algorithms, increases robustness in noisy environments, and facilitates exploiting intra-block correlation.The paper presents these as advantages over existing approaches that ignore intra-block correlation.

V. EXPERIMENTS

The experiments use repeated computer simulations with normalized Gaussian sensing matrices and evaluate recovery using NMSE in noise and success rate without noise.

  • Experimental protocol: Experiments were repeated for 400 trials using zero-mean random Gaussian matrices whose columns were normalized to unit ℓ2 norm.This setup was used throughout the reported experiments.
  • Performance metrics: Noisy experiments use NMSE, defined from the squared error between the estimate and generated signal normalized by the signal energy.The definition is given as ∥x̂ − xgen∥2^2/∥xgen∥2^2.
  • Performance metrics: Noiseless experiments use success rate, with a trial counted successful when NMSE ≤ 10^-5.Success rate is the percentage of successful trials among the 400 trials.
  • Implementation: BSBL-ℓ1 uses Mixed ℓ2/ℓ1 Program in noiseless experiments and Group Basis Pursuit in noisy experiments for its inner optimization.These choices solve the Group-Lasso-type subproblem in each iteration.

A. Phase Transition

Phase-transition experiments compare BSBL and non-BSBL methods for exact block-sparse recovery under changing measurement indeterminacy and intra-block correlation.

  • Experimental design: The phase-transition study varies sparsity ρ = K/M and indeterminacy δ = M/N, with each curve point requiring at least 99% success over 400 trials.Above a curve, the success rate sharply drops.
  • Correlation 0: With zero intra-block correlation, the three BSBL algorithms perform best, and BSBL-EM and BSBL-BO have identical phase-transition curves.BSBL-ℓ1 exactly recovers signals with ρ = 1 when δ ≥ 0.15 at success rates of at least 99%.
  • Correlation 0.95: With intra-block correlation 0.95, all three BSBL algorithms improve, while the four non-BSBL algorithms change little.BSBL-ℓ1 exactly recovers signals with ρ = 1 even for δ < 0.15; BSBL-EM and BSBL-BO do so when δ ≥ 0.25.
  • Interpretation: The results indicate that exploiting both block structure and intra-block correlation is crucial for the observed recovery advantage.This conclusion is stated in relation to the phase-transition results.

B. Benefit of Exploiting Intra-Block Correlation

Exploiting intra-block correlation substantially improves BSBL recovery when correlation is relatively homogeneous, while ignoring it causes little performance change across varying correlation values. This behavior differs from temporal-correlation effects in the MMV setting because the corresponding basis-matrix structure is absent here.

  • Exploiting intra-block correlation greatly improved the performance of BSBL-EM, BSBL-BO, and BSBL-ℓ1.With correlation ignored, the algorithms fixed Bi = I for every block.
  • When correlation was ignored, BSBL performance showed no obvious relation to the correlation value.Compared with MMV temporal correlation, increasing correlation did not produce an obvious performance decline in this block sparse model.
  • The different behavior from MMV temporal correlation is associated with the absence of the Kronecker-product basis-matrix structure in this block sparse model.In the vectorized MMV model, the basis matrix has the specific form Φ ⊗ I_L; that structure is not present here.
  • In heterogeneous-correlation experiments, exploiting correlation produced a significant benefit when block correlations varied least, but the benefit disappeared under the greatest variation.Case 3 sampled correlations from 0.7 to 1, whereas Case 1 sampled them from -1 to 1.

C. Performance in Noisy Environments

Across noise levels, the BSBL algorithms substantially outperformed non-BSBL methods in block-sparse recovery. BSBL-EM and BSBL-BO performed nearly identically to the oracle, while BSBL-ℓ1 showed software-dependent behavior at extreme SNRs.

  • All three BSBL algorithms exhibited significant performance gains over non-BSBL algorithms across the tested noise levels.The experiment used M = 128, N = 512, 64 blocks of size 8, and seven nonzero blocks with correlations from 0.8 to 1.
  • BSBL-EM and BSBL-BO had performance curves nearly identical to the oracle.
  • BSBL-ℓ1 had slightly poorer performance at low and high SNR because of sub-optimal default parameters in the Group Basis Pursuit software.The reported phenomenon disappeared when other software was used.

D. Performance When Block Partition Is Unknown

When block partition was unknown, the proposed BSBL-based algorithms outperformed StructOMP, CluSS-MCMC, and BM-MAP-OMP. BSBL-EM and EBSBL-BO achieved similar performance with assumed block sizes h = 4 and h = 8.

  • Figure 4 reports performance comparisons for recovery with unknown block partition.
  • The proposed algorithms outperformed StructOMP, CluSS-MCMC, and BM-MAP-OMP when the block partition was unknown.The noisy experiment used a 192 × 512 matrix, 48 total nonzero elements, correlations from 0.8 to 1, and SNR = 15 dB.
  • For both BSBL-EM and EBSBL-BO, setting h = 4 or h = 8 led to similar performance.The tested signals had nonzero blocks with random sizes and random non-overlapping locations.
Loading 1201.0862v5…