PaperlayerView exact revision on arXiv

Source-linked AI summary

Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery

Yonina C. Eldar, Patrick Kuppinger, Helmut Bölcskei

arXiv:0906.3173v2cs.IT

TL;DR

Compressed sensing traditionally exploits sparsity, but many signals have clustered nonzero coefficients that require a block-sparse model. This paper introduces block-coherence and block extensions of uncertainty relations and recovery methods, showing that sufficiently small block-coherence guarantees efficient recovery and can improve recovery thresholds over conventional sparsity treatment.

  • Problem

    The paper addresses recovery of signals with clustered nonzero coefficients, where treating block-sparsity as conventional sparsity ignores additional structure.

  • Method

    The paper defines block-coherence and sub-coherence, derives a block-sparse uncertainty relation, and analyzes BOMP, BMP, and mixed ℓ2/ℓ1 optimization.

  • Results

    Sufficiently small block-coherence guarantees BOMP recovery of block k-sparse signals in no more than k steps and successful mixed ℓ2/ℓ1 recovery.

  • Takeaways & Limitations

    Explicitly exploiting block-sparsity can provably yield better reconstruction properties than conventional sparse recovery.

Abstract

from arXiv · show

We consider compressed sensing of block-sparse signals, i.e., sparse signals that have nonzero coefficients occurring in clusters. An uncertainty relation for block-sparse signals is derived, based on a block-coherence measure, which we introduce. We then show that a block-version of the orthogonal matching pursuit algorithm recovers block $k$-sparse signals in no more than $k$ steps if the block-coherence is sufficiently small. The same condition on block-coherence is shown to guarantee successful recovery through a mixed $\ell_2/\ell_1$-optimization approach. This complements previous recovery results for the block-sparse case which relied on small block-restricted isometry constants. The significance of the results presented in this paper lies in the fact that making explicit use of block-sparsity can provably yield better reconstruction properties than treating the signal as being sparse in the conventional sense, thereby ignoring the additional structure in the problem.

I. INTRODUCTION

The paper studies recovery of block-sparse signals, whose nonzero coefficients occur in clusters, by explicitly incorporating that structure into recovery algorithms and performance measures. It develops block-coherence-based guarantees for uncertainty relations and efficient recovery.

  • Motivation: Block-sparse signals have nonzero coefficients occurring in clusters and arise in applications including multi-band signals, gene-expression measurements, and union-of-subspaces sampling.The model also includes multiple measurement vector problems with a shared joint sparsity pattern.
  • Related recovery guarantees: The paper complements prior mixed-norm recovery guarantees based on small block-restricted isometry constants with block-coherence-based results.Earlier results also established robustness to noise and modeling errors for the mixed ℓ2/ℓ1 method.
  • Contributions: Block-coherence and sub-coherence separately capture global dictionary properties and local properties within blocks.The paper generalizes conventional coherence to characterize block-sparsity and extends BP, MP, and OMP to the block setting.
  • Problem and approach: The paper seeks conditions on the dictionary D that enable computationally efficient recovery of block-sparse vectors from measurements y = Dx.The investigated algorithms are BOMP and a mixed ℓ2/ℓ1-optimization program called L-OPT.
  • Block-sparsity: A block k-sparse representation is unique if and only if Dg ≠ 0 for every nonzero block 2k-sparse vector g.The setup assumes fixed-length coefficient blocks and distinguishes block-sparsity from conventional sparsity.

B. Block-coherence

The paper introduces block-coherence as a global measure of inter-block similarity and sub-coherence as a local measure of within-block similarity. These quantities extend conventional coherence and support block-sparse uncertainty and recovery analysis.

  • Definition and role: Block-coherence generalizes conventional coherence to the block-sparse setting and appears in uncertainty relations and recovery thresholds.When d = 1, block-coherence reduces to conventional coherence.
  • Definition and role: Sub-coherence captures local dictionary properties within blocks, whereas block-coherence captures global properties across blocks.The paper states that both notions are necessary to characterize block-sparsity.
  • Bounds: 0 ≤ µB ≤ µ, so block-coherence is bounded above by conventional coherence.The bound follows from the block definition and the relationship between inter-block matrix entries and conventional coherence.
  • Orthonormal blocks: For dictionaries composed of orthonormal blocks, µB ≤ 1/d.Orthonormality within each block provides the additional bound.

III. UNCERTAINTY RELATION FOR BLOCK-SPARSE SIGNALS

The paper derives an uncertainty relation for block-sparse representations in two unitary bases, replacing conventional sparsity levels and coherence with block-sparsity levels and block-coherence. The resulting bound can be tighter than the conventional relation applied to the same block-sparse signal.

  • Comparison with conventional sparsity: The conventional relation counts nonzero coefficients, whereas the block relation measures the number of nonzero blocks in each representation.The paper contrasts A = ∥a∥0 and B = ∥b∥0 with block-sparsity measures.
  • Generalization: The block-sparse uncertainty relation generalizes the conventional uncertainty relation for representations in two orthonormal bases.It uses block-sparsity levels and the block-coherence between the bases.
  • Comparison with conventional sparsity: The block-sparse bound can be tighter than applying the conventional uncertainty relation after replacing coefficient sparsity by block-sparsity.The comparison uses ∥a∥0 ≤ d∥a∥2,0 and ∥b∥0 ≤ d∥b∥2,0, while µB ≤ µ may make the conventional bound looser.

A. Block-incoherent dictionaries

The paper establishes a lower bound on block-coherence and constructs basis pairs attaining it. In the corresponding block-incoherent setting, the uncertainty relation admits equality for a structured signal.

  • Lower bound: Block-coherence satisfies a lower bound analogous to the conventional coherence bound for two unitary bases.The bases are partitioned into blocks of size d, with R = L/d.
  • Achieving the bound: A DFT-based construction with an arbitrary d × d unitary matrix attains the smallest possible block-coherence.The construction uses block interactions of the form Fℓ,rUd.
  • Achieving the bound: When d = 1, the construction reduces to the maximally incoherent spike-Fourier basis pair.This recovers the familiar scalar-block case.
  • Equality case: For a structured signal x = δ√R ⊗ c, the inequalities in the block uncertainty relation are met with equality.Here c is an arbitrary nonzero length-d vector.

IV. EFFICIENT RECOVERY ALGORITHMS

The paper gives block-sparsity-aware recovery methods: mixed ℓ2/ℓ1 optimization and block-OMP, with block-MP as a special-case extension.

  • The paper studies L-OPT, a mixed ℓ2/ℓ1 optimization program, for recovering block-sparse signals.
  • It extends OMP to block-OMP (BOMP) and derives block-sparsity thresholds involving block-coherence and sub-coherence.
  • For orthonormal within-block columns, it introduces block-MP (BMP) as a block extension of MP.

A. Block OMP and block MP

This section defines BOMP and BMP and states sufficient block-coherence conditions for recovery, convergence, and improved guarantees from exploiting block structure.

  • A. Block OMP and block MP: BOMP selects the block best matched to the current residual, solves a least-squares problem over selected blocks, and updates the residual.
  • A. Block OMP and block MP: BMP applies when each block has orthonormal columns, selecting the best-matched block but directly updating rather than recomputing least squares.
  • B. Recovery conditions: Under the stated block-coherence condition, BOMP and L-OPT recover a block k-sparse vector, with BOMP selecting a correct new block at every step.
  • B. Recovery conditions: When blocks are orthonormal, exploiting block-sparsity permits the sufficient condition kd < (µ_B^-1 + d)/2, potentially allowing higher sparsity than conventional treatment.
  • B. Recovery conditions: The theorem’s initial sufficient condition depends on the unknown locations of the nonzero blocks, while a dictionary-wide condition in µ_B and ν guarantees it universally.
  • B. Recovery conditions: For orthonormal blocks, BMP selects a correct block at each step and its residual energy decays exponentially under the corresponding condition.

V. PROOFS OF THEOREMS 2, 3, AND 4

The proofs establish BOMP’s stepwise recovery by showing that residuals remain in the true block subspace and that a correct unused block is selected at every iteration.

  • The section introduces mixed block norms, block matrix norms, block submatrices, and the block-coherence norm used in subsequent proofs.
  • If the current residual lies in the true block subspace, the sufficient condition ensures that the next BOMP choice is a true block.
  • Because each new residual remains in the true subspace and previously selected subspaces are orthogonalized, BOMP selects correct blocks without repetition and recovers in k steps.

B. Proof of Theorem 2 for L-OPT

The L-OPT proof shows that the correct block representation uniquely minimizes the mixed ℓ2/ℓ1 norm under the block-coherence condition.

  • The matrix-norm and block-coherence bounds control interactions among blocks and yield the required strict inequality.
  • The proof compares the true representation with any alternative block-sparse representation of the same measurements.
  • A block outside the true support has block-coherence below one with the pseudoinverse of the true dictionary, while true-support blocks attain one.
  • Consequently, every alternative representation has a larger ℓ2/ℓ1 norm than the original block-sparse vector, so L-OPT recovers the correct vector.

D. Proof of Theorem 4

The proof establishes that BMP selects blocks from the true support and controls residual reduction through a block-sparse lemma and orthogonality.

  • Energy reduction: Lemma 5 provides a lower bound on the residual energy removed in one BMP step.The proof represents the residual as rℓ = D0cℓ and bounds the coefficient vector using block interactions.
  • Coefficient control: The coefficient bound uses the block Gram matrix, identity diagonal blocks, the block-coherence bound, and Cauchy–Schwarz inequalities.These steps control cross-block contributions while exploiting the orthonormality of the active blocks.
  • Residual support: Theorem 4 implies that BMP selects a block from D0 at every iteration.Consequently, each residual rℓ lies in R(D0).
  • Residual update: Orthogonality of the next residual to the selected block's span completes the residual-energy argument.This orthogonality is used to relate successive residual energies and conclude the proof.

VI. DISCUSSION

The discussion shows when block-sparsity improves recovery thresholds, especially after orthogonalizing blocks, while noting that suitable dictionary design can be difficult.

  • Threshold comparison: For orthonormal blocks, ν = 0 and µB ≤ µ, allowing block-sparse recovery at a potentially higher sparsity level.Nonorthonormal blocks require small ν for higher block-sparse recovery thresholds.
  • Figure 1: Figure 1 compares block-sparse and conventional recovery thresholds for R = 10 as d varies.The reported curves show that block-sparsity-aware thresholds can be significantly higher in the illustrated setting.
  • Threshold comparison: d > RM/(M − R) guarantees a higher recovery threshold for orthogonalized block-sparse recovery than conventional sparsity in the original dictionary.The guarantee applies to dictionaries satisfying Proposition 1's conditions.
  • Dictionary design: Finding dictionaries that produce significant block-sparsity gains is difficult, and partitioned i.i.d. Gaussian matrices generally do not give satisfactory results.The paper nevertheless identifies dictionaries for which significant improvements are possible.
  • Example: For the example dictionary, exploiting block-sparsity guarantees recovery at a sparsity level d times higher than conventional sparse recovery.The comparison uses the stated block-sparse threshold and the conventional threshold obtained when Ud = Id.

VII. NUMERICAL RESULTS

The numerical section evaluates whether explicitly exploiting block-sparsity improves recovery, using randomized dictionaries and block-sparse signals. Across the reported experiments, block-aware algorithms outperform their conventional counterparts, with orthogonalization providing smaller additional gains.

  • Experimental setup: Recovery performance is evaluated as a function of block-sparsity using randomly generated, column-normalized Gaussian dictionaries and Gaussian coefficients on uniformly chosen supports.The dictionaries are divided into consecutive blocks of length d.
  • Greedy recovery: BOMP significantly outperforms OMP, while BOMP-O yields slightly better performance than BOMP.The comparison is based on recovery success rates averaged over 1000 dictionary–signal realizations for each block-sparsity level.
  • Optimization-based recovery: L-OPT outperforms BP, and L-OPT-O slightly outperforms L-OPT.These results are averaged over 200 dictionary–signal realizations for each block-sparsity level.
  • Cross-method comparison: BOMP-O significantly outperforms L-OPT-O in the reported experiments.The figures compare these methods under dictionaries with different block dimensions, including L = 40, N = 400, d = 4 and L = 80, N = 160, d = 8.
  • Interpretation: The paper frames these numerical comparisons as evidence that block-sparsity can yield better reconstruction properties than conventional sparsity treatment.The broader contribution extends uncertainty relations, coherence, and recovery thresholds to block-sparse signals through block-coherence.

APPENDIX A PROOF OF LEMMA 1

The appendix establishes the relevant lemma using standard spectral-norm properties. Its proof invokes positivity, homogeneity, the triangle inequality, and submultiplicativity before deriving the stated block-norm bound.

  • Proof structure: The proof establishes equation (46) and treats equation (47) by a similar argument.The supplied proof text identifies these as the first required intermediate results.
  • Spectral-norm properties: The argument uses positivity, homogeneity, the triangle inequality, and submultiplicativity of the spectral norm.Nonnegativity and positivity follow from the spectral norm being a matrix norm; the triangle inequality and submultiplicativity are applied explicitly.
  • Final bound: The proof concludes the block mixed-norm inequality ∥Av∥2,1 ≤ ρc(A)∥v∥2,1 by applying the preceding result to a block-partitioned matrix.The argument replaces A with an L × (kd) matrix and x with v in C^kd, assuming every block has positive ℓ2 norm.
Loading 0906.3173v2…