# Connexions

You are here: Home » Content » ℓ_1 minimization proof

### 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 11 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 pp norms (Lemma 1 from "The RIP and the NSP") with K=2K=2, we have w12w2w12w2. 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 uRNuRN, 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 j2j2,

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 pp 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 hRNhRN 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-j2ΦhΛjΦhΛ=Φh-j2Φ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Λ122hΛ2hΛ02+hΛ122hΛ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.

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

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

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?

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