Compressive Sensing - Sparse Representations and Compressive Sensing for Imaging and Vision - page 3

Chapter 2
Compressive Sensing

Compressive sensing [47], [23] is a new concept in signal processing and
information theory where one measures a small number of non-adaptive linear
combinations of the signal. These measurements are usually much smaller than
the number of samples that define the signal. From these small number of
measurements, the signal is then reconstructed by a non-linear procedure. In what
follows, we present some fundamental premises underlying CS: sparsity, incoherent
sampling and non-linear recovery.

2.1 Sparsity

Let x be a discrete time signal which can be viewed as an N × 1 column vector

N . Given an orthonormal basis matrix B N × N

in R ∈ R whose columns are the basis

i

elements { b i }

1 , x can be represented in terms of this basis as =

N
i = 1 α i b i

=

x (2.1)

or more compactly x = B α , where α is an N × 1 column vector of coefficients.

T denotes the transposition
operation. If the basis B provides a K -sparse representation of x ,then( 2.1 ) can be
rewritten as

b i x where These coefficients are given by α = x , b i = . i

K
i = 1 α n i b n i ,

x =

where are the indices of the coefficients and the basis elements corresponding

to the K nonzero entries. In this case,

{ n i }

α is an N × 1 column vector with only K

nonzero elements. That is, α 0 = K where . p denotes the p -norm defined as