<< Chapter < Page Chapter >> Page >

Let Φ : R N R M denote a sensing matrix and Δ : R M R N denote a recovery algorithm. We say that the pair ( Φ , Δ ) is C -stable if for any x Σ K and any e R M we have that

Δ Φ x + e - x 2 C e .

This definition simply says that if we add a small amount of noise to the measurements, then the impact of this on the recovered signal should not be arbitrarily large. [link] below demonstrates that the existence of any decoding algorithm (potentially impractical) that can stably recover from noisy measurements requires that Φ satisfy the lower bound of [link] with a constant determined by C .

  If the pair ( Φ , Δ ) is C -stable, then

1 C x 2 Φ x 2

for all x Σ 2 K .

Pick any x , z Σ K . Define

e x = Φ ( z - x ) 2 and e z = Φ ( x - z ) 2 ,

and note that

Φ x + e x = Φ z + e z = Φ ( x + z ) 2 .

Let x ^ = Δ ( Φ x + e x ) = Δ ( Φ z + e z ) . From the triangle inequality and the definition of C -stability, we have that

x - z 2 = x - x ^ + x ^ - z 2 x - x ^ 2 + x ^ - z 2 C e x + C e z 2 = C Φ x - Φ z 2 .

Since this holds for any x , z Σ K , the result follows.

Note that as C 1 , we have that Φ must satisfy the lower bound of [link] with δ K = 1 - 1 / C 2 0 . Thus, if we desire to reduce the impact of noise in our recovered signal then we must adjust Φ so that it satisfies the lower bound of [link] with a tighter constant.

One might respond to this result by arguing that since the upper bound is not necessary, we can avoid redesigning Φ simply by rescaling Φ so that as long as Φ satisfies the RIP with δ 2 K < 1 , the rescaled version α Φ will satisfy [link] for any constant C . In settings where the size of the noise is independent of our choice of Φ , this is a valid point — by scaling Φ we are simply adjusting the gain on the “signal” part of our measurements, and if increasing this gain does not impact the noise, then we can achieve arbitrarily high signal-to-noise ratios, so that eventually the noise is negligible compared to the signal.

However, in practice we will typically not be able to rescale Φ to be arbitrarily large. Moreover, in many practical settings the noise is not independent of Φ . For example, suppose that the noise vector e represents quantization noise produced by a finite dynamic range quantizer with B bits. Suppose the measurements lie in the interval [ - T , T ] , and we have adjusted the quantizer to capture this range. If we rescale Φ by α , then the measurements now lie between [ - α T , α T ] , and we must scale the dynamic range of our quantizer by α . In this case the resulting quantization error is simply α e , and we have achieved no reduction in the reconstruction error.

Measurement bounds

We can also consider how many measurements are necessary to achieve the RIP. If we ignore the impact of δ and focus only on the dimensions of the problem ( N , M , and K ) then we can establish a simple lower bound. We first provide a preliminary lemma that we will need in the proof of the main theorem.

Let K and N satisfying K < N / 2 be given. There exists a set X Σ K such that for any x X we have x 2 K and for any x , z X with x z ,

x - z 2 K / 2 ,

and

log | X | K 2 log N K .

We will begin by considering the set

U = x 0 , + 1 , - 1 N : x 0 = K .

By construction, x 2 2 = K for all x U . Thus if we construct X by picking elements from U then we automatically have x 2 K .

Next, observe that | U | = N K 2 K . Note also that x - z 0 x - z 2 2 , and thus if x - z 2 2 K / 2 then x - z 0 K / 2 . From this we observe that for any fixed x U ,

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, An introduction to compressive sensing. OpenStax CNX. Apr 02, 2011 Download for free at http://legacy.cnx.org/content/col11133/1.5
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'An introduction to compressive sensing' conversation and receive update notifications?

Ask