Review of Sparsity Known and Blind Sparsity Greedy Algorithms for Compressed Sensing

Review of Sparsity Known and Blind Sparsity Greedy Algorithms for Compressed Sensing

Chun-Yan Zeng (South China University of Technology, China), Li-Hong Ma (South China University of Technology, China), Ming-Hui Du (South China University of Technology, China) and Jing Tian (Wuhan University of Science and Technology, China)
DOI: 10.4018/978-1-4666-3958-4.ch004
OnDemand PDF Download:
No Current Special Offers


Sparsity level is crucial to Compressive Sensing (CS) reconstruction, but in practice it is often unknown. Recently, several blind sparsity greedy algorithms have emerged to recover signals by exploiting the underlying signal characteristics. Sparsity Adaptive Matching Pursuit (SAMP) estimates the sparsity level and the true support set stage by stage, while Backtracking-Based Adaptive OMP (BAOMP) selects atoms by thresholds related to the maximal residual projection. This chapter reviews typical sparsity known greedy algorithms including OMP, StOMP, and CoSaMP, as well as those emerging blind sparsity greedy algorithms. Furthermore, the algorithms are analysed in structured diagrammatic representation and compared by exact reconstruction probabilities for Gaussian and binary signals distributed sparsely.
Chapter Preview

1. Introduction

In Compressive Sensing (CS) theory, a signal 978-1-4666-3958-4.ch004.m01 is k-sparse if 978-1-4666-3958-4.ch004.m02 has k(978-1-4666-3958-4.ch004.m03) nonzero entries or coefficients under a linear transform. Such a signal can be recovered from linear projections:

(1) where 978-1-4666-3958-4.ch004.m05is the observation vector and978-1-4666-3958-4.ch004.m06is often known as a dictionary or a measurement matrix with each column vector978-1-4666-3958-4.ch004.m07 regarded as an atom. If k<<M and978-1-4666-3958-4.ch004.m08 satisfies the following Restricted Isometry Property (RIP),978-1-4666-3958-4.ch004.m09can be faithfully recovered from 978-1-4666-3958-4.ch004.m10 measurements (Donoho, 2006):
(2) where978-1-4666-3958-4.ch004.m12is the isometry constant, the smallest number satisfying Equation (2). When978-1-4666-3958-4.ch004.m13, the projection operator very nearly maintains the 978-1-4666-3958-4.ch004.m14distance between each pair of k/2-sparse signals (Needell & Tropp, 2009).

Complete Chapter List

Search this Book: