# Connexions

You are here: Home » Content » An Introduction to Compressive Sensing » Null space conditions

### Recently Viewed

This feature requires Javascript to be enabled.

Inside Collection (Course):

# Null space conditions

Summary: This module introduces the spark and the null space property, two common conditions related to the null space of a measurement matrix that ensure the success of sparse recovery algorithms. Furthermore, the null space property is shown to be a necessary condition for instance optimal or uniform recovery guarantees.

A natural place to begin in establishing conditions on ΦΦ in the context of designing a sensing matrix is by considering the null space of ΦΦ, denoted

N ( Φ ) = { z : Φ z = 0 } . N ( Φ ) = { z : Φ z = 0 } .
(1)

If we wish to be able to recover all sparse signals xx from the measurements ΦxΦx, then it is immediately clear that for any pair of distinct vectors x,x'ΣK = x : x 0 K x,x'ΣK = x : x 0 K , we must have ΦxΦx'ΦxΦx', since otherwise it would be impossible to distinguish xx from x'x' based solely on the measurements yy. More formally, by observing that if Φx=Φx'Φx=Φx' then Φ(x-x')=0Φ(x-x')=0 with x-x'Σ2Kx-x'Σ2K, we see that ΦΦ uniquely represents all xΣKxΣK if and only if N(Φ)N(Φ) contains no vectors in Σ2KΣ2K. There are many equivalent ways of characterizing this property; one of the most common is known as the spark [2].

## The spark

Definition 1:
The spark of a given matrix ΦΦ is the smallest number of columns of ΦΦ that are linearly dependent.

This definition allows us to pose the following straightforward guarantee.

### Theorem 1: (Corollary 1 of [2])

For any vector yRMyRM, there exists at most one signal xΣKxΣK such that y=Φxy=Φx if and only if spark (Φ)>2K spark (Φ)>2K.

#### Proof

We first assume that, for any yRMyRM, there exists at most one signal xΣKxΣK such that y=Φxy=Φx. Now suppose for the sake of a contradiction that spark (Φ)2K spark (Φ)2K. This means that there exists some set of at most 2K2K columns that are linearly independent, which in turn implies that there exists an hN(Φ)hN(Φ) such that hΣ2KhΣ2K. In this case, since hΣ2KhΣ2K we can write h=x-x'h=x-x', where x,x'ΣKx,x'ΣK. Thus, since hN(Φ)hN(Φ) we have that Φ(x-x')=0Φ(x-x')=0 and hence Φx=Φx'Φx=Φx'. But this contradicts our assumption that there exists at most one signal xΣKxΣK such that y=Φxy=Φx. Therefore, we must have that spark (Φ)>2K spark (Φ)>2K.

Now suppose that spark (Φ)>2K spark (Φ)>2K. Assume that for some yy there exist x,x'ΣKx,x'ΣK such that y=Φx=Φx'y=Φx=Φx'. We therefore have that Φ(x-x')=0Φ(x-x')=0. Letting h=x-x'h=x-x', we can write this as Φh=0Φh=0. Since spark (Φ)>2K spark (Φ)>2K, all sets of up to 2K2K columns of ΦΦ are linearly independent, and therefore h=0h=0. This in turn implies x=x'x=x', proving the theorem.

It is easy to see that spark (Φ)[2,M+1] spark (Φ)[2,M+1]. Therefore, Theorem 1 yields the requirement M2KM2K.

## The null space property

When dealing with exactly sparse vectors, the spark provides a complete characterization of when sparse recovery is possible. However, when dealing with approximately sparse signals we must introduce somewhat more restrictive conditions on the null space of ΦΦ [1]. Roughly speaking, we must also ensure that N(Φ)N(Φ) does not contain any vectors that are too compressible in addition to vectors that are sparse. In order to state the formal definition we define the following notation that will prove to be useful throughout much of this course. Suppose that Λ{1,2,,N}Λ{1,2,,N} is a subset of indices and let Λc={1,2,,N}ΛΛc={1,2,,N}Λ. By xΛxΛ we typically mean the length NN vector obtained by setting the entries of xx indexed by ΛcΛc to zero. Similarly, by ΦΛΦΛ we typically mean the M×NM×N matrix obtained by setting the columns of ΦΦ indexed by ΛcΛc to zero.1

Definition 2:

A matrix ΦΦ satisfies the null space property (NSP) of order KK if there exists a constant C>0C>0 such that,

h Λ 2 C h Λ c 1 K h Λ 2 C h Λ c 1 K
(2)

holds for all hN(Φ)hN(Φ) and for all ΛΛ such that |Λ|K|Λ|K.

The NSP quantifies the notion that vectors in the null space of ΦΦ should not be too concentrated on a small subset of indices. For example, if a vector hh is exactly KK-sparse, then there exists a ΛΛ such that hΛc1=0hΛc1=0 and hence Equation 2 implies that hΛ=0hΛ=0 as well. Thus, if a matrix ΦΦ satisfies the NSP then the only KK-sparse vector in N(Φ)N(Φ) is h=0h=0.

To fully illustrate the implications of the NSP in the context of sparse recovery, we now briefly discuss how we will measure the performance of sparse recovery algorithms when dealing with general non-sparse xx. Towards this end, let Δ:RMRNΔ:RMRN represent our specific recovery method. We will focus primarily on guarantees of the form

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

for all xx, where we recall that

σ K ( x ) p = min x ^ Σ K x - x ^ p . σ K ( x ) p = min x ^ Σ K x - x ^ p .
(4)

This guarantees exact recovery of all possible KK-sparse signals, but also ensures a degree of robustness to non-sparse signals that directly depends on how well the signals are approximated by KK-sparse vectors. Such guarantees are called instance-optimal since they guarantee optimal performance for each instance of xx [1]. This distinguishes them from guarantees that only hold for some subset of possible signals, such as sparse or compressible signals — the quality of the guarantee adapts to the particular choice of xx. These are also commonly referred to as uniform guarantees since they hold uniformly for all xx.

Our choice of norms in Equation 3 is somewhat arbitrary. We could easily measure the reconstruction error using other pp norms. The choice of pp, however, will limit what kinds of guarantees are possible, and will also potentially lead to alternative formulations of the NSP. See, for instance, [1]. Moreover, the form of the right-hand-side of Equation 3 might seem somewhat unusual in that we measure the approximation error as σK(x)1/KσK(x)1/K rather than simply something like σK(x)2σK(x)2. However, we will see later in this course that such a guarantee is actually not possible without taking a prohibitively large number of measurements, and that Equation 3 represents the best possible guarantee we can hope to obtain (see "Instance-optimal guarantees revisited").

Later in this course, we will show that the NSP of order 2K2K is sufficient to establish a guarantee of the form Equation 3 for a practical recovery algorithm (see "Noise-free signal recovery"). Moreover, the following adaptation of a theorem in [1] demonstrates that if there exists any recovery algorithm satisfying Equation 3, then ΦΦ must necessarily satisfy the NSP of order 2K2K.

### Theorem 2: (Theorem 3.2 of [1])

Let Φ:RNRMΦ:RNRM denote a sensing matrix and Δ:RMRNΔ:RMRN denote an arbitrary recovery algorithm. If the pair (Φ,Δ)(Φ,Δ) satisfies Equation 3 then ΦΦ satisfies the NSP of order 2K2K.

#### Proof

Suppose hN(Φ)hN(Φ) and let ΛΛ be the indices corresponding to the 2K2K largest entries of hh. We next split ΛΛ into Λ0Λ0 and Λ1Λ1, where |Λ0|=|Λ1|=K|Λ0|=|Λ1|=K. Set x=hΛ1+hΛcx=hΛ1+hΛc and x'=-hΛ0x'=-hΛ0, so that h=x-x'h=x-x'. Since by construction x'ΣKx'ΣK, we can apply Equation 3 to obtain x'=Δ(Φx')x'=Δ(Φx'). Moreover, since hN(Φ)hN(Φ), we have

Φ h = Φ x - x ' = 0 Φ h = Φ x - x ' = 0
(5)

so that Φx'=ΦxΦx'=Φx. Thus, x'=Δ(Φx)x'=Δ(Φx). Finally, we have that

h Λ 2 h 2 = x - x ' 2 = x - Δ ( Φ x ) 2 C σ K ( x ) 1 K = 2 C h Λ c 1 2 K , h Λ 2 h 2 = x - x ' 2 = x - Δ ( Φ x ) 2 C σ K ( x ) 1 K = 2 C h Λ c 1 2 K ,
(6)

where the last inequality follows from Equation 3.

## Footnotes

1. We note that this notation will occasionally be abused to refer to the length |Λ||Λ| vector obtained by keeping only the entries corresponding to ΛΛ or the M×|Λ|M×|Λ| matrix obtained by only keeping the columns corresponding to ΛΛ. The usage should be clear from the context, but typically there is no substantive difference between the two.

## References

1. Cohen, A. and Dahmen, W. and DeVore, R. (2009). Compressed sensing and best k-term approximation. J. Amer. Math. Soc., 22(1), 211–231.
2. Donoho, D. and Elad, M. (2003). Optimally sparse representation in general (nonorthogonal) dictionaries via L1 minimization. Proc. Natl. Acad. Sci., 100(5), 2197–2202.

## 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.

PDF | EPUB (?)

### What is an EPUB file?

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

#### 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?

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?

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

### Reuse / Edit:

Reuse or edit collection (?)

#### Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

#### Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.

| Reuse or edit module (?)

#### Check out and edit

If you have permission to edit this content, using the "Reuse / Edit" action will allow you to check the content out into your Personal Workspace or a shared Workgroup and then make your edits.

#### Derive a copy

If you don't have permission to edit the content, you can still use "Reuse / Edit" to adapt the content by creating a derived copy of it and then editing and publishing the copy.