Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » An Introduction to Compressive Sensing » ℓ_1 minimization proof

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

ℓ_1 minimization proof

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

Summary: In this module we prove one of the core lemmas that is used throughout this course to establish results regarding ℓ_1 minimization.

We now establish one of the core lemmas that we will use throughout this course. Specifically, Lemma 4 is used in establishing the relationship between the RIP and the NSP as well as establishing results on ℓ1ℓ1 minimization in the context of sparse recovery in both the noise-free and noisy settings. In order to establish Lemma 4, we establish the following preliminary lemmas.

Lemma 1

Suppose u,vu,v are orthogonal vectors. Then

u 2 + v 2 ≤ 2 u + v 2 . u 2 + v 2 ≤ 2 u + v 2 .
(1)

Proof

We begin by defining the 2×12×1 vector w=u2,v2Tw=u2,v2T. By applying standard bounds on ℓpℓp norms (Lemma 1 from "The RIP and the NSP") with K=2K=2, we have w1≤2w2w1≤2w2. From this we obtain

u 2 + v 2 ≤ 2 u 2 2 + v 2 2 . u 2 + v 2 ≤ 2 u 2 2 + v 2 2 .
(2)

Since uu and vv are orthogonal, u22+v22=u+v22u22+v22=u+v22, which yields the desired result.

Lemma 2

If ΦΦ satisfies the restricted isometry property (RIP) of order 2K2K, then for any pair of vectors u,v∈ΣKu,v∈ΣK with disjoint support,

Φ u , Φ v ≤ δ 2 K u 2 v 2 . Φ u , Φ v ≤ δ 2 K u 2 v 2 .
(3)

Proof

Suppose u,v∈ΣKu,v∈ΣK with disjoint support and that u2=v2=1.u2=v2=1. Then, u±v∈Σ2Ku±v∈Σ2K and u±v22=2u±v22=2. Using the RIP we have

2 ( 1 - δ 2 K ) ≤ Φ u ± Φ v 2 2 ≤ 2 ( 1 + δ 2 K ) . 2 ( 1 - δ 2 K ) ≤ Φ u ± Φ v 2 2 ≤ 2 ( 1 + δ 2 K ) .
(4)

Finally, applying the parallelogram identity

Φ u , Φ v ≤ 1 4 Φ u + Φ v 2 2 - Φ u - Φ v 2 2 ≤ δ 2 K Φ u , Φ v ≤ 1 4 Φ u + Φ v 2 2 - Φ u - Φ v 2 2 ≤ δ 2 K
(5)

establishes the lemma.

Lemma 3

Let Λ0Λ0 be an arbitrary subset of {1,2,...,N}{1,2,...,N} such that |Λ0|≤K|Λ0|≤K. For any vector u∈RNu∈RN, define Λ1Λ1 as the index set corresponding to the KK largest entries of uΛ0cuΛ0c (in absolute value), Λ2Λ2 as the index set corresponding to the next KK largest entries, and so on. Then

∑ j ≥ 2 u Λ j 2 ≤ u Λ 0 c 1 K . ∑ j ≥ 2 u Λ j 2 ≤ u Λ 0 c 1 K .
(6)

Proof

We begin by observing that for j≥2j≥2,

u Λ j ∞ ≤ u Λ j - 1 1 K u Λ j ∞ ≤ u Λ j - 1 1 K
(7)

since the ΛjΛj sort uu to have decreasing magnitude. Applying standard bounds on ℓpℓp norms (Lemma 1 from "The RIP and the NSP") we have

∑ j ≥ 2 u Λ j 2 ≤ K ∑ j ≥ 2 u Λ j ∞ ≤ 1 K ∑ j ≥ 1 u Λ j 1 = u Λ 0 c 1 K , ∑ j ≥ 2 u Λ j 2 ≤ K ∑ j ≥ 2 u Λ j ∞ ≤ 1 K ∑ j ≥ 1 u Λ j 1 = u Λ 0 c 1 K ,
(8)

proving the lemma.

We are now in a position to prove our main result. The key ideas in this proof follow from [1].

Lemma 4

Suppose that ΦΦ satisfies the RIP of order 2K2K. Let Λ0Λ0 be an arbitrary subset of {1,2,...,N}{1,2,...,N} such that |Λ0|≤K|Λ0|≤K, and let h∈RNh∈RN be given. Define Λ1Λ1 as the index set corresponding to the KK entries of hΛ0chΛ0c with largest magnitude, and set Λ=Λ0∪Λ1Λ=Λ0∪Λ1. Then

h Λ 2 ≤ α h Λ 0 c 1 K + β Φ h Λ , Φ h h Λ 2 , h Λ 2 ≤ α h Λ 0 c 1 K + β Φ h Λ , Φ h h Λ 2 ,
(9)

where

α = 2 δ 2 K 1 - δ 2 K , β = 1 1 - δ 2 K . α = 2 δ 2 K 1 - δ 2 K , β = 1 1 - δ 2 K .
(10)

Proof

Since hΛ∈Σ2KhΛ∈Σ2K, the lower bound on the RIP immediately yields

( 1 - δ 2 K ) h Λ 2 2 ≤ Φ h Λ 2 2 . ( 1 - δ 2 K ) h Λ 2 2 ≤ Φ h Λ 2 2 .
(11)

Define ΛjΛj as in Lemma 3, then since ΦhΛ=Φh-∑j≥2ΦhΛjΦhΛ=Φh-∑j≥2ΦhΛj, we can rewrite Equation 11 as

( 1 - δ 2 K ) h Λ 2 2 ≤ Φ h Λ , Φ h - Φ h Λ , ∑ j ≥ 2 Φ h Λ j . ( 1 - δ 2 K ) h Λ 2 2 ≤ Φ h Λ , Φ h - Φ h Λ , ∑ j ≥ 2 Φ h Λ j .
(12)

In order to bound the second term of Equation 12, we use Lemma 2, which implies that

Φ h Λ i , Φ h Λ j ≤ δ 2 K h Λ i 2 h Λ j 2 , Φ h Λ i , Φ h Λ j ≤ δ 2 K h Λ i 2 h Λ j 2 ,
(13)

for any i,ji,j. Furthermore, Lemma 1 yields hΛ02+hΛ12≤2hΛ2hΛ02+hΛ12≤2hΛ2. Substituting into Equation 13 we obtain

Φ h Λ , ∑ j ≥ 2 Φ h Λ j = ∑ j ≥ 2 Φ h Λ 0 , Φ h Λ j + ∑ j ≥ 2 Φ h Λ 1 , Φ h Λ j ≤ ∑ j ≥ 2 Φ h Λ 0 , Φ h Λ j + ∑ j ≥ 2 Φ h Λ 1 , Φ h Λ j ≤ δ 2 K h Λ 0 2 ∑ j ≥ 2 h Λ j 2 + δ 2 K h Λ 1 2 ∑ j ≥ 2 h Λ j 2 ≤ 2 δ 2 K h Λ 2 ∑ j ≥ 2 h Λ j 2 . Φ h Λ , ∑ j ≥ 2 Φ h Λ j = ∑ j ≥ 2 Φ h Λ 0 , Φ h Λ j + ∑ j ≥ 2 Φ h Λ 1 , Φ h Λ j ≤ ∑ j ≥ 2 Φ h Λ 0 , Φ h Λ j + ∑ j ≥ 2 Φ h Λ 1 , Φ h Λ j ≤ δ 2 K h Λ 0 2 ∑ j ≥ 2 h Λ j 2 + δ 2 K h Λ 1 2 ∑ j ≥ 2 h Λ j 2 ≤ 2 δ 2 K h Λ 2 ∑ j ≥ 2 h Λ j 2 .
(14)

From Lemma 3, this reduces to

Φ h Λ , ∑ j ≥ 2 Φ h Λ j ≤ 2 δ 2 K h Λ 2 h Λ 0 c 1 K . Φ h Λ , ∑ j ≥ 2 Φ h Λ j ≤ 2 δ 2 K h Λ 2 h Λ 0 c 1 K .
(15)

Combining Equation 15 with Equation 12 we obtain

( 1 - δ 2 K ) h Λ 2 2 ≤ Φ h Λ , Φ h - Φ h Λ , ∑ j ≥ 2 Φ h Λ j ≤ Φ h Λ , Φ h + Φ h Λ , ∑ j ≥ 2 Φ h Λ j ≤ Φ h Λ , Φ h + 2 δ 2 K h Λ 2 h Λ 0 c 1 K , ( 1 - δ 2 K ) h Λ 2 2 ≤ Φ h Λ , Φ h - Φ h Λ , ∑ j ≥ 2 Φ h Λ j ≤ Φ h Λ , Φ h + Φ h Λ , ∑ j ≥ 2 Φ h Λ j ≤ Φ h Λ , Φ h + 2 δ 2 K h Λ 2 h Λ 0 c 1 K ,
(16)

which yields the desired result upon rearranging.

References

  1. Candès, E. (2008). The restricted isometry property and its implications for compressed sensing. Comptes rendus de l'Académie des Sciences, Série I, 346(9-10), 589–592.

Collection Navigation

Content actions

Download 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