Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » Compressive Sensing » Greedy Algorithms

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.
 

Greedy Algorithms

Module by: Jason Laska, Ronald DeVore. E-mail the authors

We now turn to the questions of generating good approximations for nn term approximation from a general dictionary We shall assume that the dictionary DD is complete in the Hilbert space HH. This means that every element in HH can be approximated arbitrarily well by linear combinations of the elements of DD. Since the dictionary is no longer an orthogonal basis as was considered above, we need to revisit how to find good nn term approximations. Because of redundancy within the dictionary, we cannot simply pick the largest coefficients as we saw with a basis. Greedy algorithms are a method to generate good nn term approximations.

  1. General Greedy Algorithm Given ff, we want to generate an nn-term approximation to ff.
    f→s=∑ s=1 n c j g j f→s=∑ s=1 n c j g j
    (1)
    The general steps are as follows:
    1. Initialize: (approximation) s 0 =0s 0 =0, (residual) r 0 =fr 0 =f, approximation collectionΛ 0 =∅Λ 0 =∅
    2. Search DD for some g∈Dg∈D, then add gg to the set ΛΛ.
    3. Use {g 1 ,g 2 ,...,g n }{g 1 ,g 2 ,...,g n } to find new approximation for s n s n .
    At stage nn, we have s n s n , r n =f-s n r n =f-s n , and Λ n ={g 1 ,g 2 ,...,g n }Λ n ={g 1 ,g 2 ,...,g n }. There are many types of greedy algorithms. We describe the three most common in the case SS is a Hilbert space. However, there are anlaogues of these for L p L p .
  2. Pure Greedy Algorithm (PGA) Note: >From r n r n choose g n+1 := argmax |r n (f),g|g n+1 := argmax |r n (f),g| (the gg that causes the largest inner product).
    s n+1 =s n +r n (f),ggs n+1 =s n +r n (f),gg
    (2)
    r n+1 =f-s n -f-s n ,gg=f-s n+1 r n+1 =f-s n -f-s n ,gg=f-s n+1
    (3)
    This method is similar to a steepest decent algorithm for decreasing the error.
  3. Orthogonal Greedy Algorithm (OGA) >From r n r n choose g n+1 := argmax |r n (f),g|g n+1 := argmax |r n (f),g| as in the PGA.
    V n+1 :=sp{g 1 ,g 2 ,...,g n+1 }V n+1 :=sp{g 1 ,g 2 ,...,g n+1 }
    (4)
    s n+1 :=p V n+1 f=∑ j=1 n+1 α j g j s n+1 :=p V n+1 f=∑ j=1 n+1 α j g j
    (5)
    where P V P V denotes the orthogonal projection onto the space VV. We can find s n+1 =P V n+1 fs n+1 =P V n+1 f by solving the linear system of equations
    ∑ j=1 n+1 α j g j ,g k =f,g k .∑ j=1 n+1 α j g j ,g k =f,g k .
    (6)
    Then, r n+1 =f-s n+1 r n+1 =f-s n+1 .
  4. Relaxed Greedy Algorithm (RGA) >From r n r n choose g n+1 g n+1 in some way (for example, our earlier methods) and then define
    s n+1 (f)=αs n +βg n+1 s n+1 (f)=αs n +βg n+1
    (7)
    Unlike PGA, here we do not make a full step in the correct direction. For example, one way to proceed is to define
    arginf α,β,g ∥f-αs n +βg n ∥=:α * ,β * ,g * arginf α,β,g ∥f-αs n +βg n ∥=:α * ,β * ,g *
    (8)
    This type of greedy algorithm is known to perform the best as compred with the previous two.

Measuring Performance

Given XX, DD, it is not practical to minimize σ n (f) X σ n (f) X by searching over all the possibilities. The greedy approximation gives an nn-term solution with less computation, but does it perform well?

Let

L 1 (D):={f∈X:∑c g g,∑ g∈D |c g |≤M}L 1 (D):={f∈X:∑c g g,∑ g∈D |c g |≤M}
(9)

where the smallest MM is the L 1 L 1 norm of ff.

Theorem 1

For OGA or RGA as described above, we have

∥f-s n f∥≤Cn -1 2 |f| L 1 .∥f-s n f∥≤Cn -1 2 |f| L 1 .
(10)

remark 1

Remark 5 This is similar to σ n (x) l 2 ≤n -1 2 ∥x∥ l 1 σ n (x) l 2 ≤n -1 2 ∥x∥ l 1 (nn-term approximation) but its not always quite as good.

Collection Navigation

Content actions

Download 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