Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Sajib Saha (The University of New South Wales, Australia) and Murat Tahtali (The University of New South Wales, Australia)

Copyright: © 2016
|Pages: 24

DOI: 10.4018/978-1-4666-8811-7.ch006

Chapter Preview

TopCompressive sensing (CS) is a novel sampling paradigm that allows the sampling of signals in a much more efficient way than the established Nyquist-Shannon sampling theorem. In 1949, Shannon (1998) presented his famous proof that, if a function *f*(*t*) contains no frequencies higher than *W *cps (cycles per second), it is completely determined by giving its ordinates at a series of points spaced at the critical sampling interval of 1/2*W*, to which he referred as the *Nyquist interval*, in recognition of Nyquist’s discovery of the fundamental importance of this interval in connection with telegraphy (Meijering, 2002).Traditional signal processing techniques generally sample data uniformly at the Nyquist rate, however compressed sensing theory states that certain signals can be recovered from fewer samples than required in the Nyquist-Shannon paradigm. David L. Donoho et al. in (2010) say “The sampling theorem of Shannon-Nyquist-Kotelnikov-Whittaker has been of tremendous importance in engineering theory and practice. Straightforward and precise, it sets forth the number of measurements required to reconstruct any band limited signal. However, the sampling theorem is wrong! Not literally wrong, but psychologically wrong. More precisely, it engender(s) the psychological expectation that we need very large numbers of samples in situations where we need very few.”

Contrary to traditional Nyquist-Shannon paradigm, the CS paradigm, banking on finding sparse solutions to under-determined linear systems, can reconstruct signals from far fewer samples than the Nyquist-Shannon sampling rate. This recovery is exact if the signal being sensed has a low information rate (means it is sparse in the original or in some transform domain).

The key idea of compressed sensing is to recover a sparse signal from very few non-adaptive, linear measurements by optimization techniques (Eldar et al., 2012). This development – the problem of sparse recovery – can in fact be traced back to earlier papers from the 90s such as (Donoho et al., 1989), and later the prominent papers by Donoho and Huo (Donoho et al., 2001) and Donoho and Elad (Donoho et al., 2003). Following the discovery that sparsity could enable the exact solution of ill-posed problems under certain conditions (Donoho, 2006; Candes et al., 2007), there has been a tremendous growth on efficient application of sparsity constraints for solving ill-posed problems (Saha et al., 2014b). The theoretical foundation of compressed sensing has already become a key concept in various areas of applied mathematics, computer science, and electrical engineering. It is worth mentioning that previously, when the fundamental papers introducing compressed sensing (Donoho et al., 2001; Donoho et al. 2003) were published, the term “compressed sensing” was initially utilized for random sensing matrices, since those allow for a minimal number of non-adaptive, linear measurements (Eldar et al., 2012). Nowadays, the term “compressed sensing” is more and more often used interchangeably with “sparse recovery” in general.

To state the problem mathematically precisely, let *X* represents the signal to be sensed, then the compressed sensing problem can be formulated as follows:

Where *A* is the *m*×*n* measurement matrix and measurement vector. Under conventional sensing paradigm *m* must be at least equal to *n* (Saad et al., 2013). However CS states that *m* can be far less than *n* provided the signal is sparse (accurate reconstruction) or nearly sparse/compressible (approximate reconstruction) in original or some transform domain.

A nonlinear algorithm is used in CS to recover *X*, with the prior assumption that *X* itself is sparse, i.e. it has very few non-zero coefficients in the sense that ||*X*||_{0}:=#{*i*: *X _{i}* ≠ 0} is small, or that there exists an orthogonal basis or frame

It is quite intuitive to solve *X* with the knowledge of *Y* by solving

This algorithm requires combinatorial search and is NP-hard (Edoardo et al., 1998; Muthukrishnan, 2005). Encouragingly, it has been shown in the fundamental paper (Chen et al. 1998) that, in many cases, it is possible to estimate the *l*_{0}-norm by solving the following *l*_{1}-norm optimization problem

Now the general question when ‘*l*_{0} = *l*_{1}’ holds the key to compressed sensing.

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved