Skip to content Skip to navigation

Connexions

You are here: Home » Content » Optimality and the MRIP

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

      A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

      What is in a lens?

      Lens makers point to Connexions 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 Connexions member, a community, or a respected organization.

    • External bookmarks
  • E-mail the authors

Recently Viewed

Optimality and the MRIP

Module by: Wai Lam Chan, Ronald DeVore

From our last lecture, we are interested in signals x∈R N x∈R N , and we can make nn measurements (or ask nn questions) to obtain y=Φx∈R n y=Φx∈R n . We proposed several optimality criteria to make these measurements, i.e., to choose the measurement matrix ΦΦ.

  1. For signals x∈Σ k x∈Σ k (with kk non-zero coefficients), we choose an encoder ΦΦ and the corresponding decoder, ΔΔ, such that Δ(Φ(x))=xΔ(Φ(x))=x.
  2. For classes of signals e.g. K=U(ℓ p N )K=U(ℓ p N ), our performance measure is closely related to the Gelfand widths.
  3. Instance Optimal: our encoder and decoder, ΦΦ and ΔΔ, should satisfy
| | x - Δ Φ ( x ) | | ℓ p ≤ C 0 σ k ( x ) ℓ p . | | x - Δ Φ ( x ) | | ℓ p ≤ C 0 σ k ( x ) ℓ p .(1)

We see that criterion (3) implies (1) since σ k ( x ) ℓ p =0 σ k ( x ) ℓ p =0 for x∈Σ k x∈Σ k . We also showed in the previous lecture that we have instance optimality for order kk if and only if we have the Null Space Property (NSP) of order 2k2k. As a reminder, NSP of order 2k2k means that ∀η∈N,N=x:Φ(x)=0∀η∈N,N=x:Φ(x)=0, we have ∥ η ∥ ℓ p ≤ C 1 σ 2 k ( η ) ℓ p ∥ η ∥ ℓ p ≤ C 1 σ 2 k ( η ) ℓ p . In other words, elements of η∈Nη∈N are not sparse, and they are all of approximately equal size (i.e., they do not concentrate their entries in 2k 2k positions).

We mentioned that, in order to attain instant optimality, the n×Nn×N measurement matrix ΦΦ should have the modified restricted isometry property (MRIP) of order mm, i.e., when we choose any mm columns of ΦΦ to obtain a n×mn×m sub-matrix Φ T Φ T where m≤nm≤n,

C 2 - 1 | | x T | | ℓ 2 ≤ | | Φ T x T | | ℓ 2 ≤ C 2 | | x T | | ℓ 2 . C 2 - 1 | | x T | | ℓ 2 ≤ | | Φ T x T | | ℓ 2 ≤ C 2 | | x T | | ℓ 2 . (2)

theorem 1

If ΦΦ has MRIP for m=3km=3k, then ΦΦ has NSP for ℓ 1 ℓ 1 of order 2 k 2 k , and so ΦΦ is instance optimal in ℓ 1 ℓ 1 of order kk, i.e.,

| | x - Δ Φ ( x ) | | ℓ 1 ≤ C σ k ( x ) ℓ 1 . | | x - Δ Φ ( x ) | | ℓ 1 ≤C σ k ( x ) ℓ 1 . (3)
A related result is that under the same assumption,
| | x - Δ Φ ( x ) | | ℓ 2 ≤ C σ k ( x ) ℓ 1 k . | | x - Δ Φ ( x ) | | ℓ 2 ≤ C σ k ( x ) ℓ 1 k . (4)

Proof

To prove (Equation 3), we need to only show NSP for ℓ 1 ℓ 1 and 2k2k, i.e.,

| | η | | ℓ 1 ≤ C σ 2 k ( η ) ℓ 1 , η ∈ N . | | η | | ℓ 1 ≤ C σ 2 k ( η ) ℓ 1 , η ∈ N . (5)
Given ηη, let T 0 T 0 be the set of indices of the 2k2k largest entries, T 1 T 1 be the set of indices of the kk next largest entries, T 2 T 2 be the set of indices of the kk next largest entries, and so on.
η 0 =η T 0 +η T 1 ,η=η T 0 +η T 1 +...+η T s ,Φ(η)=Φ(η T 0 +η T 1 +...+η T s )=0,Φ(η 0 )=-Φ(η T 2 +...+η T s ),bylinearity=-∑ j=2 s Φ(η T j ).η 0 =η T 0 +η T 1 ,η=η T 0 +η T 1 +...+η T s ,Φ(η)=Φ(η T 0 +η T 1 +...+η T s )=0,Φ(η 0 )=-Φ(η T 2 +...+η T s ),bylinearity=-∑ j=2 s Φ(η T j ).(6)
Therefore, we can estimate
| | η 0 | | ℓ 2 ≤ C 2 | | Φ ( η 0 ) | | ℓ 2 , by restricted isometry ≤ C 2 ∑ j = 2 s | | Φ ( η T j ) | | ℓ 2 , by triangle inequality ≤ C 2 2 ∑ j = 2 s | | η T j | | ℓ 2 , by restricted isometry . | | η 0 | | ℓ 2 ≤ C 2 | | Φ ( η 0 ) | | ℓ 2 , by restricted isometry ≤ C 2 ∑ j = 2 s | | Φ ( η T j ) | | ℓ 2 , by triangle inequality ≤ C 2 2 ∑ j = 2 s | | η T j | | ℓ 2 , by restricted isometry . (7)
Since, for j≥2j≥2, η T j η T j is the best k-term approximation to η T j-1 +η T j η T j-1 +η T j ,

| | η T j | | ℓ 2 = σ k ( η T j - 1 + η T j ) ℓ 2 . | | η T j | | ℓ 2 = σ k ( η T j - 1 + η T j ) ℓ 2 . (8)

Furthermore, we know for any q<pq<p,

σ k ( η ) ℓ p ≤ k 1 p - 1 q | | x | | ℓ q . σ k ( η ) ℓ p ≤ k 1 p - 1 q | | x | | ℓ q . (9)

Combining (Equation 8) and (Equation 9), we obtain

| | η T j | | ℓ 2 ≤ | | η T j - 1 + η T j | | ℓ 1 k . | | η T j | | ℓ 2 ≤ | | η T j - 1 + η T j | | ℓ 1 k .(10)

Substituting (Equation 10) back into (Equation 7), we now have

| | η 0 | | ℓ 2 ≤ C 2 2 k ∑ j=2 s || η T j-1 + η T j || ℓ 1 ≤ C 2 2 k ∑ j=2 s | | η T j - 1 | | ℓ 1 + | | η T j | | ℓ 1 ≤ 2 C 2 2 k ∑ j=1 s | | η T j | | ℓ 1 ≤2C 2 2 k σ 2 k ( η ) ℓ 1 . | | η 0 | | ℓ 2 ≤ C 2 2 k ∑ j=2 s || η T j-1 + η T j || ℓ 1 ≤ C 2 2 k ∑ j=2 s | | η T j - 1 | | ℓ 1 + | | η T j | | ℓ 1 ≤ 2 C 2 2 k ∑ j=1 s | | η T j | | ℓ 1 ≤2C 2 2 k σ 2 k ( η ) ℓ 1 .(11)

The last step is due to the fact that ∑ j=1 s | | η T j | | ℓ 1 ∑ j=1 s | | η T j | | ℓ 1 is the 2k2k-term approximation error for ηη. Notice this is only true for ℓ 1 ℓ 1 . This completes the proof of (Equation 4).

To prove (Equation 3), we let x j x j be the jj-th entry in η T 0 η T 0 . By the Cauchy-Schwarz Inequality,

| | η T 0 | | ℓ 1 = ∑ j=1 2k |x j |≤∑ j=1 2k 1 2 1 2 ∑ j=1 2k |x j | 2 1 2 ,byCSI = 2k | | η T 0 | | ℓ 2 ≤ 2k | | η 0 | | ℓ 2 ≤22C 2 2 σ 2 k ( η ) ℓ 1 , | | η T 0 | | ℓ 1 = ∑ j=1 2k |x j |≤∑ j=1 2k 1 2 1 2 ∑ j=1 2k |x j | 2 1 2 ,byCSI = 2k | | η T 0 | | ℓ 2 ≤ 2k | | η 0 | | ℓ 2 ≤22C 2 2 σ 2 k ( η ) ℓ 1 ,(12)

The 2k2k-term approximation error in ℓ 1 ℓ 1 for ηη can be expressed as

| | η T 1 + ... + η T s | | ℓ 1 = σ 2 k ( η ) ℓ 1 . | | η T 1 + ... + η T s | | ℓ 1 = σ 2 k ( η ) ℓ 1 .(13)

Since

η=η T 0 +(η T 1 +...+η T s ),η=η T 0 +(η T 1 +...+η T s ),(14)

we can finally prove that

| | η | | ℓ 1 ≤ | | η T 0 | | ℓ 1 + | | η T 1 + ... + η T s | | ℓ 1 , by triangle inequality = 22C 2 2 σ 2 k ( η ) ℓ 1 + σ 2 k ( η ) ℓ 1 =(22C 2 2 +1) σ 2 k ( η ) ℓ 1 . | | η | | ℓ 1 ≤ | | η T 0 | | ℓ 1 + | | η T 1 + ... + η T s | | ℓ 1 , by triangle inequality = 22C 2 2 σ 2 k ( η ) ℓ 1 + σ 2 k ( η ) ℓ 1 =(22C 2 2 +1) σ 2 k ( η ) ℓ 1 .(15)

Therefore, we have proved ((Reference)) with C=22C 2 2 +1C=22C 2 2 +1.□□

Comments, questions, feedback, criticisms?

Send feedback