Recovery of Sparse Signals via Generalized Orthogonal Matching Pursuit: A New Analysis

preprint2015arXivOpen access

Abstract

As an extension of orthogonal matching pursuit (OMP) improving the recovery performance of sparse signals, generalized OMP (gOMP) has recently been studied in the literature. In this paper, we present a new analysis of the gOMP algorithm using restricted isometry property (RIP). We show that if the measurement matrix Φ∈Rm×n\mathbfΦ \in \mathcal{R}^{m \times n} satisfies the RIP with δmax⁡{9,S+1}K≤18,δ_{\max \left\{9, S + 1 \right\}K} \leq \frac{1}{8}, then gOMP performs stable reconstruction of all KK-sparse signals x∈Rn\mathbf{x} \in \mathcal{R}^n from the noisy measurements y=Φx+v\mathbf{y} = \mathbf{Φx} + \mathbf{v} within max⁡{K,⌊8KS⌋}\max \left\{K, \left\lfloor \frac{8K}{S} \right\rfloor \right\} iterations where v\mathbf{v} is the noise vector and SS is the number of indices chosen in each iteration of the gOMP algorithm. For Gaussian random measurements, our results indicate that the number of required measurements is essentially m=O(Klog⁡nK)m = \mathcal{O}(K \log \frac{n}{K}), which is a significant improvement over the existing result m=O(K2log⁡nK)m = \mathcal{O}(K^2 \log \frac{n}{K}), especially for large KK.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.