0.15 Denoising ii: adapting to unknown smoothness  (Page 2/2)

The start and end points of each line segment are each one of $\sqrt{n}$ discrete values, as indicated in [link] . Since each line may start at any of the $\sqrt{n}$ levels and terminate at any of the $\sqrt{n}$ levels, there are a total of $n$ possible lines for each segment.

Given that there are $k$ intervals we have

Therefore we can use $klogn$ bits to describe a function $f\in {\mathcal{F}}_k$ .

Let

Construct a prefix code for every $f\in \mathcal{F}$ by

Thus, if $f\in {\mathcal{F}}_k$ , then the prefix code associated with $f$ has codeword length

which satisfies the Kraft Inequality

Now we will apply our complexity regularization result to select a function ${\widehat{f}}_n$ from $\mathcal{F}$ and bound its risk. We are assuming Gaussian errors, so

We can ignore the constant term and so our empirical selection is

We can compute ${\widehat{f}}_n$ according to:

For $k=1,...,n$

then select

and finally

Because the KL divergence and $-2log$ affinity simply reduce to squared error in the Gaussian case (Lecture 14) , we arrive at a relatively simple bound on the mean square error of ${\widehat{f}}_n$

The first term in the brackets above is related to the error incurred by approximating $f^{*}$ by an element of $\mathcal{F}.$ The second term is related to the estimation error involved with the model selection process.

Let's focus on the approximation error. First, suppose $f^{*}\in H^{\alpha }\left(C_{\alpha }\right)$ for $1<\alpha \le 2.$ Let $f_k^{*}$ be the “best" piecewise linear approximation to $f^{*}$ , with $k$ pieces on intervals $\left[0,,,\frac{1}{k}\right),\left[\frac{1}{k},,,\frac{2}{k}\right),...\left[\frac{k-1}{k},,,1\right).$ Consider the difference between $f^{*}$ and $f_k^{*}$ on one such interval, say $\left[\frac{i-1}{k},,,\frac{i}{k}\right).$ By applying Taylor's theorem with remainder we have

for $t\in \left[\frac{i-1}{k},,,\frac{i}{k}\right)$ and some $t^{\text{'}}\in \left[t,,,\frac{i}{k}\right]$ . Define

Note that $f_k^{*}\left(t\right)$ is not necessarily the best piecewise linear approximation to $f^{*}$ , just good enough for our purposes. Then using the fact that $f^{*}\in H^{\alpha }\left(C_{\alpha }\right)$ , for $t\in [i-1/k,i/k)$ we have

So, for all $t\in [0,1]$

Now let $f_k$ be the element of ${\mathcal{F}}_k$ closest to $f_k^{*}$ ( $f_k$ is the quantized version of $f_k^{*}$ )

since we used $\frac{1}{2}logn$ bits to quantize the endpoints of each line segment. Consequently,

Thus it follows that

The first and last terms dominate the above expression. Therefore, the upper bound is minimizedwhen $k^{-2\alpha }$ and $\frac{k}{n}$ are balanced. This is accomplished by choosing $k=\lfloor n^{\frac{1}{2\alpha +1}}\rfloor .$ Then it follows that

If $\alpha =2$ then we have

If $f^{*}\in H^{\alpha }\left(C_{\alpha }\right)$ for $0<\alpha \le 1$ , let $f_k^{*}$ be the following piecewise constant approximation to $f^{*}.$ Let

Then

Repeating the same reasoning as in the $1<\alpha \le 2$ case, we arrive at

for $0<\alpha \le 1.$ In particular, for $\alpha =1$ we get

within a logarithmic factor of the rate we had before (in Lecture 4 ) for that case!

Summary

1. ${\widehat{f}}_n$ can be computed by finding least-square line fits to the data on partitions of the form $\left[0,,,\frac{1}{k}\right),\left[\frac{1}{k},,,\frac{2}{k}\right),...\left[\frac{k-1}{k},,,1\right)$ for $k=1,...,n,$ and then selecting the best fit by the $\widehat{k}$ that gives the minimum of the complexity regularization criterion.
2. If $f^{*}\in H^{\alpha }\left(C_{\alpha }\right)$ for some $0<\alpha \le 2,$ then
   $$MSE\left({\widehat{f}}_n\right)=\frac{1}{n}\sum _{i=1}^{n}E\left[{\left({\widehat{f}}_n,\left(\frac{i}{n}\right),-,f^{*},\left(\frac{i}{n}\right)\right)}^2\right]=O\left(n^{-\frac{2\alpha }{2\alpha +1}},log,n\right).$$
3. ${\widehat{f}}_n$ automaticallypicks the optimal number of bins. Essentially ${\widehat{f}}_n$ (indirectly) estimates the smoothness of $f^{*}$ and produces a rate which is near minimax optimal ! ( $n^{-\frac{2\alpha }{2\alpha +1}}$ is the best possible).
4. The larger $\alpha$ is the faster the convergence and the better the denoising !