Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » An Introduction to Compressive Sensing » The restricted isometry property

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

The restricted isometry property

Module by: Mark A. Davenport. E-mail the author

Summary: In this module we introduce the restricted isometry property (RIP) and discuss its role in compressive sensing. In particular, we describe the relationship between the RIP and the concept of stability in the context of sparse signal acquisition. We also provide a simple lower bound on the number of measurements necessary for a matrix to satisfy the RIP.

The null space property (NSP) is both necessary and sufficient for establishing guarantees of the form

Δ ( Φ x ) - x 2 C σ K ( x ) 1 K , Δ ( Φ x ) - x 2 C σ K ( x ) 1 K ,
(1)

but these guarantees do not account for noise. When the measurements are contaminated with noise or have been corrupted by some error such as quantization, it will be useful to consider somewhat stronger conditions. In [1], Candès and Tao introduced the following isometry condition on matrices ΦΦ and established its important role in compressive sensing (CS).

Definition 1:

A matrix ΦΦ satisfies the restricted isometry property (RIP) of order KK if there exists a δK(0,1)δK(0,1) such that

( 1 - δ K ) x 2 2 Φ x 2 2 ( 1 + δ K ) x 2 2 , ( 1 - δ K ) x 2 2 Φ x 2 2 ( 1 + δ K ) x 2 2 ,
(2)

holds for all xΣK = x : x 0 K xΣK = x : x 0 K .

If a matrix ΦΦ satisfies the RIP of order 2K2K, then we can interpret Equation 2 as saying that ΦΦ approximately preserves the distance between any pair of KK-sparse vectors. This will clearly have fundamental implications concerning robustness to noise.

It is important to note that in our definition of the RIP we assume bounds that are symmetric about 1, but this is merely for notational convenience. In practice, one could instead consider arbitrary bounds

α x 2 2 Φ x 2 2 β x 2 2 α x 2 2 Φ x 2 2 β x 2 2
(3)

where 0<αβ<0<αβ<. Given any such bounds, one can always scale ΦΦ so that it satisfies the symmetric bound about 1 in Equation 2. Specifically, multiplying ΦΦ by 2/(β+α)2/(β+α) will result in an Φ˜Φ˜ that satisfies Equation 2 with constant δK=(β-α)/(β+α)δK=(β-α)/(β+α). We will not explicitly show this, but one can check that all of the theorems in this course based on the assumption that ΦΦ satisfies the RIP actually hold as long as there exists some scaling of ΦΦ that satisfies the RIP. Thus, since we can always scale ΦΦ to satisfy Equation 2, we lose nothing by restricting our attention to this simpler bound.

Note also that if ΦΦ satisfies the RIP of order KK with constant δKδK, then for any K'<KK'<K we automatically have that ΦΦ satisfies the RIP of order K'K' with constant δK'δKδK'δK. Moreover, in [6] it is shown that if ΦΦ satisfies the RIP of order KK with a sufficiently small constant, then it will also automatically satisfy the RIP of order γKγK for certain γγ, albeit with a somewhat worse constant.

Lemma 1: (Corollary 3.4 of [6])

Suppose that ΦΦ satisfies the RIP of order KK with constant δKδK. Let γγ be a positive integer. Then ΦΦ satisfies the RIP of order K'=γK2K'=γK2 with constant δK'<γ·δKδK'<γ·δK, where ·· denotes the floor operator.

This lemma is trivial for γ=1,2γ=1,2, but for γ3γ3 (and K4K4) this allows us to extend from RIP of order KK to higher orders. Note however, that δKδK must be sufficiently small in order for the resulting bound to be useful.

The RIP and stability

We will see later in this course that if a matrix ΦΦ satisfies the RIP, then this is sufficient for a variety of algorithms to be able to successfully recover a sparse signal from noisy measurements. First, however, we will take a closer look at whether the RIP is actually necessary. It should be clear that the lower bound in the RIP is a necessary condition if we wish to be able to recover all sparse signals xx from the measurements ΦxΦx for the same reasons that the NSP is necessary. We can say even more about the necessity of the RIP by considering the following notion of stability.

Definition 2:

Let Φ:RNRMΦ:RNRM denote a sensing matrix and Δ:RMRNΔ:RMRN denote a recovery algorithm. We say that the pair (Φ,Δ)(Φ,Δ) is CC-stable if for any xΣKxΣK and any eRMeRM we have that

Δ Φ x + e - x 2 C e . Δ Φ x + e - x 2 C e .
(4)

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. Theorem 1 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 Equation 2 with a constant determined by CC.

Theorem 1

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

1 C x 2 Φ x 2 1 C x 2 Φ x 2
(5)

for all xΣ2KxΣ2K.

Proof

Pick any x,zΣKx,zΣK. Define

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

and note that

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

Let x^=Δ(Φx+ex)=Δ(Φz+ez)x^=Δ(Φx+ex)=Δ(Φz+ez). From the triangle inequality and the definition of CC-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 . 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 .
(8)

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

Note that as C1C1, we have that ΦΦ must satisfy the lower bound of Equation 2 with δK=1-1/C20δK=1-1/C20. 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 Equation 2 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 δ2K<1δ2K<1, the rescaled version αΦαΦ will satisfy Equation 5 for any constant CC. 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 ee represents quantization noise produced by a finite dynamic range quantizer with BB bits. Suppose the measurements lie in the interval [-T,T][-T,T], and we have adjusted the quantizer to capture this range. If we rescale ΦΦ by αα, then the measurements now lie between [-αT,αT][-αT,αT], and we must scale the dynamic range of our quantizer by αα. In this case the resulting quantization error is simply αeα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 (NN, MM, and KK) 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.

Lemma 2

Let KK and NN satisfying K<N/2K<N/2 be given. There exists a set XΣKXΣK such that for any xXxX we have x2Kx2K and for any x,zXx,zX with xzxz,

x - z 2 K / 2 , x - z 2 K / 2 ,
(9)

and

log | X | K 2 log N K . log | X | K 2 log N K .
(10)

Proof

We will begin by considering the set

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

By construction, x22=Kx22=K for all xUxU. Thus if we construct XX by picking elements from UU then we automatically have x2Kx2K.

Next, observe that |U|=NK2K|U|=NK2K. Note also that x-z0x-z22x-z0x-z22, and thus if x-z22K/2x-z22K/2 then x-z0K/2x-z0K/2. From this we observe that for any fixed xUxU,

z U : x - z 2 2 K / 2 z U : x - z 0 K / 2 N K / 2 3 K / 2 . z U : x - z 2 2 K / 2 z U : x - z 0 K / 2 N K / 2 3 K / 2 .
(12)

Thus, suppose we construct the set XX by iteratively choosing points that satisfy Equation 9. After adding jj points to the set, there are at least

N K 2 K - j N K / 2 3 K / 2 N K 2 K - j N K / 2 3 K / 2
(13)

points left to pick from. Thus, we can construct a set of size |X||X| provided that

| X | N K / 2 3 K / 2 N K 2 K | X | N K / 2 3 K / 2 N K 2 K
(14)

Next, observe that

N K N K / 2 = ( K / 2 ) ! ( N - K / 2 ) ! K ! ( N - K ) ! = i = 1 K / 2 N - K + i K / 2 + i N K - 1 2 K / 2 , N K N K / 2 = ( K / 2 ) ! ( N - K / 2 ) ! K ! ( N - K ) ! = i = 1 K / 2 N - K + i K / 2 + i N K - 1 2 K / 2 ,
(15)

where the inequality follows from the fact that (n-K+i)/(K/2+i)(n-K+i)/(K/2+i) is decreasing as a function of ii. Thus, if we set |X|=(N/K)K/2|X|=(N/K)K/2 then we have

| X | 3 4 K / 2 = 3 N 4 K K / 2 = N K - N 4 K K / 2 N K - 1 2 K / 2 N K N K / 2 . | X | 3 4 K / 2 = 3 N 4 K K / 2 = N K - N 4 K K / 2 N K - 1 2 K / 2 N K N K / 2 .
(16)

Hence, Equation 14 holds for |X|=(N/K)K/2|X|=(N/K)K/2, which establishes the lemma.

Using this lemma, we can establish the following bound on the required number of measurements to satisfy the RIP.

Theorem 2

Let ΦΦ be an M×NM×N matrix that satisfies the RIP of order 2K2K with constant δ(0,12]δ(0,12]. Then

M C K log N K M C K log N K
(17)

where C=1/2log(24+1)0.28C=1/2log(24+1)0.28.

Proof

We first note that since ΦΦ satisfies the RIP, then for the set of points XX in Lemma 2 we have,

Φ x - Φ z 2 1 - δ x - z 2 K / 4 Φ x - Φ z 2 1 - δ x - z 2 K / 4
(18)

for all x,zXx,zX, since x-zΣ2Kx-zΣ2K and δ12δ12. Similarly, we also have

Φ x 2 1 + δ x 2 3 K / 2 Φ x 2 1 + δ x 2 3 K / 2
(19)

for all xXxX.

From the lower bound we can say that for any pair of points x,zXx,zX, if we center balls of radius K/4/2=K/16K/4/2=K/16 at ΦxΦx and ΦzΦz, then these balls will be disjoint. In turn, the upper bound tells us that the entire set of balls is itself contained within a larger ball of radius 3K/2+K/163K/2+K/16. If we let BM(r)={xRM:x2r}BM(r)={xRM:x2r}, this implies that

Vol B M 3 K / 2 + K / 16 | X | · Vol B M K / 16 , 3 K / 2 + K / 16 M | X | · K / 16 M , 24 + 1 M | X | , M log | X | log 24 + 1 . Vol B M 3 K / 2 + K / 16 | X | · Vol B M K / 16 , 3 K / 2 + K / 16 M | X | · K / 16 M , 24 + 1 M | X | , M log | X | log 24 + 1 .
(20)

The theorem follows by applying the bound for |X||X| from Lemma 2.

Note that the restriction to δ12δ12 is arbitrary and is made merely for convenience — minor modifications to the argument establish bounds for δδ max δδ max for any δ max <1δ max <1. Moreover, although we have made no effort to optimize the constants, it is worth noting that they are already quite reasonable.

Although the proof is somewhat less direct, one can establish a similar result (in the dependence on NN and KK) by examining the Gelfand width of the 11 ball [2]. However, both this result and Theorem 2 fail to capture the precise dependence of MM on the desired RIP constant δδ. In order to quantify this dependence, we can exploit recent results concerning the Johnson-Lindenstrauss lemma, which concerns embeddings of finite sets of points in low-dimensional spaces [3]. Specifically, it is shown in [4] that if we are given a point cloud with pp points and wish to embed these points in RMRM such that the squared 22 distance between any pair of points is preserved up to a factor of 1±ϵ1±ϵ, then we must have that

M c 0 log ( p ) ϵ 2 , M c 0 log ( p ) ϵ 2 ,
(21)

where c0>0c0>0 is a constant.

The Johnson-Lindenstrauss lemma is closely related to the RIP. We will see in "Matrices that satisfy the RIP" that any procedure that can be used for generating a linear, distance-preserving embedding for a point cloud can also be used to construct a matrix that satisfies the RIP. Moreover, in [5] it is shown that if a matrix ΦΦ satisfies the RIP of order K=c1log(p)K=c1log(p) with constant δδ, then ΦΦ can be used to construct a distance-preserving embedding for pp points with ϵ=δ/4ϵ=δ/4. Combining these we obtain

M c 0 log ( p ) ϵ 2 = 16 c 0 K c 1 δ 2 . M c 0 log ( p ) ϵ 2 = 16 c 0 K c 1 δ 2 .
(22)

Thus, for small δδ the number of measurements required to ensure that ΦΦ satisfies the RIP of order KK will be proportional to K/δ2K/δ2, which may be significantly higher than Klog(N/K)Klog(N/K). See [5] for further details.

References

  1. Candès, E. and Tao, T. (2005). Decoding by linear programming. IEEE Trans. Inform. Theory, 51(12), 4203–4215.
  2. Garnaev, A. and Gluskin, E. (1984). The widths of Euclidean balls. Dokl. An. SSSR, 277, 1048–1052.
  3. Johnson, W. and Lindenstrauss, J. (1982, Jun.). Extensions of Lipschitz mappings into a Hilbert space. In Proc. Conf. Modern Anal. and Prob. New Haven, CT
  4. Jayram, T. and Woodruff, D. (2011, Jan.). Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error. In Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA). San Francisco, CA
  5. Krahmer, F. and Ward, R. (2010, Sept.). New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property. [Preprint].
  6. Needell, D. and Tropp, J. (2009). CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harmon. Anal., 26(3), 301–321.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks