Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » Introduction to Compressive Sensing » The cross-polytope and phase transitions

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

The cross-polytope and phase transitions

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

Summary: In this module we provide an overview of the relationship between L1 minimization and random projections of the cross-polytope.

The analysis of 11 minimization based on the restricted isometry property (RIP) described in "Signal recovery in noise" allows us to establish a variety of guarantees under different noise settings, but one drawback is that the analysis of how many measurements are actually required for a matrix to satisfy the RIP is relatively loose. An alternative approach to analyzing 11 minimization algorithms is to examine them from a more geometric perspective. Towards this end, we define the closed 11 ball, also known as the cross-polytope:

C N = x R N : x 1 1 . C N = x R N : x 1 1 .
(1)

Note that CNCN is the convex hull of 2N2N points {pi}i=12N{pi}i=12N. Let ΦCNRMΦCNRM denote the convex polytope defined as either the convex hull of {Φpi}i=12N{Φpi}i=12N or equivalently as

Φ C N = y R M : y = Φ x , x C N . Φ C N = y R M : y = Φ x , x C N .
(2)

For any xΣK = x : x 0 K xΣK = x : x 0 K , we can associate a KK-face of CNCN with the support and sign pattern of xx. One can show that the number of KK-faces of ΦCNΦCN is precisely the number of index sets of size KK for which signals supported on them can be recovered by

x ^ = argmin z z 1 subject to z B ( y ) . x ^ = argmin z z 1 subject to z B ( y ) .
(3)

with B(y)={z:Φz=y}B(y)={z:Φz=y}. Thus, 11 minimization yields the same solution as 00 minimization for all xΣKxΣK if and only if the number of KK-faces of ΦCNΦCN is identical to the number of KK-faces of CNCN. Moreover, by counting the number of KK-faces of ΦCNΦCN, we can quantify exactly what fraction of sparse vectors can be recovered using 11 minimization with ΦΦ as our sensing matrix. See [1], [2], [3], [4], [5] for more details and [6] for an overview of the implications of this body of work. Note also that by replacing the cross-polytope with certain other polytopes (the simplex and the hypercube), one can apply the same technique to obtain results concerning the recovery of more limited signal classes, such as sparse signals with nonnegative or bounded entries [6].

Given this result, one can then study random matrix constructions from this perspective to obtain probabilistic bounds on the number of KK-faces of ΦCNΦCN with ΦΦ is generated at random, such as from a Gaussian distribution. Under the assumption that K=ρMK=ρM and M=γNM=γN, one can obtain asymptotic results as NN. This analysis leads to the phase transition phenomenon, where for large problem sizes there are sharp thresholds dictating that the fraction of KK-faces preserved will tend to either one or zero with high probability, depending on ρρ and γγ [6].

These results provide sharp bounds on the minimum number of measurements required in the noiseless setting. In general, these bounds are significantly stronger than the corresponding measurement bounds obtained within the RIP-based framework given in "Noise-free signal recovery", which tend to be extremely loose in terms of the constants involved. However, these sharper bounds also require somewhat more intricate analysis and typically more restrictive assumptions on ΦΦ (such as it being Gaussian). Thus, one of the main strengths of the RIP-based analysis presented in "Noise-free signal recovery" and "Signal recovery in noise" is that it gives results for a broad class of matrices that can also be extended to noisy settings.

References

  1. Donoho, D. (2005, Jan.). Neighborly polytopes and sparse solutions of underdetermined linear equations. (2005-04). Technical report. Stanford Univ., Stat. Dept.
  2. Donoho, D. (2006). High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension. Discrete and Comput. Geometry, 35(4), 617–652.
  3. Donoho, D. and Tanner, J. (2005). Neighborliness of randomly projected simplices in high dimensions. Proc. Natl. Acad. Sci., 102(27), 9452–9457.
  4. Donoho, D. and Tanner, J. (2005). Sparse Nonnegative Solutions of Undetermined Linear Equations by Linear Programming. Proc. Natl. Acad. Sci., 102(27), 9446–9451.
  5. Donoho, D. and Tanner, J. (2009). Counting faces of randomly-projected polytopes when the projection radically lowers dimension. J. Amer. Math. Soc., 22(1), 1–53.
  6. Donoho, D. and Tanner, J. (2010). Precise undersampling theorems. Proc. IEEE, 98(6), 913–924.

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

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