# Block Sparsity¶

This section covers algorithms for recovery of block sparse signals from compressive measurements.

Related Examples

## Problem Formulations¶

The basic compressive sensing model is given by

(1)$\by = \Phi \bx + \be$

where $$\by$$ is a known measurement vector, $$\Phi$$ is a known sensing matrix and $$\bx$$ is a sparse signal to be recovered from the measurements.

We introduce the block/group structure on $$\bx$$ as

(2)$\bx = \begin{pmatrix} \bx_1 & \bx_2 & \dots & \bx_g \end{pmatrix}$

where each $$\bx_i$$ is a block of $$b$$ values. The signal $$\bx$$ consists of $$g$$ such blocks/groups. Under the block sparsity model, only a few $$k \ll g$$ blocks are nonzero (active) in the signal $$\bx$$ however, the locations of these blocks are unknown.

We can rewrite the sensing equation as:

(3)$\by = \sum_{i=1}^g \Phi_i \bx_i + \be$

by splitting the sensing matrix into blocks of columns appropriately.

Following possibilities are there:

Block Sizes:

1. All blocks have same size.

2. Different blocks have different sizes.

3. Block sizes are known.

4. Block sizes are unknown.

Intra Block Correlation:

1. Nonzero coefficients in each active block are independent of each other.

2. Nonzero coefficients in each active block exhibit some correlation.

Measurements

1. Measurements are noiseless.

2. Measurements have some noise at high SNR.

3. Measurements have high amount of noise with low SNR.

4. Measurements are real valued.

5. Measurements are quantized and hence integer valued introducing quantization noise.

Different block sparse recovery algorithms exhibit different capabilities along these choices.

Intra Block Correlation

We can model the correlation among the values within each active block as an AR-1 process. Under this assumption the matrices $$\bB_i$$ of intra block covariance take the form of a Toeplitz matrix

(4)$\begin{split}\bB = \begin{bmatrix} 1 & r & \dots & r^{b-1}\\ r & 1 & \dots & r^{b-2}\\ \vdots & & \ddots & \vdots\\ r^{b-1} & r^{b-2} & \dots & 1 \end{bmatrix}\end{split}$

where $$r$$ is the AR-1 model coefficient.

## Block Sparse Bayesian Learning¶

The Block Sparse Bayesian Learning (BSBL) algorithm and its extensions are described in [ZR12, ZR13].

Our implementation is restricted to the case of blocks with identical sizes which are known a priori. This is done to take advantage of JIT (just in time) compilation abilities of JAX that require sizes of arrays to be statically determined.

Following extensions of BSBL algorithm have been implemented:

• BSBL-EM (Expectation Maximization)

• BSBL-BO (Bound Optimization)

Methods

 bsbl_em Reconstructs a block sparse signal using BSBL-EM algorithm bsbl_em_jit Reconstructs a block sparse signal using BSBL-EM algorithm bsbl_bo Reconstructs a block sparse signal using BSBL-BO algorithm bsbl_bo_jit Reconstructs a block sparse signal using BSBL-BO algorithm bsbl_em_options Helper function to initialize options for the BSBL-EM algorithm bsbl_bo_options Helper function to initialize options for the BSBL-BO algorithm

Data Types

 BSBL_Options Options for the BSBL algorithm BSBL_State Sparse Bayesian Learning algorithm state