Inside Collection (Course): An Introduction to Compressive Sensing

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

Suppose

We begin by defining the

Since

If

Suppose

Finally, applying the parallelogram identity

establishes the lemma.

Let

We begin by observing that for

since the

proving the lemma.

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

Suppose that

where

Since

Define

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

for any

From Lemma 3, this reduces to

Combining Equation 15 with Equation 12 we obtain

which yields the desired result upon rearranging.

- « Previous module in collection Proof of the RIP for sub-Gaussian matrices
- Collection home: An Introduction to Compressive Sensing