David Donoho, Department of Statistics, Stanford University Guest

Posted: Sun Jan 10, 1993 4:37 am Subject: Papers on wavelet de_noising available




Papers on wavelet de_noising available
The following papers may be obtained via anonymous FTP
from playfair.stanford.edu.
David Donoho donoho@playfair.stanford.edu
Iain Johnstone imj@playfair.stanford.edu

David L. Donoho and Iain M. Johnstone
"Minimax Estimation via Wavelet Shrinkage"
TR 402, July 1992, Submitted for publication.
mews.dvi
We attempt to recover an unknown function from noisy, sampled data.
Using orthonormal bases of compactly supported wavelets we develop a
nonlinear method which works in the wavelet domain by simple nonlinear
shrinkage of the empirical wavelet coefficients. The shrinkage can be
tuned to be nearly minimax over any member of a wide range of Triebel
and Besovtype smoothness constraints, and asymptotically minimax over
Besov bodies with $p leq q$. Linear estimates cannot achieve even the
minimax rates over Triebel and Besov classes with $p < 2$, so our
method can significantly outperform every linear method (kernel,
smoothing spline, sieve, dots) in a minimax sense. Variants of our
method based on simple threshold nonlinearities are nearly minimax.
Our method possesses the interpretation of {em spatial adaptivity/}:
it reconstructs using a kernel which may vary in shape and bandwidth
from point to point, depending on the data. Least favorable
distributions for certain of the Triebel and Besov scales generate
objects with sparse wavelet transforms. Many real objects have
similarly sparse transforms, which suggests that these minimax results
are relevant for practical problems. Sequels to this paper discuss
practical implementation, spatial adaptation properties and
applications to inverse problems.

David L. Donoho and Iain M. Johnstone
"Ideal Spatial Adaptation via Wavelet Shrinkage"
TR 400, July 1992, Submitted for publication.
isaws.dvi, isaws1.ps, isaws2.ps, ... , isaws10.ps
(Figs 1  10)
With {it ideal spatial adaptation}, an oracle furnishes information
about how best to adapt a spatially variable estimator  piecewise
constant, piecewise polynomial, variable knot spline, or variable
bandwidth kernel  to the unknown function. Estimation with the aid
of an oracle offers dramatic advantages over traditional linear
estimation by nonadaptive kernels; however, it is {it a priori}
unclear whether such performance can be obtained by a procedure
relying on the data alone.
We describe a new principle for spatiallyadaptive estimation {it
selective wavelet reconstruction}. We show that %variablebandwidth
kernels, variableknot spline fits and piecewisepolynomial fits, when
equipped with an oracle to select the knots, are not dramatically more
powerful than selective wavelet reconstruction with an oracle.
We develop a practical spatially adaptive method, {it WaveSelect},
which works by shrinkage of empirical wavelet coefficients. {it
WaveSelect} mimics the performance of an oracle for selective wavelet
reconstruction as well as it is possible to do so. A new inequality
in multivariate normal decision theory which we call the {it oracle
inequality} shows that attained performance differs from ideal
performance by at most a factor $ sim 2 log(n)$, where $n$ is the
sample size. Moreover no measurable function of the data can give a
better guarantee than this.
Within the class of spatially adaptive procedures, {it WaveSelect} is
essentially optimal. Relying only on the data, it comes within a
factor $log^2(n)$ of the performance of piecewise polynomial and
variableknot spline methods equipped with an oracle. In contrast, it
is unknown how or if piecewise polynomial methods could be made to
function this well when denied access to an oracle and forced to rely
on data alone.

David L. Donoho and Iain M. Johnstone
"Minimax risk over $l_p$balls for $l_q$error"
July 1992, Submitted for publication
Revision of TR 322, May 1989
mrlp.dvi
Consider estimating the mean vector $ heta$ from data $N_n( heta ,
sigma^2 I )$ with $l_q$ norm loss, $q geq 1$, when $ heta$ is known
to lie in an $n$dimensional $l_p$ ball, $p in (0, infty )$. For
large $n$, the ratio of minimax sl linear
m risk to minimax risk
can be {em arbitrarily large} if $p < q$. Obvious exceptions aside,
the limiting ratio equals 1 only if $p=q=2$. Our arguments are mostly
indirect, involving a reduction to a univariate Bayes minimax problem.
When $p<q$, simple nonlinear coordinatewise threshold rules are
asymptotically minimax at small signaltonoise ratios, and within a
bounded factor of asymptotic minimaxity in general. Our results are
basic to a theory of estimation in Besov spaces using wavelet bases
(to appear elsewhere).

David L. Donoho
"Nonlinear Solution of Linear Inverse Problems by WaveletVaguelette
Decomposition"
TR 403 July 1992, Submitted for publication
nslip.dvi
We describe the WaveletVaguelette Decomposition (WVD) of a linear
inverse problem. It is a substitute for the singular value
decomposition (SVD) of an inverse problem, and it exists for a class
of special inverse problems of homogeneous type  such as numerical
differentiation, inversion of Abeltype transforms, certain
convolution transforms, and the Radon Transform.
We propose to solve illposed linear inverse problems by nonlinearly
``shrinking" the WVD coefficients of the noisy, indirect data. Our
approach offers significant advantages over traditional SVD inversion
in the case of recovering spatially inhomogeneous objects.
We suppose that observations are contaminated by white noise and that
the object is an unknown element of a Besov space. We prove that
nonlinear WVD shrinkage can be tuned to attain the minimax rate of
convergence, for $L^2$ loss, over the entire Besov scale. The
important case of Besov spaces $Bspq$, $p <2$, which model spatial
inhomogeneity, is included. In comparison, linear procedures  SVD
included  cannot attain optimal rates of convergence over such
classes in the case $p<2$. For example, our methods achieve faster
rates of convergence, for objects known to lie in the Bump Algebra or
in Bounded Variation, than any linear procedure.

David L. Donoho
"Interpolating Wavelet Transforms"
TR 408 November 1992, Submitted for publication
Interpol.tex (LATEX)
egin{abstract}
We describe several ``wavelet transforms" which characterize
smoothness spaces and for which the coefficients are obtained
by sampling rather than integration. We use them to reinterpret
the empirical wavelet transform, i.e. the common practice
of applying pyramid filters to samples of a function.
end{abstract}
{f Key Words and Phrases.} Interpolating
Wavelet Transform. Interpolating Spline Wavelets.
Interpolating DeslauriersDubuc Wavelets. Wavelet transforms of Sampled
Data. Wavelet Interpolation of Sampled Data. Wavelets on the Interval.

David L. Donoho
"Unconditional Bases are Optimal Bases for Data Compression and
for Statistical Estimation"
TR 410 November 1992, Submitted for publication
UBRelease.tex (LATEX)
egin{abstract}
An orthogonal basis of $L^2$ which is also an
unconditional basis of a functional space $cal F$ is a kind
of optimal basis for compressing, estimating, and recovering
functions in $cal F$. Simple thresholding operations,
applied in the unconditional basis,
work essentially better for compressing,
estimating, and recovering than they do in any other orthogonal basis.
In fact, simple thresholding in an unconditional basis works essentially
better for recovery and estimation than other methods, period.
(Performance is measured in an asymptotic minimax sense.)
As an application, we formalize and prove Mallat's Heuristic,
which says that wavelet bases are optimal for representing functions
containing singularities, when there may be an arbitrary
number of singularities, arbitrarily distributed.
end{abstract}
{f Key Words.}
Unconditional Basis, Optimal Recovery, weak$ell^p$ spaces.
Minimax Decision theory. Besov, H"older, Sobolev, Triebel Spaces.
Thresholding of Wavelet Coefficients.

David L. Donoho
"DeNoising via Soft Thresholding"
TR 409 November 1992, Submitted for publication
denoiserelease3.tex (LATEX)
egin{abstract}
Donoho and Johnstone (1992a)
proposed a method for
reconstructing an unknown function $f$ on $[0,1]$
from noisy data $d_i =f(t_i ) + sigma z_i$,
$i=1, dots,n $, $t_i = i/n$, $z_i stackrel{iid}{sim} N(0,1)$.
The reconstruction $f_n^*$ is
defined in the wavelet domain by translating all the empirical wavelet
coefficients of $d$ towards 0 by an amount $sqrt{2 log (n)} cdot sa /
sqrt{n}$. We prove two results about that estimator. [Smooth]: With high
probability $f_n^*$ is at least as smooth as $f$, in any of a wide variety
of smoothness measures. [Adapt]: The estimator comes nearly as close in
mean square to $f$ as any measurable estimator can come, uniformly over
balls in each of
two broad scales of smoothness classes. These two properties
are unprecedented in several ways. Our
proof of these results develops new facts about abstract statistical
inference and its connection with an optimal recovery model.
The abstract model also applies to other types of
noisy observations, such as higherdimensional samples
and area samples.
end{abstract}
{f Key Words and Phrases.} Empirical Wavelet Transform. Minimax
Estimation. Adaptive Estimation. Optimal Recovery. 
