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:
List Price: $37.50


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 is k-sparse if has k() nonzero entries or coefficients under a linear transform. Such a signal can be recovered from linear projections:

(1) where is the observation vector andis often known as a dictionary or a measurement matrix with each column vector regarded as an atom. If k<<M and satisfies the following Restricted Isometry Property (RIP),can be faithfully recovered from measurements (Donoho, 2006):
(2) whereis the isometry constant, the smallest number satisfying Equation (2). When, the projection operator very nearly maintains the distance between each pair of k/2-sparse signals (Needell & Tropp, 2009).

Complete Chapter List

Search this Book: