PaperlayerView exact revision on arXiv

Source-linked AI summary

Block-Sparse Recovery via Convex Optimization

Ehsan Elhamifar, Rene Vidal

arXiv:1104.0654v3math.OCcs.CVcs.IT

TL;DR

Block-sparse recovery seeks representations using the fewest dictionary blocks, including settings where blocks are redundant and larger than their underlying subspaces. The paper proposes two convex program classes with subspace-coherence guarantees, and reports improved face-recognition performance, including a 5% to 10% recognition-rate advantage for ℓq/ℓ1 over Pℓq/ℓ1.

  • Problem

    Existing block-sparse recovery theory largely assumes non-redundant blocks, while applications such as face recognition use blocks whose atom counts can exceed subspace dimensions.

  • Method

    The paper studies Pℓq/ℓ1 and P′ℓq/ℓ1 for q ≥1, allowing redundant blocks and arbitrary lengths, and derives conditions using mutual and cumulative subspace coherence.

  • Results

    ℓq/ℓ1 has 5% to 10% higher recognition rate than Pℓq/ℓ1 in face-recognition experiments.

  • Takeaways & Limitations

    Treating face recognition as block-sparse recovery can significantly improve recognition performance, and P′ℓq/ℓ1 outperforms state-of-the-art face-recognition methods on a real-world dataset.

  • Takeaways & Limitations

    The paper identifies analysis of the ℓq/ℓ1 family and its unconstrained Lasso-type variations as an open avenue for further research.

Abstract

from arXiv · show

Given a dictionary that consists of multiple blocks and a signal that lives in the range space of only a few blocks, we study the problem of finding a block-sparse representation of the signal, i.e., a representation that uses the minimum number of blocks. Motivated by signal/image processing and computer vision applications, such as face recognition, we consider the block-sparse recovery problem in the case where the number of atoms in each block is arbitrary, possibly much larger than the dimension of the underlying subspace. To find a block-sparse representation of a signal, we propose two classes of non-convex optimization programs, which aim to minimize the number of nonzero coefficient blocks and the number of nonzero reconstructed vectors from the blocks, respectively. Since both classes of problems are NP-hard, we propose convex relaxations and derive conditions under which each class of the convex programs is equivalent to the original non-convex formulation. Our conditions depend on the notions of mutual and cumulative subspace coherence of a dictionary, which are natural generalizations of existing notions of mutual and cumulative coherence. We evaluate the performance of the proposed convex programs through simulations as well as real experiments on face recognition. We show that treating the face recognition problem as a block-sparse recovery problem improves the state-of-the-art results by 10% with only 25% of the training data.

I. INTRODUCTION

Block-sparse recovery targets representations using few coefficient blocks rather than few individual atoms. The paper motivates convex relaxations and coherence-based conditions for dictionaries with varied block structures.

  • Recovery of Sparse Signals: Finding the sparsest representation minimizes the number of nonzero coefficients, but the corresponding ℓ0 optimization problem is NP-hard.Classical sparse recovery formulates this as minimizing the ℓ0 quasi-norm under y = Bc.
  • Recovery of Sparse Signals: Coherence and restricted-isometry conditions can establish equivalence between tractable convex programs and combinatorial sparse or block-sparse formulations.Classical results use mutual or cumulative coherence and RIP; block extensions provide analogous guarantees for Pℓ2/ℓ1.
  • Recovery of Block-Sparse Signals: Block sparsity counts nonzero blocks, so a block-sparse vector need not be sparse and a sparse vector need not be block-sparse.Figure 1 contrasts both cases: two nonzero blocks can contain 200 nonzero elements, while 100 nonzero blocks can contain only 50 nonzero elements.
  • Recovery of Block-Sparse Signals: Block-sparse recovery instead minimizes the number of nonzero coefficient blocks, and its nonconvex formulation is likewise NP-hard.The objective counts nonzero blocks and requires searching over possible block selections.
  • Recovery of Block-Sparse Signals: For q ≥1, Pℓq/ℓ1 is a convex relaxation that can be solved efficiently and includes ordinary ℓ1 recovery when q = 1.The q = 2 case has been studied previously, while the paper considers arbitrary q ≥1.
  • Recovery of Block-Sparse Signals: Existing block-sparse guarantees largely assume non-redundant blocks, whereas applications such as face recognition can use redundant blocks with more atoms than subspace dimension.Prior work also commonly assumes linearly independent columns and, in some cases, equal block lengths.

C. Paper Contributions

The paper develops a unified convex-recovery framework for block-sparse dictionaries with arbitrary block lengths and both redundant and non-redundant blocks. It introduces subspace-coherence conditions and evaluates the resulting programs on synthetic data and face recognition.

  • Paper Contributions: The paper analyzes two convex program classes, Pℓq/ℓ1 and P′ℓq/ℓ1, for q ≥1.These relax two corresponding nonconvex objectives for block-sparse recovery.
  • Paper Contributions: Unlike prior work, the framework permits linearly dependent atoms within blocks and arbitrary, different block lengths.It therefore covers both non-redundant and redundant blocks without separating the theoretical treatments.
  • Paper Contributions: Mutual and cumulative subspace coherence extend mutual and cumulative coherence from one-dimensional atoms to multidimensional subspaces.Cumulative subspace coherence yields weaker recovery conditions than mutual subspace coherence, although it is harder to compute.
  • Paper Contributions: The proposed programs are evaluated on synthetic data and face recognition, where P′ℓq/ℓ1 outperforms state-of-the-art face-recognition methods on a real-world dataset.The paper reports that treating face recognition as block-sparse recovery significantly improves recognition performance.

II. PROBLEM SETTING

The problem setting models a dictionary as blocks whose columns span subspaces, allowing redundant or non-redundant blocks. Inter-block geometry is characterized by mutual and cumulative subspace coherence, while intra-block structure is captured by restricted-isometry quantities.

  • Problem Setting: Each dictionary block spans a subspace, and blocks may be non-redundant or redundant depending on whether atom count equals or exceeds subspace dimension.The framework allows arbitrary block lengths and does not require linearly independent columns.
  • Problem Setting: The subspaces are assumed disjoint when uniqueness of the blocks in a block-sparse representation is required.Disjoint subspaces intersect only at the origin.
  • Problem Setting: Mutual subspace coherence is the largest coherence between any pair of subspaces and can be computed from orthonormal subspace bases.It reflects the most extreme inter-subspace correlation.
  • Problem Setting: Cumulative subspace coherence measures the maximum total coherence between one subspace and a collection of k others.For k = 1, it equals mutual subspace coherence; it can provide weaker recovery conditions but is generally more costly to compute.
  • Problem Setting: Subspace coherence reduces to ordinary mutual or cumulative coherence for one-dimensional subspaces.It is also related to the cosine of the smallest principal angle between subspaces.
  • Problem Setting: The intra-block constants ϵq and σq characterize restricted-isometry behavior within blocks for generic q and include non-redundant-block quantities as special cases.For non-redundant blocks, ϵq and σq coincide; when q = 2, ϵ2 matches the one-block restricted-isometry constant.

III. UNIQUENESS OF BLOCK-SPARSE REPRESENTATION

The paper establishes when the active blocks and their reconstructed subspace vectors are uniquely identifiable, including dictionaries with redundant blocks. Uniqueness is characterized through rank and block-sparse nullspace conditions, with a practical checking limitation.

  • Redundant blocks: Uniqueness of reconstructed vectors is weaker than uniqueness of coefficient blocks when a dictionary block is redundant.A vector in a redundant block subspace can have multiple coefficient representations.
  • Uniqueness conditions: For generic dictionaries, uniqueness of active blocks and reconstructed vectors holds if no nonzero 2k-block-sparse vector lies in the nullspace of a full-rank block subdictionary.This formulation accommodates both non-redundant and redundant blocks.
  • Uniqueness conditions: Disjoint subspaces are necessary for uniquely recovering the blocks, because any two active subspaces must intersect only at the origin.This follows directly from the k = 1 case of the uniqueness condition.
  • Uniqueness conditions: A k-block-sparse representation is uniquely determined by the active blocks and vectors under a rank condition applying to every admissible dictionary matrix.The condition is rank(B_n) ≥ 2k for every B_n in the specified matrix class.
  • Practical scope: The rank condition is not directly checkable because it requires considering every admissible vector choice, motivating later efficiently checkable coherence-based sufficient conditions.The paper assumes a unique representation when analyzing convex recovery.

IV. BLOCK-SPARSE RECOVERY VIA Pℓq/ℓ1

The paper formulates block-sparse recovery through nonconvex mixed-norm programs and studies convex ℓq/ℓ1 recovery for arbitrary, including redundant and unequal-length, blocks. It derives equivalence conditions using subspace coherence and shows that cumulative coherence yields weaker sufficient conditions than mutual coherence.

  • Formulation: The block-sparse representation problem seeks the minimum number of nonzero coefficient blocks, while its ℓq/ℓ1 relaxation is designed for efficient recovery.The original block-counting formulation is NP-hard for q ≥ 1.
  • General framework: The unified framework analyzes equivalence of Pℓq/ℓ1 and Pℓq/ℓ0 for both non-redundant and redundant blocks.It does not impose equal block lengths or linear independence within blocks.
  • Recovery guarantee: Theorem 1 gives necessary and sufficient conditions for Pℓq/ℓ1 to recover every uniquely represented k-block-sparse signal.The condition compares minimum mixed-norm representations supported on active and complementary block sets.
  • Recovery guarantee: Proposition 3 provides a coherence-based sufficient condition under which Pℓq/ℓ1 and Pℓq/ℓ0 are equivalent for uniquely represented signals.Its bound depends on intra-block parameters, inter-block cumulative subspace coherence, and q.
  • Proof mechanism: Under the proposition's sufficient condition, the active-block representation has smaller mixed-norm cost than any representation using complementary blocks, yielding convex recovery.This inequality establishes the condition required by the recovery theorem.
  • Coherence conditions: Cumulative subspace coherence produces weaker recovery conditions than mutual subspace coherence, including for non-redundant blocks with q = 2.The comparison is stated relative to the corresponding mutual-coherence and block-coherence conditions.

V. BLOCK-SPARSE RECOVERY VIA P ′

This section studies P′ℓq/ℓ1, which penalizes reconstructed block vectors rather than coefficient blocks, and gives recovery conditions for non-redundant and redundant dictionaries. Its conditions can be weaker than those for Pℓq/ℓ1, and experiments generally favor P′ℓ2/ℓ1.

  • Convex relaxation: The convex relaxation P′ℓq/ℓ1 replaces the non-convex count of reconstructed vectors with a sum of their ℓq norms.The program is convex for q ≥ 1.
  • Formulation: P′ℓq/ℓ0 minimizes the number of nonzero reconstructed vectors B[i]c[i], rather than the number of nonzero coefficient blocks.For non-redundant blocks, this also yields the minimum number of nonzero coefficient blocks; with redundant blocks, nullspace coefficients can remain nonzero without changing reconstructed vectors.
  • Recovery guarantees: Under uniqueness, P′ℓq/ℓ1 is equivalent to P′ℓq/ℓ0 when the stated sufficient conditions involving subspace coherence and norm constants hold.The paper provides theorem, proposition, and corollary conditions, including versions based on cumulative subspace coherence.
  • Recovery guarantees: The sufficient conditions for P′ℓq/ℓ1 and P′ℓq/ℓ0 do not depend on whether dictionary blocks are redundant or non-redundant.This contrasts with the conditions for Pℓq/ℓ1 and Pℓq/ℓ0.
  • Empirical comparison: P′ℓ2/ℓ1 is generally more successful than Pℓ2/ℓ1 in the experimental results, although sufficient conditions alone cannot establish superiority.The paper explicitly distinguishes empirical performance from comparison of sufficient conditions.

VI. CORRECTING SPARSE OUTLYING ENTRIES

The paper extends block-sparse recovery to signals corrupted by sparse outlying entries. It augments the dictionary with identity atoms so convex programs can recover both contributing dictionary blocks and sparse errors.

  • Motivation: Corrupted signals may not lie exactly in the range of a few dictionary blocks, for example because of face-image occlusions.Sparse outlying entries are also relevant to motion-segmentation feature trajectories.
  • Model: Appending the identity matrix creates a block-structured dictionary whose blocks represent both the original dictionary and individual error atoms.The observed signal then has a block-sparse representation involving a few original blocks and a few identity atoms.
  • Recovery: The convex programs can recover a block-sparse representation of the corrupted signal when the earlier sufficient conditions hold for the augmented dictionary.For identity blocks of length one, the error penalty becomes the ℓ1 norm of the error vector.
  • Recovery: The framework provides theoretical guarantees for recovering the block-sparse representation of a corrupted signal and eliminating the error.This extends the proposed convex programs beyond exactly uncorrupted block-sparse signals.

VII. EXPERIMENTAL RESULTS

The paper evaluates its two classes of convex programs on synthetic data and in face recognition. These experiments assess block-sparse recovery in both controlled and real settings.

  • Evaluation: Performance is evaluated through synthetic experiments and real experiments on face recognition.

A. Synthetic Experiments

Synthetic experiments compare the two convex-program classes across block-sparsity levels, using non-redundant and redundant random blocks. P′ℓq/ℓ1 generally produces lower errors and remains effective at higher sparsity levels.

  • Experimental setup: The experiments generate random disjoint subspaces and blocks with either m = d or m = 2d atoms per block.Signals use randomly selected k-block-sparse supports and Gaussian coefficients.
  • Metrics: Performance is measured by reconstruction, block-contribution, and, for non-redundant blocks, coefficient-recovery errors.The reconstruction error is zero when the recovered block contributions match the true contributions.
  • Experimental setup: 20,000 trials average the errors over 200 block sets and 100 signals per set for each fixed block-sparsity level.
  • Non-redundant blocks: For non-redundant blocks, P′ℓq/ℓ1 has lower reconstruction, block-contribution, and coefficient-recovery errors than Pℓq/ℓ1 at every tested block-sparsity level.
  • Non-redundant blocks: For non-redundant blocks, Pℓq/ℓ1 degrades significantly above block-sparsity level 3, whereas P′ℓq/ℓ1 maintains high performance over a wider range.
  • Redundant blocks: For redundant blocks, P′ℓq/ℓ1 again outperforms Pℓq/ℓ1 across block-sparsity levels, while redundancy improves Pℓq/ℓ1 but worsens it at higher sparsity relative to non-redundant blocks.
  • Choice of q: Across both figures, q = ∞ performs worse or degrades earlier than q = 1, 2, while q = 2 generally performs better than q = 1.

B. Face Recognition

The face-recognition experiments model each subject’s images as a low-dimensional subspace and evaluate block-sparse convex programs under reduced training data and corrupted observations. The proposed P′ℓq/ℓ1 programs are more robust than Pℓq/ℓ1, while sparse-representation methods outperform nearest-subspace and SVM baselines.

  • Each subject’s face images lie close to a 9-dimensional subspace under the Lambertian assumption, forming a union of subject-specific subspaces.
  • The experiments evaluate both convex-program classes for q ∈ {1, 2}, use an error-tolerant constraint with δ = 0.05, and classify test images by the recovered identity.
  • The Extended Yale B experiments use 2,414 images from 38 individuals, with dimensionality reduced to D = 132 and m ∈ {9, 18, 25, 32} training images per subject.
  • Sparse-representation methods outperform nearest-subspace and linear SVM methods because face images have a multi-subspace structure and corrupted observations.
  • P′ℓq/ℓ1 almost always outperforms Pℓq/ℓ1, with the difference becoming clearer as the number of training images per class decreases.
  • The paper concludes that it analyzes both convex-program families for non-redundant and redundant blocks, while stability under signal noise and extensions to mixed ℓq/ℓp methods remain open.

APPENDIX

The appendix develops contradiction-based arguments linking block-sparse uniqueness and rank conditions, then derives a recovery bound by combining norm and coherence inequalities. The proof establishes the stated sufficient result through substitutions into earlier inequalities.

  • A nonzero 2k-block-sparse null vector is shown to contradict uniqueness of k-block-sparse representations, and conversely distinct representations produce such a null vector.
  • Replacing each block by a full-column-rank basis preserves block ranks and converts the null-vector argument into a rank condition for a selected subdictionary.
  • The proof bounds column norms and pairwise interactions of matrices associated with selected and complementary blocks.
  • Substituting the preceding bounds into the target inequality yields the displayed sufficient recovery expression involving α, β, and ζ_k.

E. Proof of Proposition 4

The proof of Proposition 4 constructs vectors from the active and inactive blocks, applies the relevant coherence-set bounds, and compares their ℓ1 norms. The resulting inequality implies the sufficient condition needed for P′ℓq/ℓ1 recovery.

  • For active blocks, the proof defines unit vectors s_i and coefficients a_i from the solution of optimization program (52), assigning zero coefficients when the reconstructed block vector vanishes.
  • The active-block matrix B_k belongs to the prescribed coherence class B_ϵ′q(Λ_k), while the complementary matrix B_bk satisfies the analogous inactive-block condition.
  • The proof performs the same vector-and-coefficient construction for the solution of optimization program (53) on the complementary blocks.
  • When the stated right-hand side is strictly less than one, the derived inequality gives ∥a_k∥_1 < ∥a_bk∥_1.
  • This ℓ1 comparison satisfies the condition of Theorem 2 and establishes the proposition’s sufficient recovery condition for P′ℓq/ℓ1.
Loading 1104.0654v3…