<< Chapter < Page Chapter >> Page >

Review: denoising in smooth function spaces i - method of sieves

Suppose we make noisy measurements of a smooth function:

Y i = f * ( x i ) + W i , i = { 1 , ... , n } ,

where

W i i . i . d . N 0 , σ 2

and

x i = i n .

The unknown function f * is a map

f * : [ 0 , 1 ] R .

In Lecture 4 , we consider this problem in the case where f * was Lipschitz on [ 0 , 1 ] . That is, f * satisfied

| f * ( t ) - f * ( s ) | L | t - s | , t , s [ 0 , 1 ]

where L > 0 is a constant. In that case, we showed that by using a piecewise constant function on a partition of n 1 3 equal-size bins [link] we were able to obtain an estimator f ^ n whose mean square error was

E f * - f ^ n 2 = O n - 2 3 .
Example of the piecewise constant approximation of f *

In this lecture we will use the Maximum Complexity-Regularized Likelihood Estimation result we derived in Lecture 14 to extend our denoising scheme in several important ways.

To begin with let's consider a broader class of functions.

Hölder spaces

For 0 < α < 1 , define the space of functions

H α ( C α ) = | f | < C α : sup x , h | f ( x + h ) - f ( x ) | | h | α C α

for some constant C α < and where f L . H α above contains functions that are bounded, but less smooth than Lipschitz functions. Indeed, the space of Lipschitzfunctions can be defined as H 1 ( α = 1 )

H 1 ( C 1 ) = | f | < C 1 : sup x , h | f ( x + h ) - f ( x ) | | h | C 1

for C 1 < . Functions in H 1 are continuous, but those in H α , α < 1 , are not in general.

Let's also consider functions that are smoother than Lipschitz. If α = 1 + β , where 0 < β < 1 , then define

H α ( C α ) = f H 1 ( C α ) : f x H β ( C α ) .

In other words, H α , 1 < α < 2 , contains Lipschitz functions that are also differentiable and their derivatives are Hölder smooth with smoothness β = α - 1 .

And finally, let

H 2 ( C 2 ) = f : f x H 1 ( C 2 )

contain functions that have continuous derivatives, but that are notnecessarily twice-differentiable.

If f H α ( C α ) , 0 < α 2 , then we say that f is Hölder - α smooth with Hölder constant C α . The notion of Hölder smoothness can also be extended to α > 2 in a straightforward way.

Note: If α 1 < α 2 then

f H α 2 f H α 1 .

Summarizing, we can describe Hölder spaces as follows. If f * H α C α for some 0 < α 2 and C α < , then

  • 0 < α 1                    | f * ( t ) - f * ( s ) | C α | t - s | α
  • 1 < α 2                    f * x ( t ) - f * x ( s ) C α | t - s | α - 1

Note that in general there is a natural relationship between the Hölder space containing the function and the approximation classused to estimate the function. Here we will consider functions which are Hölder - α smooth where 0 < α 2 and work with piecewise linear approximations. If we were to consider smootherfunctions, α > 2 we would need consider higher order approximation functions, i.e. quadratic, cubic, etc.

Denoising example for signal-plus-gaussian noise observation model

Now let's assume f * H α ( C α ) for some unknown α ( 0 < α 2 ) ; i.e. we don't know how smooth f * is. We will use our observations

Y i = f * ( x i ) + W i , i = { 1 , ... , n } ,

to construct an estimator f ^ n . Intuitively, the smoother f * is, the better we should be able to estimate it. Can we take advantage ofextra smoothness in f * if we don't know how smooth it is? The smoother f * is, the more averaging we can perform to reduce noise. In other words for smoother f * we should average over larger bins. Also, we will need to exploit the extra smoothnessin our approximation of f * . To that end, we will consider candidate functions that are piecewiselinear functions on uniform partitions of [ 0 , 1 ] . Let

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Statistical learning theory. OpenStax CNX. Apr 10, 2009 Download for free at http://cnx.org/content/col10532/1.3
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Statistical learning theory' conversation and receive update notifications?

Ask