PaperlayerView exact revision on arXiv

Source-linked AI summary

Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation

Yonina C. Eldar, Holger Rauhut

arXiv:0904.0494v1cs.IT

TL;DR

The paper asks why jointly sparse multichannel recovery can outperform applying sparse reconstruction independently to each channel, since worst-case analysis often cannot reveal such an advantage. It develops an average-case analysis of mixed ℓ2,1 convex recovery using random signal coefficients and a weaker sufficient condition. Under mild sparsity and measurement-matrix conditions, failure probability decays exponentially with the number of channels, while the resulting bounds improve comparisons with thresholding and SOMP.

  • Problem

    Worst-case recovery conditions do not explain when jointly sparse multichannel recovery is superior to single-channel reconstruction.

  • Method

    The paper analyzes mixed ℓ2,1 recovery under a probability model for nonzero coefficients, using a weaker 2-norm sufficient condition on the sensing matrix and sparsity set.

  • Results

    Failure probability decays exponentially with the number of channels under mild sparsity and measurement-matrix conditions.

  • Takeaways & Limitations

    The bounds support multichannel recovery advantages over single-channel methods and are theoretically stronger than previous average-case bounds for thresholding and SOMP.

Abstract

from arXiv · show

In this paper, we consider recovery of jointly sparse multichannel signals from incomplete measurements. Several approaches have been developed to recover the unknown sparse vectors from the given observations, including thresholding, simultaneous orthogonal matching pursuit (SOMP), and convex relaxation based on a mixed matrix norm. Typically, worst-case analysis is carried out in order to analyze conditions under which the algorithms are able to recover any jointly sparse set of vectors. However, such an approach is not able to provide insights into why joint sparse recovery is superior to applying standard sparse reconstruction methods to each channel individually. Previous work considered an average case analysis of thresholding and SOMP by imposing a probability model on the measured signals. In this paper, our main focus is on analysis of convex relaxation techniques. In particular, we focus on the mixed l_2,1 approach to multichannel recovery. We show that under a very mild condition on the sparsity and on the dictionary characteristics, measured for example by the coherence, the probability of recovery failure decays exponentially in the number of channels. This demonstrates that most of the time, multichannel sparse recovery is indeed superior to single channel methods. Our probability bounds are valid and meaningful even for a small number of signals. Using the tools we develop to analyze the convex relaxation method, we also tighten the previous bounds for thresholding and SOMP.

I. INTRODUCTION

The paper studies recovery of jointly sparse multichannel signals and develops average-case guarantees for mixed-norm convex recovery. Its analysis shows that multichannel recovery can outperform single-channel methods under mild conditions, while tightening comparisons with thresholding and SOMP.

  • I. INTRODUCTION: Compressed sensing reconstructs sparse vectors from linear measurements that may be substantially fewer than the ambient dimension.The measurement model is y = Ax with n < N.
  • I. INTRODUCTION: Basis pursuit offers stronger uniform recovery guarantees than simple thresholding or OMP, although practical average recovery can exceed worst-case predictions.Uniform recovery can hold when n ≥ Ck log(N/k), whereas thresholding and OMP lack such guarantees in general.
  • I. INTRODUCTION: Multichannel extensions exploit jointly sparse supports, but worst-case conditions often provide no advantage over recovering each channel separately.Equal channels provide no additional support information, and several RIP or coherence conditions remain independent of the number of channels.
  • I. INTRODUCTION: Average-case analysis models signal inputs as random variables and seeks measurement-matrix conditions yielding high-probability recovery.This framework is intended to capture behavior that worst-case analysis misses when multiple channels contain complementary information.
  • I. INTRODUCTION: Under mild sparsity and matrix conditions, mixed ℓ2,1 recovery has faster exponential failure-probability decay with channels than thresholding and SOMP.The bounds remain applicable in the single-channel case, unlike earlier multichannel results, although simulations can favor SOMP because the bounds may not be tight.
  • I. INTRODUCTION: The paper analyzes mixed ℓ2,1 recovery using a weaker 2-norm sufficient condition, then derives average-case bounds for multichannel recovery.The condition generalizes earlier results and is easier to satisfy than existing ℓ1-based multichannel conditions.

III. A RECOVERY CONDITION

The paper develops a sufficient condition ensuring that mixed ℓ2,1-minimization uniquely recovers a jointly sparse matrix. The condition is established through a dual-certificate-style matrix H and supports later average-case analysis.

  • The sufficient condition generalizes a single-channel result and is weaker than existing multichannel recovery conditions.The paper introduces it specifically to derive average-case recovery results.
  • A matrix H satisfying the theorem’s two conditions guarantees that X is the unique solution of the mixed ℓ2,1 recovery program.The signal support matrix A_S must also be non-singular.
  • The proof compares the mixed ℓ2,1 norms of the true matrix X and any alternative X′ satisfying the same measurements.Its goal is to show ∥X∥2,1 < ∥X′∥2,1.
  • The argument substitutes A_S^*H = sgn(X_S) into a trace expression and applies a matrix norm inequality.The proof uses cyclicity of the trace and Lemma 3.2, whose bound involves ∥B∥2,1 and the largest column ℓ2-norm of A.
  • Strict inequality follows when the values ∥H^*A_ℓ∥2 over the alternative support are not all equal.The proof handles the equal-value case by showing at least one index lies outside the true support and has norm below one.

IV. AVERAGE CASE ANALYSIS

The section develops an average-case analysis of mixed ℓ2,1 recovery under random coefficients, showing that recovery success improves with the number of channels under conditions on A and sparsity.

  • Motivation: Worst-case multichannel recovery can provide no advantage when every channel carries the same signal.In that case, the measurements provide no additional joint-support information, and ℓ2,1 minimization fails whenever single-channel ℓ1 recovery fails.
  • Average-case model: The analysis instead models the nonzero coefficients on the joint support as random and studies recovery with high probability as a function of L.The coefficient model allows real or complex Gaussian and spherical distributions, including arbitrary positive diagonal variance scaling.
  • Recovery condition: A new sufficient condition for exact ℓ2,1 recovery is weaker than existing multichannel conditions and is based on bounds involving the 2-norm of A†Saℓ.The proof connects this norm bound to the sufficient recovery condition through concentration inequalities for random vectors on spheres.
  • Main result: The failure probability decays exponentially with the number of channels L, and the bound remains meaningful for L = 1.For complex models, the exponent uses L rather than L/2; the results therefore also cover the monochannel case.
  • Main result: More channels increase the probability of success and relax the required conditions on the measurement matrix A.The relevant admissible sparsity quantity is monotonically increasing in L, while the success probability also increases toward 1.

V. BOUNDED NORM CONDITION

This section replaces worst-case norm requirements with bounded-norm and refined RIP or coherence conditions that support average-case recovery guarantees.

  • Bounded norm condition: The average-case theorems require an upper bound on ∥A†Saℓ∥2 for indices ℓ outside the support S.Several matrix and sparsity conditions are developed to ensure this bound.
  • Recovery guarantees: The resulting conditions connect matrix norms, local RIP quantities, coherence, sparsity, and the number of channels in the recovery guarantees.These conditions are then used to establish high-probability recovery for the multichannel convex program.
  • RIP conditions: The refined RIP analysis uses δk+1 rather than the larger worst-case quantity δ2k.The condition δk+1 ≤ δ can hold when n ≥ Cδk log(N/k).
  • Random matrices: For Gaussian, Bernoulli, and spherical random matrices, local RIP control can provide the required bounded-norm condition with high probability.The result establishes probabilistic control of δ*(S) for random supports or fixed supports, depending on the proposition.
  • Coherence conditions: The coherence-based analysis uses uniformly random support sets and relates coherence to local spectral behavior.The argument relies on random-support estimates and matrix invertibility conditions derived from coherence.

A. Comparison With Worst-Case Results

Compared with worst-case guarantees, the average-case analysis permits weaker matrix conditions and substantially larger sparsity regimes while retaining exponential channel dependence.

  • Comparison With Worst-Case Results: The average-case 2-norm condition is weaker than the classical worst-case 1-norm condition.The improvement follows from using ∥x∥2 rather than ∥x∥1 in the relevant bound.
  • Comparison With Worst-Case Results: For unit-norm tight frames, average-case recovery can be ensured when k ≤ Cµ^-2, potentially as large as k ≤ Cn.The failure probability still decays exponentially in the number of channels.
  • Comparison With Worst-Case Results: The coherence-based result beats the square-root sparsity bottleneck and removes the log-factor present in RIP estimates.Coherence is also easier to estimate than restricted isometry constants.

VI. COMPARISON WITH MULTICHANNEL GREEDY ALGORITHMS

The paper compares multichannel ℓ2,1 optimization with p-thresholding and p-SOMP, presenting improved average-case performance results for the greedy methods.

  • VI. COMPARISON WITH MULTICHANNEL GREEDY ALGORITHMS: The comparison studies multichannel versions of simple thresholding and orthogonal matching pursuit in the noiseless setting.The algorithms use a greedy search to produce a k-sparse estimate from Y = AX.
  • VI. COMPARISON WITH MULTICHANNEL GREEDY ALGORITHMS: The paper slightly improves previous average-case performance results for these greedy algorithms.The comparison covers 1 ≤ p ≤ ∞.

A. Greedy Methods

The paper develops average-case guarantees for thresholding and SOMP under random coefficient models, including explicit recovery conditions and failure-probability bounds. SOMP improves slightly over prior noiseless bounds, but its bound becomes effective only when the channel count is comparable to sparsity.

  • Thresholding: 2-thresholding selects the k indices having the largest p-correlations with the multichannel measurements.Its theorem analyzes recovery under a real or complex spherical coefficient model.
  • SOMP: 2-SOMP iteratively selects the atom with maximal p-correlation to the residual and updates that residual by orthogonal projection onto selected atoms.After k iterations, the theorem guarantees recovery under matrix and sparsity conditions for Gaussian coefficient models.
  • Thresholding: Thresholding’s failure bound depends on the diagonal scaling ratio R, with larger R imposing stricter sparsity conditions and increasing error probability.This dependence distinguishes the thresholding analysis from the mixed ℓ2,1 result.
  • SOMP: The complex Gaussian model replaces L by 2L in the SOMP probability bound, while the same theorem applies to the real Gaussian model.The theorem states recovery in k steps with a probability lower bound under the stated assumptions.
  • SOMP: SOMP’s bound contains a factor 2k, so it becomes effective only when the number of channels is comparable to the sparsity k.The paper attributes this drawback likely to the analysis and notes that removing the factor is difficult.
  • SOMP: With δ = ǫ = 1/2, the SOMP condition is satisfied when µ2(Λ) ≤ 1/7, while its probability estimate behaves like 1 − N2k exp(−L/4).The corresponding SOMP condition is slightly stronger than the bounded norm condition used for mixed ℓ2,1 recovery.

B. Comparison

The paper compares mixed ℓ2,1 recovery, thresholding, and SOMP using three matrix ensembles: random spherical, Dirac–Fourier, and Alltop time-frequency dictionaries.

  • Comparison: The comparison covers a random spherical ensemble, a union of Dirac and Fourier bases, and time-frequency shifts of the Alltop window.These matrix choices are also used in the numerical experiments.
  • Comparison: For the random spherical ensemble, the mixed ℓ2,1 analysis uses a bounded-norm condition implied by δ∗(S) ≤ α.The support set has cardinality k and the columns are independent and uniformly distributed on the sphere.

1) Random spherical ensemble:

For random spherical dictionaries, the paper derives exponential failure bounds for mixed ℓ2,1 recovery, thresholding, and SOMP, then concludes that mixed ℓ2,1 has the best theoretical average-case result.

  • Random spherical ensemble: N exp(−cL) + ǫ with c ≈ 6.1137 bounds mixed ℓ2,1 failure when α = 1/4 under the stated random spherical model.This follows from the condition on the random dictionary and the real coefficient probability model.
  • Random spherical ensemble: Thresholding’s failure probability is bounded by N exp(−L/2(θ−2 − log(θ−2) − 1)) + ǫ under the corresponding comparison condition.The thresholding condition involves local 2-coherence and the same random-ensemble setting.
  • Random spherical ensemble: The three algorithms have similar recovery conditions, but thresholding additionally depends on R, making it worse when R is large.The paper identifies mixed ℓ2,1 as having the best known theoretical average-case result.
  • Random spherical ensemble: Unlike mixed ℓ2,1 and SOMP, thresholding does not require a probability model on the support set S for its performance bound.This is a scope distinction in the comparison, not a claim of uniformly better performance.

3) Time-Frequency shifts of Alltop window:

For Alltop time-frequency dictionaries, the paper compares theoretical bounds and simulations for mixed ℓ2,1, thresholding, and SOMP. The simulations show that SOMP performs best, while both SOMP and mixed ℓ2,1 improve as the number of channels increases.

  • 3) Time-Frequency shifts of Alltop window: The Alltop dictionary uses time-frequency shifts of the Alltop window, forming an n × n^2 matrix with coherence µ = 1/√n.The construction assumes n ≥ 5 is prime.
  • 3) Time-Frequency shifts of Alltop window: Thresholding’s Alltop-case failure probability is bounded by N exp(−L(θ−2 − log(θ−2) − 1)) under the stated complex probability model.The bound follows from the coherence-based condition used for this dictionary.
  • 3) Time-Frequency shifts of Alltop window: SOMP’s Alltop-case bound contains N2k exp(−A2L/2) + ǫ under the complex Gaussian coefficient model.The condition uses δ∗(S) and local 2-coherence bounds from the comparison theorem.
  • 3) Time-Frequency shifts of Alltop window: The simulations use 100 runs per parameter choice, with uniformly random supports and real or complex Gaussian coefficient models.The choice Σ = I favors thresholding, while it should not influence mixed ℓ2,1 and has only mild influence on SOMP.
  • 3) Time-Frequency shifts of Alltop window: SOMP performs better than mixed ℓ2,1 in all three experiments, while both methods show clear performance gains as L increases.For Alltop dictionaries, thresholding performs extremely poorly and is not plotted.

APPENDIX I PROOF OF THEOREM 4.2

The proof combines concentration inequalities, normalization arguments, and union bounds to establish the required probability guarantees for random measurement matrices.

  • The proof begins by extending Khintchine’s inequality to higher-dimensional complex vectors through real and imaginary parts.The stated extension applies for p ≥2 and vectors in C^k.
  • A Taylor-series identity and optimization over λ yield the theorem’s final bound.The minimizing choice is λ = 1 − u^-2.
  • For Gaussian or Bernoulli matrices, concentration bounds control deviations of A*_S A_S from the identity.The probability bound has the form 2(1 + 12/δ)^k exp(−c0/9nδ^2), with c0 = 7/18.
  • A union bound over indices outside S extends the estimate to δ*(S), with failure probability bounded by 2N(1 + 12/δ)^k exp(−c0/9nδ^2).The bound is required to be below ε under condition (33).
  • For spherical random columns, normalization by Gaussian column norms and Gaussian measure concentration establish the restricted norm bound.The resulting bound holds with probability at least 1 − 2ε when condition (33) and n ≥ 64δ^-2 log(2N/ε) are satisfied.

APPENDIX III PROOF OF THEOREM 6.2

The proof analyzes the probability that the greedy selection process chooses correct support indices, then combines concentration estimates and union bounds to obtain a recovery guarantee.

  • The analysis assumes that the currently selected set J is contained in the true support S and studies the next selection step.The residual is YM = QJY = QJASX = QJASΣΦ.
  • Concentration inequalities involving AL and C2(L) provide the probabilistic estimates used in the selection analysis.C2(L) is defined as E∥Z∥2 for a vector of L independent standard normal variables.
  • A union bound converts the stepwise estimates into an upper bound on the probability that SOMP fails.The bound is obtained after imposing the stated assumption in (p21).
  • The maximum correlation terms are simplified using projection identities and submatrix relationships involving A.The proof uses PJ aℓ = aℓ for ℓ∈J and identifies A*_{S\J}A_J as a submatrix of A*_S A.
  • SOMP selects a correct index when the correlation with an unselected true index dominates the competing correlations.The relevant correct-index quantity includes inf j∈S\J |⟨QJaj, aj⟩|^2.
  • The proof concludes that recovery succeeds when the selection condition holds for every subset J ⊂S, with probability at least 1 − N2^k exp(−ε^2A^2).The displayed conclusion states that this guarantee follows when condition (41) holds.
Loading 0904.0494v1…