PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized Orthogonal Matching Pursuit

Jian Wang, Seokbeop Kwon, Byonghyo Shim

arXiv:1111.6664v2cs.IT

TL;DR

Recovering sparse signals from underdetermined compressed measurements can be computationally demanding. The paper introduces gOMP, an OMP extension that selects multiple high-correlation indices per iteration, and shows exact-recovery conditions together with competitive empirical recovery and complexity.

  • Problem

    Sparse recovery from compressed measurements requires reconstruction of K-sparse signals from an underdetermined system, motivating efficient alternatives to computationally burdensome approaches.

  • Method

    gOMP generalizes OMP by selecting N largest-magnitude correlations per iteration, updating the support, and then computing a least-squares estimate.

  • Results

    Under δ_NK < √N/(√K + 3√N) for K > 1, gOMP exactly recovers any K-sparse signal within K iterations.

  • Takeaways & Limitations

    gOMP combines recovery performance comparable to ℓ1-minimization with fast processing and competitive computational complexity.

Abstract

from arXiv · show

As a greedy algorithm to recover sparse signals from compressed measurements, orthogonal matching pursuit (OMP) algorithm has received much attention in recent years. In this paper, we introduce an extension of the OMP for pursuing efficiency in reconstructing sparse signals. Our approach, henceforth referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple $N$ indices are identified per iteration. Owing to the selection of multiple ''correct'' indices, the gOMP algorithm is finished with much smaller number of iterations when compared to the OMP. We show that the gOMP can perfectly reconstruct any $K$-sparse signals ($K > 1$), provided that the sensing matrix satisfies the RIP with $δ_{NK} < \frac{\sqrt{N}}{\sqrt{K} + 3 \sqrt{N}}$. We also demonstrate by empirical simulations that the gOMP has excellent recovery performance comparable to $\ell_1$-minimization technique with fast processing speed and competitive computational complexity.

I. INTRODUCTION

Compressive sensing recovers sparse signals from underdetermined measurements, but conventional ℓ1 minimization and OMP can be computationally demanding. The paper introduces gOMP, which selects multiple high-correlation indices per iteration and provides recovery guarantees, empirical performance, and complexity analysis.

  • Motivation: Compressive sensing seeks to recover K-sparse vectors from fewer linearly transformed measurements than the signal dimension.The measurement system is underdetermined, so sparsity and conditions on the sensing matrix enable reconstruction.
  • Motivation: O(n^3) complexity makes ℓ1-minimization burdensome for many applications, while OMP complexity increases with sparsity as approximately 2Kmn + 3K^2m.OMP may be less suitable when the recovered signal is not very sparse.
  • Proposed method: gOMP extends OMP by selecting the N largest-magnitude correlations per iteration, with OMP recovered as the special case N = 1.Unlike thresholding or regularization variants, gOMP directly modifies the identification step and adds selected indices to the support set before least-squares updating.
  • Experiments and extensions: Empirical simulations show gOMP recovery performance comparable to ℓ1-minimization, CoSaMP, and StOMP, while targeting faster execution and competitive complexity.The paper also analyzes noisy measurements using an upper bound on ℓ2 reconstruction distortion.
  • Theoretical analysis: The paper develops an RIP-based sufficient condition for gOMP to exactly recover any K-sparse vector within K iterations.The analysis combines conditions for selecting at least one correct index in the initial and subsequent iterations.

II. GOMP ALGORITHM

gOMP extends OMP by selecting N highest-correlation indices per iteration, then applying least-squares estimation and residual updates. Simulations report competitive recovery and lower runtime growth than OMP as sparsity increases.

  • Algorithm: gOMP selects N indices with the largest residual correlations and adds them to the estimated support set each iteration.When N = 1, gOMP reduces to OMP.
  • Algorithm: The algorithm computes a least-squares estimate on the current support and updates the residual by projecting measurements onto the orthogonal complement of the selected columns.Iterations stop at k_max = min(K, m/N) or when the residual norm falls below a preset threshold.
  • Recovery behavior: At least one correct index per iteration is sufficient for perfect recovery, while selecting multiple correct indices usually reduces the required iterations below K.The final support may include incorrect indices without affecting recovery because coefficients outside the true support are zero.
  • Recovery performance: gOMP has larger critical sparsity than ROMP, OMP, and StOMP for Gaussian signals, and slightly outperforms LP and CoSaMP in that setting.For PAM signals, the overall behavior is similar, except that ℓ1-minimization performs better than gOMP.
  • Runtime: When K is large, gOMP runtime increases linearly and more slowly than OMP and CoSaMP; gOMP with N = 6 or 9 is among the fastest tested algorithms.LP runtime is omitted because it is more than an order of magnitude higher than the other algorithms.

III. RIP BASED RECOVERY CONDITION ANALYSIS

The recovery analysis derives RIP-based sufficient conditions for gOMP success across initial and later iterations. It relies on RIP monotonicity and standard consequences for restricted submatrices and disjoint supports.

  • Analysis strategy: The analysis combines conditions for success at the first iteration and at non-initial iterations to obtain a sufficient condition for perfect recovery.Success means that at least one correct index is selected in an iteration.
  • RIP tools: RIP is monotone in its order: if K1 ≤ K2, then δK1 ≤ δK2.This property is called monotonicity of the isometry constant.
  • RIP tools: When the relevant RIP constant is below 1, the analysis applies norm and inner-product bounds to vectors supported on restricted or disjoint index sets.These bounds are supplied through consequences of RIP for one set and for two disjoint sets.

A. Condition for Success at the Initial Iteration

The initial-iteration analysis defines success as selecting at least one true support index among the N chosen indices. A theorem gives an RIP-based sufficient condition for this event.

  • Initial-iteration condition: gOMP succeeds in the first iteration when at least one of its N selected indices belongs to the true support.Theorem 3.4 states a sufficient condition for this event when x is K-sparse and K ≥ N.
  • Proof idea: The proof compares the average correlation power of the N best selected columns with the average correlation power of the K true columns.RIP consequences are then used to bound the two sides of this comparison.
  • Proof idea: If no correct index is selected initially, the resulting correlation bound contradicts the bound obtained for the selected indices under the stated RIP condition.Thus at least one correct index must be selected in the first iteration.
  • Notation: The set diagram represents the ambient index set Ω, the true support T, and the estimated support Λk.These sets organize the distinction between correct, selected, and remaining indices used in the analysis.

B. Condition for Success in Non-initial Iterations

For later iterations, the analysis bounds correlations with remaining incorrect and correct columns. If the largest remaining-correct correlation exceeds the N-th incorrect correlation, gOMP selects a correct index.

  • Setup: The non-initial analysis assumes previous iterations succeeded and that not all correct indices have yet entered the estimated support.The remaining correct set T − Λk is therefore nonempty.
  • Termination: Once all correct indices are selected, the residual becomes zero and the gOMP algorithm terminates.The non-initial analysis therefore focuses on the case where Λk does not yet contain all of T.
  • Proof ingredients: The proof uses an upper bound αN for the N-th largest correlation among remaining incorrect columns and a lower bound β1 for the largest remaining-correct correlation.Comparing these bounds provides the condition for selecting at least one correct index.
  • Success condition: If β1 exceeds αN, a remaining correct index lies among the top N correlations and is selected in the next iteration.This is the central comparison connecting the correlation bounds to gOMP success.
  • RIP reduction: RIP monotonicity replaces lower-order constants with δNK in the later-iteration bounds through Nk < NK and N + Nk ≤ NK.The resulting inequalities support the sufficient condition used to prove Theorem 3.5.

C. Overall Sufficient Condition

The gOMP’s sufficient recovery condition combines initial- and later-iteration success conditions, guaranteeing exact recovery under an RIP bound and at most K iterations.

  • The overall sufficient condition is the stricter of the bounds ensuring success in the initial and non-initial iterations.
  • N ≤ min{K, m/N} and δ_NK < √N/(√K + 3√N) guarantee recovery of any K-sparse vector within at most K iterations.
  • Case analysis: For N > 1 and K > 1, the analysis compares RIP orders through δ_NK ≥ δ_K+N when combining case-specific conditions.
  • Case analysis: For N = 1 and K > 1, the general condition is selected by comparing the stricter case-specific sufficient bounds, with the result combining consistently with Case 1.
  • Case analysis: The K = 1 case is recovered in the first iteration regardless of N under the corresponding RIP condition.
  • Comparison with previous work: The proposed bound can offer better recovery conditions than a previous bound when N is typically much smaller than K.

D. Sufficient Condition of OMP

OMP is treated as the N = 1 special case of gOMP, yielding a sufficient RIP condition that propagates successful index selection through all iterations.

  • OMP is the special case of gOMP obtained by setting N = 1.
  • Applying N = 1 to Theorem 3.8 gives an improved OMP condition because non-initial OMP steps have the same form as the initial step.
  • δ_K+1 < 1/(√K + 1) ensures that OMP recovers an index from the true support in its first iteration.
  • If the first k OMP iterations are successful, the next iteration also succeeds under the same δ_K+1 condition.
  • Combining first- and later-iteration guarantees, OMP recovers the original signal in exactly K iterations under δ_K+1 < 1/(√K + 1).
  • Bound comparison: The OMP and gOMP bounds cannot be directly compared because they involve different RIP orders and expressions.
  • Practical trade-off: Allowing OMP more than K iterations can improve performance toward gOMP levels, but may incur larger delay and higher computational cost.

IV. RECONSTRUCTION OF SPARSE SIGNALS FROM NOISY MEASUREMENTS

Under noisy measurements, perfect reconstruction is replaced by an upper bound on ℓ2-norm distortion, analyzed for the algorithm’s stopping scenarios.

  • With measurements y = Φx + v, the paper evaluates reconstruction using the upper bound of ℓ2-norm distortion because perfect recovery cannot be guaranteed.
  • The gOMP stopping rule is ∥r_k∥2 < ε or k = K when Φ satisfies the RIP of order NK.
  • Stopping scenarios: Theorem 4.1 bounds ∥x − x̂∥2 when the residual threshold is reached after s < K iterations.
  • Stopping scenarios: Theorem 4.2 provides the distortion bound when gOMP terminates after K iterations under an RIP condition of order NK + K.
  • Error behavior: The distortion bound is essentially controlled by the product of noise power and a constant c.
  • Error behavior: Increasing N decreases the constant C_K and may yield a smaller distortion bound, but the guarantee requires NK ≤ m and therefore applies only to very sparse signals.
  • Iteration analysis: The noisy-case proof analyzes whether at least one correct index is selected at each subsequent iteration after successful prior iterations.

V. DISCUSSIONS ON COMPLEXITY

The gOMP reduces running time by selecting multiple indices per iteration and reusing QR-factorization data for least-squares estimation. Its complexity depends on the iteration count, which empirical results show is substantially smaller than OMP's.

  • Complexity analysis: The gOMP’s total complexity is approximately 2smn+(2N^2+N)s^2m, where s is the number of iterations.The analysis states that s is small in empirical simulations, supporting reduced running time and computational complexity.
  • Empirical iteration savings: For N = 5, Fig. 5 compares OMP and gOMP iteration counts against sparsity K using K/3 iterations as a reference curve.The figure caption defines the plotted quantity and the red dashed reference.
  • Per-iteration operations: Identification costs O(mn), while residual updating costs approximately 2Nkm per iteration.Identification computes and sorts correlations; residual updating multiplies the selected submatrix by the least-squares estimate.
  • Per-iteration operations: The gOMP estimates the selected coefficients through a least-squares problem based on QR factorization.Because successive selected-index sets largely overlap, modified Gram-Schmidt can recycle the previous QR factorization.
  • Empirical iteration savings: The gOMP complexity can be expressed as O(Kmn) when N is a small constant, while its practical iteration count is much smaller than K.The paper attributes the practical savings to selecting multiple correct indices in each iteration.

VI. CONCLUSION

The paper concludes that gOMP improves sparse-signal reconstruction efficiency by identifying multiple indices per iteration. It reports comparable recovery to ℓ1-minimization, faster processing, competitive complexity, and an RIP-based exact-recovery guarantee.

  • Conclusion: gOMP identifies multiple indices without additional postprocessing, enabling parallel-wise processing and reducing running time.The conclusion links multiple-index selection with expedited processing.
  • Conclusion: Empirical simulations show recovery performance comparable to ℓ1-minimization, together with fast processing speed and competitive computational complexity.These are the paper’s reported empirical outcomes.
  • Conclusion: The RIP analysis states that gOMP perfectly recovers K-sparse signals when the sensing-matrix isometry constant satisfies the paper’s stated bound.The supplied passage contains the guarantee’s continuation in a separate fragment, but not the full inequality.

APPENDIX A PROOF OF LEMMA 3.6

The proof analyzes whether the gOMP’s N selected indices include correct support elements by comparing correlations associated with incorrect and remaining correct indices.

  • Support-selection comparison: The proof defines W as the N indices with largest-magnitude correlations among the remaining incorrect columns.W contains w1 through wN, ordered by correlation magnitude.
  • Support-selection comparison: If l correct indices are already in Λk, then W and T−Λk are disjoint and their combined size is N+K−l.This cardinality relation sets up the comparison between selected incorrect indices and remaining true support.
  • Support-selection comparison: The proof also uses that W is disjoint from Λk and that |W|+|Λk| equals N+Nk.These set relations support the subsequent RIP-based bounds.
  • Support-selection comparison: The resulting inequalities combine correlation norms and RIP lemmas to establish the required support-selection condition.The supplied proof fragments identify the norm inequality and Lemmas 3.2 and 3.3 as ingredients.

APPENDIX B PROOF OF LEMMA 3.7

These proof and implementation passages develop correlation bounds for gOMP selection and quantify the least-squares estimation cost using incremental QR updates.

  • Correlation bounds: The RIP-based inequalities use support-size relations and residual bounds to control the relevant correlation terms.The passages explicitly invoke RIP definitions, Lemmas 3.2 and 3.3, and ||rs||2 < ǫ.
  • Correlation bounds: The proof begins by bounding β1, the largest-magnitude correlation between the residual and a remaining correct-support column.It then combines this lower bound with an upper bound on αN to derive a sufficient condition for αN < β1.
  • Least-squares implementation: At iteration k, gOMP estimates the selected nonzero coefficients by solving a least-squares problem.The QR factorization represents the selected sensing submatrix with orthonormal Q and upper-triangular R factors.
  • Least-squares implementation: Modified Gram-Schmidt maintains the previous QR decomposition, reducing the cost of solving the updated least-squares system.The implementation reuses stored QR data because successive selected sets overlap substantially.
  • Complexity accounting: The detailed least-squares cost is represented by CLS = CQR + C1 + C2 + C3 + C4.The supplied expression expands the leading terms of this aggregate cost.
Loading 1111.6664v2…