Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Compressive Sensing » Gelfand n-widths

Navigation

Lenses

What is a lens?

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.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

Also in these lenses

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.
 

Continuing from last time, we have a signal xR N xR N , an n×Nn×N measurement matrix ΦΦ, and y=ΦxR n y=ΦxR n is the information we draw from xx.

We consider decoders ΔΔ mapping R n R N R n R N . We have been discussing whether there exists a decoder with certain properties. So for this discussion (about information preservation), we can just think about optimal decoding.

While the previous result on sparse signal recovery is interesting, it is not very robust. What happens if our signal does not have support kk? Can we still obtain meaningful results? The answer is yes. To do so we introduce more general input signal classes KXKX that allows fully supported signals. For example, we will consider the signal class defined by the unit ball

K = U ( p N ) = { x : x X 1 } . K=U( p N )={x: x X 1}.
(1)
Given an encoder/decoder pair ( Φ , Δ ) (Φ,Δ), the worst case error on a set KK for that pair will be given by
E ( K , Φ , Δ ) X = sup x K x Δ ( Φ x ) X . E ( K , Φ , Δ ) X = sup x K x Δ ( Φ x ) X .
(2)
Finally, using min-max principles we will define the minimum error over all encoder/decoder pairs for a signal class and for a fixed number of measurements nn to be
E n ( K ) X = inf ( Φ , Δ ) : Φ is n×N E ( K , Φ , Δ ) X . E n ( K ) X = inf ( Φ , Δ ) : Φ is n×N E ( K , Φ , Δ ) X .
(3)
This measure E n (K) X E n (K) X is the best we could do while measuring distortion on the topology of XX, using nn linear measurements, and using arbitrary decoding.

We will see that these questions are actually equivalent to a classical “nn-width” problem. nn-widths have seen a great deal of work over the years by a variety of mathematicians: Kolmogorov, Tikhomirov, Kashin, Gluskin, etc. There are many different flavors of nn-widths, but we will study the Gelfand nn-width (the least intuitive of the widths).

definition 1: Gelfand n-width

Let KXKX be compact. Given nn, the Gelfand width (also called the dual width) is given by

d n (K) X := inf Y : codim (Y) = n sup { x X : xKY} . d n (K) X := inf Y : codim (Y) = n sup{ x X :xKY}.
(4)
where by codimension (Y)=n codimension (Y)=n we mean that YY has dimension dim (X)n dim (X)n.

In other words, we are looking for the subspace YY that slices through the set KK so that the norms of the projected signals are as small as possible. We can now state the following theorem about n-widths:

Theorem 1

Provided that KK has the properties (1) K=-KK=-K and (2) K+K=CKK+K=CK, then

d n (K) X E n (K) X Cd n (K) X d n (K) X E n (K) X Cd n (K) X
(5)
where CC is the same constant listed in property (2).1

Proof

We start with the left-hand inequality. We want to take any encoder/decoder pair and use that to construct a YY. So let Φ,ΔΦ,Δ be an encoder/decoder. Then simply let Y=N(Φ)Y=N(Φ). Now consider an ηKYηKY and note that Φ(η)=0Φ(η)=0 since ηYηY. Let z=Δ(0)z=Δ(0) be the decoding of 0 (practically speaking, zz should be zero itself, but we avoid that assumption in this proof). Then

η X max(η-z X ,η+z X )=max(η-ΔΦ(η) X ,-η-ΔΦ(η) X ) sup xK x - Δ Φ (x) X η X max(η-z X ,η+z X )=max(η-ΔΦ(η) X ,-η-ΔΦ(η) X ) sup xK x - Δ Φ (x) X
(6)
where we first employ the triangle inequality, then the fact that multiplying by -1-1 does not change the norm, then the fact that K=-KK=-K. So then
sup ηKY η X sup xK x - Δ Φ ( x ) X . sup ηKY η X sup xK x - Δ Φ ( x ) X .
(7)
Taking the infimum over all Φ,ΔΦ,Δ, it follows that
d n (K) X E n (K) X . d n (K) X E n (K) X .
(8)
Since ΦΦ is n×Nn×N, then dim (N(Φ))N-n dim (N(Φ))N-n.

Now we prove the right-hand inequality. Assume we have a good YY. Suppose YY has codimension N-nN-n. Then Y Y (the orthogonal complement of YY in R N R N ) has dimension nn. Let v 1 ,v 2 ,,v n R N v 1 ,v 2 ,,v n R N be a basis for Y Y . Let ΦΦ be the n×Nn×N matrix obtained by stacking the rows v 1 ,v 2 ,,v n v 1 ,v 2 ,,v n . Then N(Φ)=YN(Φ)=Y. Define Δ(y)=Δ(y)= any element of KF(y)KF(y) if there is one (otherwise let Δ(y)Δ(y) be anything in F(y)F(y)). Now look at the performance x-ΔΦ(x) X x-ΔΦ(x) X for some xKxK. Both xx and ΔΦ(x)=:x ' ΔΦ(x)=:x ' are elements of KK, so x-x ' x-x ' is in N(Φ)N(Φ) and in CKCK. Therefore x-x ' CKN(Φ)x-x ' CKN(Φ). Thus,

x - x ' C X sup z Y K z X , x - x ' C X sup z Y K z X ,
(9)
and so for any xKxK,
x-ΔΦ(x) X Csup zYK z X .x-ΔΦ(x) X Csup zYK z X .
(10)
Taking the infimum over all YY, we get that E n (K) X C d n (K) X E n (K) X C d n (K) X .

From the proof of this theorem, we see that there is a matching between the matrices ΦΦ and the spaces YY (via the nullspace of ΦΦ).

An important result is that d n (U( q N ) ) p N d n (U( q N ) ) p N is known for all p,qp,q except p=1,q=p=1,q=. A precise statement of these widths can be found in the book (Reference). A particularly important case is

C 1 log ( N / n ) n d n ( U ( 1 N ) ) 2 N C 2 log ( N / n ) n C 1 log ( N / n ) n d n ( U ( 1 N ) ) 2 N C 2 log ( N / n ) n
(11)
for N>2nN>2n. This result was first proved by Kashin with a worse logarithm in the upper inequality and later brought to the present form by Gluskin. This result solves several important problems in functional analysis and approximation.

Footnotes

  1. Clarifying notation: CK={Cx:xK}CK={Cx:xK} and K+K={x1+x2:x1,x2K}K+K={x1+x2:x1,x2K}.

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