PaperlayerView exact revision on arXiv

Source-linked AI summary

Multipath Matching Pursuit

Suhyuk, Kwon, Jian Wang, Byonghyo Shim

arXiv:1308.4791v6cs.IT

TL;DR

Sparse recovery from compressed measurements is difficult because single-candidate greedy methods can select an incorrect support and perform poorly in noisy settings. The paper proposes MMP, which combines greedy search with a combinatoric tree of multiple candidates, and reports effective recovery in noiseless and noisy scenarios with RIP-based guarantees. It also introduces MMP-DF to control computational complexity while retaining comparable performance to breadth-first MMP.

  • Problem

    Existing greedy sparse-recovery methods can fail after an incorrect index selection and remain unsatisfactory in noisy scenarios compared with Oracle-estimator bounds.

  • Method

    MMP performs greedy-assisted combinatoric tree search over multiple promising candidates, while MMP-DF uses depth-first search and a modulo strategy to control complexity.

  • Results

    MMP effectively reconstructs sparse signals in noiseless and noisy scenarios, with RIP-based recovery guarantees and empirical performance gains over existing algorithms.

  • Takeaways & Limitations

    MMP improves the chance of selecting the true support by retaining multiple full-blown candidates until final selection, while MMP-DF offers a lower-complexity implementation.

Abstract

from arXiv · show

In this paper, we propose an algorithm referred to as multipath matching pursuit that investigates multiple promising candidates to recover sparse signals from compressed measurements. Our method is inspired by the fact that the problem to find the candidate that minimizes the residual is readily modeled as a combinatoric tree search problem and the greedy search strategy is a good fit for solving this problem. In the empirical results as well as the restricted isometry property (RIP) based performance guarantee, we show that the proposed MMP algorithm is effective in reconstructing original sparse signals for both noiseless and noisy scenarios.

I. INTRODUCTION

The paper introduces MMP to address the fragility of single-candidate greedy recovery by searching multiple promising candidates in a combinatoric tree. It provides empirical and RIP-based evidence for recovery in noiseless and noisy settings, while proposing MMP-DF to reduce complexity.

  • Motivation: Existing greedy methods can fail after selecting an incorrect index, and their noisy-scenario performance remains below Oracle-estimator bounds.OMP maintains a single candidate, while related variants improve empirical and theoretical performance but remain unsatisfactory in noisy recovery.
  • MMP approach: MMP models sparse-support selection as a combinatoric tree search and uses greedy ranking to examine multiple promising candidates before selecting the final output.The method exploits overlapping candidates to limit the growth in search size relative to exhaustive enumeration.
  • Results: MMP empirically outperforms existing sparse-recovery algorithms in both noiseless and noisy scenarios.The paper reports recovery-performance gains over existing methods across the two measurement settings.
  • Noisy recovery: Under a high-SNR condition, MMP identifies the true support and can match the performance of the Oracle least-squares estimator.The stated condition is minx̸=0 |x| ≥ c∥v∥2, where c depends on δ2K.
  • Complexity reduction: MMP-DF combines depth-first search with a modulo strategy to substantially reduce complexity while performing comparably to breadth-first MMP.The paper presents MMP-DF as a modification for strict computational-complexity control.

A. Success Condition in the First Iteration

MMP selects multiple highly correlated indices in its first iteration and establishes RIP-based conditions for retaining a correct support index. The analysis extends this guarantee to subsequent iterations through candidate expansion.

  • First iteration: MMP computes correlations between y and sensing-matrix columns, then selects L indices with largest correlation magnitudes in the first iteration.
  • First iteration: Theorem 3.5 guarantees that at least one of the L first-iteration candidates contains a correct support index under a stated RIP condition.
  • Subsequent iterations: For later iterations, MMP expands each candidate into L children and analyzes whether at least one child selects an index from the true support.
  • Subsequent iterations: The non-initial analysis bounds correlation quantities associated with remaining true indices and selected candidate indices to derive sufficient success conditions.

C. Overall Sufficient Condition

The paper combines first- and later-iteration guarantees into an overall RIP-based sufficient condition for accurate recovery by MMP. When L = K, the resulting condition is compared favorably with conditions reported for several greedy algorithms.

  • Overall condition: The overall recovery condition combines the stricter sufficient conditions established for the initial and non-initial iterations.
  • Overall condition: If βk 1 > αk N, at least one of the L indices chosen in the K-th iteration belongs to the true support T.
  • Comparison: When L = K, MMP's perfect recovery condition becomes δ2K < 0.33.
  • Comparison: Compared with CoSaMP, SP, ROMP, and gOMP conditions, MMP provides a more relaxed recovery condition and a larger guaranteed exact-recovery matrix set.

IV. RECOVERY FROM NOISY MEASUREMENTS

For noisy measurements, MMP analysis separates iteration success from final support identification. RIP- and coefficient-dependent sufficient conditions govern these stages, while exact support identification does not imply perfect signal recovery under noise.

  • Noisy-measurement analysis: In noisy recovery, MMP requires conditions for selecting true-support indices during initial and non-initial iterations, plus a separate condition for final support identification.The final minimum-residual candidate is not automatically the true support when measurements contain noise.
  • Noisy-measurement analysis: Accurate support identification in noise cannot be translated into perfect recovery of the original sparse signal because noise remains present.The paper distinguishes support recovery from exact signal reconstruction in the noisy setting.
  • Initial iteration: The first iteration succeeds when at least one of the L candidates contains a true index under the theorem’s coefficient and RIP condition.The condition is derived by comparing a lower bound on true-support correlations with an upper bound on competing correlations.
  • Initial iteration: The first-iteration sufficient condition is obtained by bounding α1 using norm inequalities and bounds on its lower and upper correlation terms.The proof proceeds through bounds denoted Bu and Bl and requires Bl > Bu.

B. Success Condition in Non-initial Iterations

For non-initial iterations, MMP uses a separate sufficient-condition analysis to ensure that at least one candidate contains a remaining true-support index. The proof constructs bounds for the relevant correlation quantity.

  • B. Success Condition in Non-initial Iterations: In the k-th non-initial iteration, at least one of the L candidates contains a true index when the theorem’s coefficient and RIP condition holds.This extends the candidate-branching guarantee beyond the first iteration.
  • B. Success Condition in Non-initial Iterations: The proof establishes non-initial iteration success by constructing lower and upper bounds for αk and applying supporting lemmas.The argument uses monotonicity of the restricted isometry constant and a lemma-based bound.

C. Condition in the Final Stage

The final-stage analysis asks when the candidate with minimum residual is the true support. In the noiseless case, zero residual identifies the true support, while noisy recovery needs an additional sufficient condition.

  • C. Condition in the Final Stage: In the noiseless scenario, the minimum-residual candidate has residual norm zero and equals the true support.The final candidate-selection rule therefore identifies the support when the noiseless conditions hold.
  • C. Condition in the Final Stage: For noisy measurements, an additional condition is required to ensure that the minimum-residual candidate becomes the true support.The theorem formulates this condition using the nonzero coefficients and the set ΩK of K-column combinations.
  • C. Condition in the Final Stage: The final-stage proof derives an upper bound on the true-support residual and compares it with competing candidates under the stated coefficient condition.The argument uses intermediate bounds and cardinality relations among Γ and T − Γ.

D. Overall Sufficient Condition

Combining iteration and final-stage conditions yields an overall sufficient condition for MMP support identification and stable noisy reconstruction. The section also introduces a serialized search variant to reduce computational cost.

  • D. Overall Sufficient Condition: MMP outputs the true support under the strictest of the conditions ensuring success in the initial, non-initial, and final stages.The conclusion follows because one generated candidate contains the true support and the minimum-residual candidate is then guaranteed to be it.
  • D. Overall Sufficient Condition: Under condition (55), the final MMP output is equivalent to the Oracle LS estimator.With prior signal and noise information, the final stage can instead produce an LMMSE estimate.
  • D. Overall Sufficient Condition: When condition (55) holds, MMP identifies the true support, removes non-support elements, and converts the underdetermined model into an overdetermined system.The paper states that this condition is sufficient for stable reconstruction of K-sparse signals in noise.
  • D. Overall Sufficient Condition: Table II maps candidate search order to the corresponding set of layer orders for L = 2 and K = 4.The mapping determines the path traced by MMP-DF.
  • D. Overall Sufficient Condition: MMP’s breadth-first search can impose burdensome and realization-dependent complexity in high-dimensional systems.This motivates a modification that controls the number of investigated candidates.
  • D. Overall Sufficient Condition: MMP-DF uses a modulo search order to serialize candidate investigation, prioritizing promising paths while limiting the number of candidates searched.Layer orders determine which ranked correlation is selected at each iteration; the first path matches OMP’s path.
  • D. Overall Sufficient Condition: MMP-DF performs comparably to MMP-BF while using far fewer candidates, producing significant computational savings according to numerical results.After Nmax candidates are found, the candidate with minimum residual magnitude is selected.

VI. NUMERICAL RESULTS

Numerical simulations evaluate MMP and related recovery algorithms in noiseless and noisy sparse-signal recovery settings. MMP improves recovery performance, while MMP-DF substantially reduces the computational complexity of MMP-BF.

  • MMP-BF is far better than conventional algorithms in critical sparsity and overall recovery behavior.
  • MMP improves with SNR and performs close to the Oracle-LS estimator, while conventional greedy algorithms show diminishing improvement.
  • For K = 30, MMP-BF and MMP-DF achieve lower miss detection and false alarm rates than existing sparse recovery algorithms.
  • MMP-DF achieves more than two order of magnitude reduction in complexity over MMP-BF and has slightly higher but comparable complexity for small K than other greedy algorithms.
  • The paper concludes that MMP is effective in both noisy and noiseless scenarios based on empirical results and RIP-based performance guarantees.

APPENDIX A PROOF OF LEMMA 3.7

The proof proceeds by applying Lemmas 3.2 and 3.3, norm inequalities, and equations (66)–(68) to bound terms in the argument.

  • The second term on the right-hand side of (62) is rewritten using the number of correct indices in s_k−1.
  • Lemma 3.3 is used to transform the first term on the right-hand side of (62).
  • The proof identifies steps (a) and (b) as consequences of Lemmas 3.2 and 3.3, respectively.
  • A norm inequality supplies equation (67), after which equations (66) and (68) are combined.

APPENDIX B PROOF OF LEMMA 3.8

The proof uses triangle and norm inequalities together with earlier lemmas, then combines intermediate bounds to obtain the desired result.

  • Lemma 3.3 and the triangle inequality are used in the derivation leading to equations (75)–(77).
  • The argument begins by applying the triangle inequality to derive an intermediate bound.
  • Equation (66) from Appendix A and Lemma 3.4 provide ingredients for subsequent bounds.
  • A norm inequality is applied before equations (82) and (83) are combined.
  • Appendix D begins its proof by recalling the definition of β_k and results from Appendix B.
  • The upper bound is combined with an earlier Lemma 3.4-based step to obtain the desired result.

APPENDIX E THE LOWER BOUND OF RESIDUAL

The supplied passages indicate that the appendix derives a lower-bound result using the RIP definition and earlier lemmas, but do not provide the complete bound.

  • The lower-bound derivation combines the RIP definition with Lemmas 3.2 and 3.3 before obtaining the desired result.
Loading 1308.4791v6…