<< Chapter < Page Chapter >> Page >

We shall next discuss some notions related to best n -term approximation.

Thresholding

  • Let X be a Hilbert space. Given f , let Λ ϵ ( f ) = { j : | c j ( f ) | > ϵ } . The thresholding operator T ϵ is defined by
    T ϵ f = j Λ ϵ ( f ) C j ( f ) φ j .
    It is easy to see that for each ϵ , T ϵ f is the best approximation to f using N terms where N is the cardinality of Λ ϵ :
    f - T ϵ X = σ N ( f ) X .
    Thresholding is easily implemented on a computer.
  • The thresholding scheme above can be generalized if X is not a Hilbert space provided the dictionary has some specific structure. For example, when
    • The dictionary is the wavelet basis and X = L p , 1 < p < .
    • X = l p and the dictionary is the canonical basis δ j = φ j . ex: ( 0 , 0 , ... , 1 , 0 )
    • For a general Banach space X and the dictionary ( φ j ) is a greedy basis.

Greedy bases

We briefly describe the notion of greedy basis.

Given X , we say ( φ j ) is a greedy basis for X if for each ϵ > 0 ,

f - T ϵ f X C ( X ) σ N ( f ) X

where N is the cardinality of Λ ϵ .

A basis φ j is said to be unconditional if

± c j φ j X C c j φ j X

or equivalently

c j φ j X C d j φ j X where | c j | | d j | .

This is an older concept from functional analysis. In words, this definition says that if the terms c j are rearranged, the series c j φ j will still converge. This is not generally true for all bases.

A basis φ j is said to be democratic if

j Λ φ j C j Λ ' φ j ,

where the cardinality of Λ ' equals the cardinality of Λ .

( φ j ) greedy ( φ j ) is both unconditional and democratic.

Some examples involving the last two definitions:

  • The fourier basis in L p is not democratic, but is unconditional for l < p < .
  • The wavelet basis contains both of these properties, and is therefore greedy.

If X = L p has ( φ j ) greedy, B = { φ j } , f = j = 1 c j ( f ) φ j , c j ( f ) = f , ψ j where ψ j is a dual basis,

f A r ( B ) ( c j ( f ) ) w l τ , 1 τ = r + 1 p

and

f A r c j ( f ) l τ

Let us now consider a specific setting that we shall be concerned with a lot in this course. We shall examine some of the conceptswe have introduced in the finite dimensional space of of all sequence (points) in R N . Recall that we can put many different norms on this space including the p norms and the weak p norms.

Given a vector = ( x 1 , x 2 , ... , x N ) R N . The best approximation to x from Σ n in the p norm is to take the vector in Σ n which shares the n largest values of x . Its error of approximation satisfies

σ n ( x ) p C n - r x w l τ , 1 τ = r + 1 p

x w l τ x l τ , 1 τ = r + 1 p .

For p = 1 and r = 3 , σ n ( x ) 1 C n - 3 x w l τ and 1 τ = 4 . In words, this equation shows what kind of τ is needed for a given decay rate (or given some τ , what kind of decay rate will be achieved) to approximate with certain ability.

Show σ n ( x ) l p C n - r x l τ holds with C = 1 .

Proof: Let Λ n : = { i : | x i | largest } ,

σ n ( x ) l p p = i Λ n | x i | p
i Λ n | x i | p - τ | x i | τ
( x w l τ n - 1 τ ) p - τ ( | x i | τ )
x l τ p - τ x l τ τ n = n - r p x l τ p

and so

σ n ( x ) l p p n - r p x l τ p

σ n ( x ) l p n - r x l τ

For X = L p , { φ j } a wavelet basis, we can say wavelet coefficients of f are in l p is equivalent to f is in a certain Besov class (roughly speaking f has r derivatives and f ( r ) L τ ). We refer the reader to for precise formulations of results of this type.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Compressive sensing. OpenStax CNX. Sep 21, 2007 Download for free at http://cnx.org/content/col10458/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Compressive sensing' conversation and receive update notifications?

Ask