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

where y is an M × 1 column vector of the compressive measurements and A = Φ B

is the measurement matrix or the sensing matrix. Given an M N sensing matrix

A and the observation vector y , the general problem is to recover the sparse or
compressible vector

×

. To this end, the first question is to determine whether A is
good for compressive sensing. Cand e s and Tao introduced a necessary condition on
A that guarantees a stable solution for both K sparse and compressible signals [26],
[24].

α

Definition 2.1. Amatrix A is said to satisfy the Restricted Isometry Property (RIP)
of order K with constants δ K ∈ ( 0 , 1 ) if

2
2

2
2

2
2

( 1 − δ K ) v ≤ Av ≤ ( 1 + δ K ) v

for any v such that v 0 ≤ K .

An equivalent description of RIP is to say that all subsets of K columns taken
from A are nearly orthogonal. This in turn implies that K sparse vectors cannot be
in the null space of A . When RIP holds, A approximately preserves the Euclidean
length of K sparse vectors. That is,

2
2

2
2

2
2

( 1 − δ 2 K ) v 1 − v 2 ≤ Av 1 − Av 2 ≤ ( 1 + δ 2 K ) v 1 − v 2

holds for all K sparse vectors v 1 and v 2 . A related condition known as incoherence,

requires that the rows of Φ can not sparsely represent the columns of B and vice

versa.

Definition 2.2. The coherence between Φ and the representation basis B is

√ N

μ ( Φ , B )=

1 ≤ i , j ≤ N | φ i ,

max b j |, (2.5)

where φ i ∈ Φ and b j ∈ B .

The number μ measures h ow much two vectors in A = Φ B can look alike. The

is between 1 and √ N . We say that a matrix A is incoherent when value of is very

small. The incoherence holds for many pairs of bases. For example, it holds for the
delta spikes and the Fourier bases. Surprisingly, with high probability, incoherence
holds between any arbitrary basis and a random matrix such as Gaussian or
Bernoulli [6], [142].

μ μ

2.3 Recovery

Since, M N , we have an under-determined system of linear equations, which in

general has infinitely many solutions. So our problem is ill-posed. If one desires
to narrow the choice to a well-defined solution, additional constraints are needed.