PaperlayerView exact revision on arXiv

Source-linked AI summary

Sensing Matrix Optimization for Block-Sparse Decoding

Kevin Rosenblum, Lihi Zelnik-Manor, Yonina C. Eldar

arXiv:1009.1533v1cs.IT

TL;DR

Block-sparse signals require sensing-matrix designs that exploit structure beyond ordinary atom coherence. The paper proposes WCM, which minimizes weighted inter-block and sub-block coherence through an iterative bound-optimization algorithm. Experiments report improved reconstruction and classification over methods that do not use block structure, with the strongest results when sub-block coherence receives greater weight.

  • Problem

    Existing sensing-matrix designs improve recovery for general sparse vectors but do not exploit block-sparse structure arising from signals drawn from unions of subspaces.

  • Method

    WCM minimizes a weighted sum of total inter-block and sub-block coherence using iterative bound optimization with closed-form surrogate updates.

  • Results

    The proposed sensing matrices improve signal reconstruction and classification over previous approaches without block structure, with best recovery when sub-block coherence is weighted most heavily.

  • Takeaways & Limitations

    Nearly orthonormal equivalent-dictionary blocks provide the best reported recovery results, while equal weighting reproduces the non-block objective.

Abstract

from arXiv · show

Recent work has demonstrated that using a carefully designed sensing matrix rather than a random one, can improve the performance of compressed sensing. In particular, a well-designed sensing matrix can reduce the coherence between the atoms of the equivalent dictionary, and as a consequence, reduce the reconstruction error. In some applications, the signals of interest can be well approximated by a union of a small number of subspaces (e.g., face recognition and motion segmentation). This implies the existence of a dictionary which leads to block-sparse representations. In this work, we propose a framework for sensing matrix design that improves the ability of block-sparse approximation techniques to reconstruct and classify signals. This method is based on minimizing a weighted sum of the inter-block coherence and the sub-block coherence of the equivalent dictionary. Our experiments show that the proposed algorithm significantly improves signal recovery and classification ability of the Block-OMP algorithm compared to sensing matrix optimization methods that do not employ block structure.

I. INTRODUCTION

Compressed sensing can recover sparse representations from underdetermined measurements, but applications involving unions of subspaces require exploiting block-sparse structure. The proposed WCM framework designs sensing matrices by jointly weighting inter-block and sub-block coherence to improve block-sparse recovery and classification.

  • I. INTRODUCTION: Compressed sensing recovers sparse representations from underdetermined measurements using algorithms such as BP and OMP.Overcomplete dictionaries are used because they often provide improved sparse representations.
  • I. INTRODUCTION: Signals drawn from unions of subspaces produce block-sparse coefficients, with nonzero entries clustered according to dictionary subspaces.This structure appears in applications including face recognition and motion segmentation.
  • I. INTRODUCTION: WCM designs a sensing matrix for a provided block-sparsifying dictionary by minimizing weighted inter-block and sub-block coherence.The objective targets the Gram matrix of the equivalent dictionary and extends prior atom-coherence designs to blocks.
  • I. INTRODUCTION: The optimization replaces the weighted-coherence objective with an easier surrogate and provides a closed-form update that converges to a local solution.The surrogate is updated at each iteration using bound optimization.
  • I. INTRODUCTION: Minimizing sub-block coherence is more important than minimizing inter-block coherence, producing equivalent dictionaries with nearly orthonormal blocks.The resulting sensing matrices significantly improve signal reconstruction and classification over approaches that do not use block structure.

II. PRIOR WORK ON SENSING MATRIX DESIGN

Prior sensing-matrix design reduces coherence in the equivalent dictionary to improve sparse recovery. The reviewed approach optimizes total coherence and has a closed-form globally optimal solution under its stated assumptions, but does not exploit block structure.

  • II. PRIOR WORK ON SENSING MATRIX DESIGN: Sensing matrices are designed to improve BP and OMP recovery for a fixed sparsifying dictionary and underdetermined measurements.The dictionary may be overcomplete, with K ≥ N.
  • II. PRIOR WORK ON SENSING MATRIX DESIGN: The reviewed sensing-matrix design improves reconstruction but does not take advantage of block structure in sparse representations.The next formulation extends this objective to block-sparse decoding.
  • II. PRIOR WORK ON SENSING MATRIX DESIGN: Lower coherence in the equivalent dictionary raises the theoretical sparsity bound for recovery, although the bound is worst-case.The coherence condition motivates making the equivalent dictionary as orthogonal as possible.
  • II. PRIOR WORK ON SENSING MATRIX DESIGN: The prior objective minimizes total coherence, defined through the sum of squared inner products among equivalent-dictionary atoms, while keeping atom norms near one.This objective differs from directly minimizing the maximum coherence.
  • II. PRIOR WORK ON SENSING MATRIX DESIGN: The prior closed-form design follows an eigenvalue decomposition of DD′ and uses a sensing matrix with orthonormal transformed rows.Assuming D has full row rank, the global minimum equals K − M.
  • II. PRIOR WORK ON SENSING MATRIX DESIGN: Although the objective is nonconvex, every local minimum is also global, with local minima occurring when all singular values of Γ equal one.Other stationary points are a local maximum or saddle points.

III. SENSING MATRIX DESIGN FOR BLOCK-SPARSE

The block-sparse design problem extends prior sensing-matrix optimization by explicitly accounting for block structure. Its objective is formulated through inter-block and sub-block coherence.

  • III. SENSING MATRIX DESIGN FOR BLOCK-SPARSE: Prior sensing-matrix design does not exploit the block structure of sparse representations.This motivates a formulation specifically for block-sparse decoding.
  • III. SENSING MATRIX DESIGN FOR BLOCK-SPARSE: The proposed block-sparse objective extends the earlier coherence objective to the case of dictionary blocks.The formulation follows an introduction of basic block-sparsity concepts.

A. Block-sparse decoding

Block-sparse decoding recovers signals from under-determined measurements by exploiting coefficient support concentrated in a small number of dictionary blocks. Block-sparsifying dictionaries organize atoms into blocks corresponding to this structure.

  • A. Block-sparse decoding: Block-sparse decoding assumes x has a sufficiently block-sparse representation θ in an orthogonal block-sparsifying dictionary D.Recovery uses methods such as Block-BP and Block-OMP to approximate the block-sparsest representation from measurements.
  • A. Block-sparse decoding: A block-sparsifying dictionary concatenates column-blocks D[1], ..., D[B], with block j containing sj atoms.The coefficient vector θ is partitioned into matching blocks θ[j] of length sj.
  • A. Block-sparse decoding: A representation is k-block-sparse when its nonzero coefficients are concentrated in at most k blocks.The notation ∥θ∥2,0 ≤ k counts the number of blocks with nonzero Euclidean norm.

B. Problem definition

The sensing matrix is designed through the Gram matrix of the equivalent dictionary, balancing normalization with inter-block and within-block coherence. The weighting parameter α controls the trade-off between separating blocks and making individual blocks nearly orthonormal.

  • B. Problem definition: The design seeks a sensing matrix A for a possibly overcomplete block-sparsifying dictionary D that improves block-sparse recovery.D may have K ≥ N atoms while A maps signals into M<N measurements.
  • B. Problem definition: The equivalent dictionary E=AD is analyzed through its Gram matrix G=E′E, whose block correlations govern block-sparse recovery conditions.The cited recovery bound assumes fixed-size blocks and normalized columns.
  • B. Problem definition: Total inter-block coherence sums squared Gram-matrix entries between different blocks, while total sub-block coherence sums squared off-diagonal entries within each block.For normalized E, these correspond to squared principal-angle cosines across blocks and squared within-block atom-angle cosines.
  • B. Problem definition: The alternative spectral-norm and maximal-entry coherence definitions are more complex and yielded inferior results to the total coherence definitions.The paper attributes this to improving worst-case angles without necessarily improving average recovery ability.
  • B. Problem definition: The objective minimizes normalization penalty plus a weighted sum of total inter-block and total sub-block coherence because these terms cannot be minimized freely.The single parameter α controls the relative weight assigned to the two coherence terms.
  • B. Problem definition: α<0.5 emphasizes inter-block coherence, whereas α>0.5 emphasizes sub-block coherence and produces more orthonormal blocks at the expense of higher inter-block coherence.At α=0.5, the objective gives equal weights to the coherence terms and becomes independent of block structure.

IV. WEIGHTED COHERENCE MINIMIZATION

Weighted Coherence Minimization (WCM) minimizes the proposed sensing-design objective using bound optimization. Its surrogate updates admit closed-form minimization, and the resulting iterations converge to a local solution.

  • IV. WEIGHTED COHERENCE MINIMIZATION: WCM replaces the original objective with an easier surrogate that is updated at each optimization step.The surrogate is minimized in closed form, and iterative minimization is proved to converge to a local solution of the original problem.

A. The Weighted Coherence Minimization Algorithm

The algorithm expresses the objective through the equivalent dictionary’s Gram matrix and iteratively minimizes a surrogate based on the previous iterate. Each update has a closed-form eigenvalue-based solution and convergence is guaranteed.

  • A. The Weighted Coherence Minimization Algorithm: The objective f(G) is rewritten as a function of G=D′A′AD, the Gram matrix of the equivalent dictionary.This representation enables construction of the bound-optimization surrogate.
  • A. The Weighted Coherence Minimization Algorithm: At iteration n, the surrogate g(G,G(n)) uses the Gram matrix G(n)=D′A(n)′A(n)D from the previous sensing matrix.The surrogate satisfies the bound-optimization conditions, so iterative minimization converges to the minimum of the original objective.
  • A. The Weighted Coherence Minimization Algorithm: Each surrogate minimization is solved by selecting the top M eigenvalues and corresponding eigenvectors of a transformed matrix involving D, the dictionary covariance, and the current surrogate weights.The resulting closed-form update is characterized in Proposition 1.
  • A. The Weighted Coherence Minimization Algorithm: The algorithm initializes A(0) from the eigendecomposition of DD′ and repeatedly updates G(n), surrogate weights, and A(n+1) until convergence.The update sequence is summarized as a five-step iterative procedure.

V. EXPERIMENTS

The experiments evaluate WCM for block-sparse decoding across block sparsity levels and dictionary types, using reconstruction error, classification success, and coherence ratios. WCM improves recovery and classification over DS, especially when α exceeds 0.5 and approaches 1.

  • Experimental setup: The evaluation compares BOMP using WCM-designed sensing matrices with random matrices and the Duarte-Sapiro method.The experiments use normally distributed and structured DCT-based dictionaries.
  • Evaluation measures: The simulations measure normalized representation error, successful classification rate, and the ratio νt/µt between total sub-block and inter-block coherence.Classification success is the percentage of recognized generating subspaces.
  • Effect of α: For α < 0.5, νt/µt and representation error are high while classification success is low.This regime gives relatively greater weight to inter-block coherence.
  • Dictionary overcompleteness: The recovery improvement over DS increases as the dictionary becomes more overcomplete, across normally distributed and structured dictionaries.The comparison spans square dictionaries through highly overcomplete dictionaries.
  • Varying block sizes: For varying block sizes, the experiments use 15 blocks of size 4 and 20 blocks of size 3 with k = 2 and M = 14.Results are shown as a function of α for normally distributed and structured dictionaries.

VI. CONCLUSIONS

The paper presents WCM as a block-aware sensing-matrix design framework that minimizes weighted inter-block and sub-block coherence. Simulations indicate that emphasizing sub-block coherence yields lower reconstruction error and higher classification success than DS.

  • Framework: WCM designs a sensing matrix for a provided block-sparsifying dictionary by minimizing weighted inter-block and sub-block coherence while approximately normalizing equivalent-dictionary atoms.The objective extends coherence minimization to block-structured representations.
  • Algorithm: WCM uses bound optimization, replacing the original objective with an easier surrogate at each iteration and converging to a local solution.The iterative surrogate-based procedure is presented as a closed-form-oriented alternative to directly solving the objective.
  • Empirical conclusion: Emphasizing total sub-block coherence produces nearly orthonormal blocks, slightly increases total inter-block coherence, and outperforms DS.The observed improvements are lower reconstruction errors and higher successful-classification rates.

APPENDIX A PROOF OF CONVERGENCE

The convergence proof establishes that the surrogate objective majorizes the original objective, agrees with it at the current iterate, and has the same gradient there. These properties guarantee convergence of iterative surrogate minimization to a local minimum.

  • Majorization conditions: The surrogate g(G, G(n)) is constructed to upper-bound the original objective f(G) for every G and coincide with it at G = G(n).Minimizing the surrogate therefore decreases the original objective.
  • Majorization conditions: The convergence argument requires equality at the current iterate, upper-bounding of the original function, and equal gradients at that iterate.These are the three stated surrogate-objective constraints.
  • Proof steps: The proof verifies equality at G = G(n) directly from the surrogate definition.This establishes the first convergence condition.
  • Proof steps: The gradients of g and f coincide at G = G(n), completing the convergence proof.Together with the other two conditions, this supports convergence to a local minimum.

APPENDIX B PROOF OF PROPOSITION 1

The appendix derives a closed-form update for the surrogate minimization by transforming it into an eigenvalue problem. The next sensing matrix is constructed from the top M eigencomponents, with left-unitary ambiguity that does not affect the Gram matrix.

  • Closed-form update: The surrogate minimization is reformulated using the eigenvalue decomposition of DD′ and the transformed matrix Γ = AUΛ^1/2.This change of variables converts the update into a spectral optimization problem.
  • Closed-form update: The surrogate is minimized in closed form by selecting the top M eigenvalues and corresponding eigenvectors of the transformed objective matrix.The resulting factor is Γ = Δ_M^1/2.
  • Sensing-matrix construction: The optimal sensing matrix is A(n+1) = Δ_M^1/2Λ^-1/2U′.This update produces the next Gram matrix used by WCM.
  • Sensing-matrix construction: Left multiplication of A(n+1) by any unitary matrix leaves the resulting Gram matrix unchanged, so WCM is unaffected by this nonuniqueness.The sensing-matrix factorization is therefore not unique.
Loading 1009.1533v1…