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

2.5 Phase Transition Diagrams

The performance of a CS system can be evaluated by generating phase transition
diagrams [86], [48], [10], [51]. Given a particular CS system, governed by the
sensing matrix A

M
N

= Φ B ,let δ = be a normalized measure of undersampling

K
M be a normalized measure of sparsity. A plot of the pairing of the

factor and ρ =

2 . It has been shown that
for many practical CS matrices, there exist sharp boundaries in this phase space that
clearly divide the solvable from unsolvable problems in the noiseless case. In other
words, a phase transition diagram provides a way of checking

( δ , ρ ) ∈ [ , ]

variables δ and ρ describes a 2-D phase space 0 1

/

1 equivalence, 0

indicating how sparsity and indeterminacy affect the success of 1 minimization

[86], [48], [51]. Fig. 2.2 shows an example of a phase transition diagram which is
obtained when a random Gaussian matrix is used as A . Below the boundary,

/

1
equivalence holds and above the boundary, the system lacks sparsity and/or too few
measurements are obtained to solve the problem correctly.

0

Phase Transition

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

δ =M/N

Fig. 2.2 Phase transition diagram corresponding to a CS system where A is the random Gaussian
matrix. The boundary separates regions in the problem space where ( 2.7 ) can and cannot be solved.
Below the curve solutions can be obtained and above the curve solutions can not be obtained