[Home]
[Back Issues]
[Search]
[Vol 1]
[Vol 2]
[Vol 3]
[Vol 4]
[Vol 5]
The Wavelet Digest - Volume 2, Issue 10 (July 12, 1993)
Today's Editor: Wim Sweldens
sweldens@math.sc.edu
Today's Topics:
1. New text related to wavelets
2. Papers on wavelet de-noising available electronically.
3. Preprint available: Adaptive Wavelet Collocation Methods for Initial Value Boundary Problems of Nonlinear PDE's
4. Contents Numerical Algorithms
5. Contents Advances in Computational Mathematics
6. Question: Wavelets and remote sensing.
7. Wavelet software in S: version 2.2
8. PhD Thesis available: Wavelets and Filter Banks
Submissions for Wavelet Digest:
E-mail to wavelet@math.sc.edu with "submit" as subject.
Subscriptions for Wavelet Digest:
E-mail to wavelet@math.sc.edu with "subscribe" as subject.
To unsubscribe, e-mail with "unsubscribe" followed by your e-mail
address as subject. To change address, unsubscribe and resubscribe.
Archive site and back issues:
Anonymous ftp to maxwell.math.sc.edu (129.252.12.3),
directory /pub/wavelet/archive.
Gopher server: bigcheese.math.sc.edu.
Current number of subscribers: 2761
From: Frank Stenger, University of Utah, e-mail: stenger@sinc.utah.edu
Subject: New text related to wavelets
I wish to announce the publication of my text, "Numerical Methods Based on
Sinc and Analytic Functions", by Springer-Verlag (ISBN 0-387-94008-1).
This text uses analytic function methods to derive the symbolic formulae
based on sinc functions, their approximation properties and error, and the
derivation of numerical algorithms based on these symbolic formulae for
solving a large class of problems stemming from applications. For example,
the DFT formula, which yields the well-known FFT procedure is one of the
formulas of the class, but there are many others, such as new methods of
interpolation, quadrature, the approximation of derivatives, the
approximation of one and multidimensional indefinite or definite convolution
integrals, the approximate solution of ordinary differential equations, and
the approximation of Hilbert transforms, over arbitrary intervals or contours.
Included also are new methods of solving elliptic, parabolic, and hyperbolic
partial differential equations, new methods of solving linear and nonlinear
Volterra, Fredholm, multidimensional, and Cauchy singular integral equations,
and new methods of evaluating and inverting Laplace and Fourier transforms.
For example, the complexity, i.e., the amount of work required to obtain an
approximate solution of a partial differential equation in d dimensions to
within a tolerance of E is usually of the order of {log(E)}**(2d+2).
The methods excel for problems with end-point singularities, for problems
over semi-infinite or infinite regions, or for boundary layer problems.
From: David Donoho, Department of Statistics, Stanford University.
Subject: Papers on wavelet de-noising available electronically.
To get these, use anonymous FTP to playfair.stanford.edu. After
connecting "cd pub/reports", then "ls" to get a listing of available files,
and "get filename" to get a specific file. Files are in
either LaTex or Plain tex and figures are in postscript.
Questions? e-mail Iain Johnstone (imj@playfair.stanford.edu)
or Dave Donoho (donoho@playfair.stanford.edu).
---
David L. Donoho, Iain M. Johnstone, G\'erard Kerkyacharian
and Dominique Picard.
"Wavelet Shrinkage: Asymptopia"
TR 419, March 1993, Submitted for publication
asymp.tex (LaTex)
Considerable effort has been directed recently to develop
asymptotically minimax methods in problems of recovering
infinite-dimensional objects (curves, densities, spectral densities,
images) from noisy data. A rich and complex body of work has evolved,
with nearly- or exactly- minimax estimators being obtained for a
variety of interesting problems. Unfortunately, the results have
often not been translated into practice, for a variety of reasons --
sometimes, similarity to known methods, sometimes, computational
intractability\ , and sometimes, lack of spatial adaptivity. We
discuss a method for curve estimation based on $n$ noisy data; one
translates the empirical wavelet coefficients towards the origin by an
amount $\sqrt{2 \log(n)} \sa /\sqrt{n}$. The method is different from
methods in common use today, is computationally practical, and is
spatially adaptive; thus it avoids a number of previous objections to
minimax estimators. At the same time, the method is nearly minimax
for a wide variety of loss funct\ ions -- e.g. pointwise error, global
error measured in $L^p$ norms, pointwise and global error in
estimation of derivatives -- and for a wide range of smoothness
classes, including standard H\"{o}lder classes, Sobolev classes, and
Bounded Variation. This is a much broader near-optimality than
anything previously proposed in the minimax literature. Finally, the
theory underlying the method is interesting, as it exploits a
correspondence between statistical questions and questions of optimal
recovery and information-based complexity.
---
David L. Donoho and Iain M. Johnstone
"Adapting to Unknown Smoothness via Wavelet Shrinkage
June 1993, Submitted for publication
ausws.tex (LaTex)
We attempt to recover a function of unknown smoothness from noisy,
sampled data. We introduce a procedure, {\it SureShrink}, which
suppresses noise by thresholding the empirical wavelet coefficients.
The thresholding is adaptive: a threshold level is assigned to each
dyadic resolution level by the principle of minimizing the Stein
Unbiased Estimate of Risk ({\it Sure}) for threshold estimates. The
computational effort of the overall procedure is order $N \cdot
\log(N)$ as a function of the sample size $N$.
{\it SureShrink} is smoothness-adaptive: if the unknown function
contains jumps, the reconstruction (essentially) does also; if the
unknown function has a smooth piece, the reconstruction is
(essentially) as smooth as the mother wavelet will allow. The
procedure is in a sense optimally smoothness-adaptive: it is
near-minimax simultaneously over a whole interval of the Besov scale;
the size of this interval depends on the choice of mother wavelet. We
know from a previous paper by the authors that traditional smoothing
methods -- kernels, splines, and orthogonal series estimates -- even
with optimal choices of the smoothing parameter, would be unable to
perform in a near-minimax way over many spaces in the Besov scale.
Examples of {\it SureShrink} are given: the advantages of the method
are particularly evident when the underlying function has jump
discontinuities on a smooth background.
---
David L. Donoho, Iain M. Johnstone, G\'erard Kerkyacharian
and Dominique Picard.
"Density estimation by wavelet thresholding"
June 1993, Submitted for publication
dens.tex (LaTex)
Density estimation is a commonly used test case for non-parametric
estimation methods. We explore the asymptotic properties of estimators
based on thresholding of empirical wavelet coefficients. Minimax rates
of convergence are studied over a large range of Besov function
classes $B_{s,p,q}$ and for a range of global $L_p' $ error measures,
$1 \leq p' < \infty$. A single wavelet threshold estimator is
asymptotically minimax within logarithmic terms simultaneously over a
range of spaces and error measures. In particular, when $p' > p$, some
form of non-linearity is essential, since the minimax linear
estimators are suboptimal by polynomial powers of $n$. A second
approach, using an approximation of a Gaussian white noise model in a
Mallows metric, is used to attain exactly optimal rates of convergence
for quadratic error ($p' = 2$).
---
Iain M. Johnstone
"Minimax Bayes, asymptotic minimax and sparse wavelet priors"
TR 420, April 1993, To appear, Proc. 5th Purdue Symposium on Decision Theory.
priors.tex (LaTex)
Pinsker(1980) gave a precise asymptotic evaluation of the minimax mean
squared error of estimation of a signal in Gaussian noise when the
signal is known \it a priori \rm to lie in a compact ellipsoid in
Hilbert space. This `Minimax Bayes' method can be applied to a
variety of global non-parametric estimation settings with parameter
spaces far from ellipsoidal. For example it leads to a theory of
exact asymptotic minimax estimation over norm balls in Besov and
Triebel spaces using simple co-ordinatewise estimators and wavelet
bases.
This paper outlines some features of the method common to several
applications. In particular, we derive new results on the exact
asymptotic minimax risk over weak $\ell_p$- balls in ${\cal R}^n$ as
$n \rightarrow \infty $, and also for a class of `local' estimators on
the Triebel scale.
By its very nature, the method reveals the structure of asymptotically
least favorable distributions. Thus we may simulate `least favorable'
sample paths. We illustrate this for estimation of a signal in
Gaussian white noise over norm balls in certain Besov spaces. In
wavelet bases, when $p < 2$, the least favorable priors are sparse,
and the resulting sample paths strikingly different from those
observed in Pinsker's ellipsoidal setting ($p=2$).
---
Smooth Wavelet Decompositions with blocky coefficient Kernels
David L. Donoho
May, 1993. To Appear: ``Recent Advances in Wavelet Analysis''
Schumaker and Webb, Eds. Academic Press.
blocky.tex (Plain Tex)
7 figures -- blockyps.shar
We describe bases of smooth
wavelets where the coefficients are obtained
by integration against (finite combinations of) boxcar kernels rather
than against traditional smooth wavelets. Bases of this type
were first developed in work of Tchamitchian
and of Cohen, Daubechies, and Feauveau.
Our approach emphasizes the idea of
{\it average-interpolation} -- synthesizing
a smooth function on the line having prescribed boxcar averages --
and the link between average-interpolation and Dubuc-Deslauriers
interpolation. We also emphasize characterizations of smooth
functions via their coefficients.
We describe boundary-corrected expansions for the interval, which
have a simple and revealing form.
We use these results to re-interpret the {\it empirical
wavelet transform} -- i.e. finite, discrete wavelet transforms
of data arising from boxcar integrators (e.g. CCD devices).
---
Wavelet Shrinkage and W.V.D. -- A ten-minute tour
David L. Donoho
January, 1993. To Appear, Proc. Toulouse Conference on Wavelets and Appl.,
S. Roques Ed., Springer-Verlag, 1993.
toulouse.tex (plain tex)
15 figures -- toulouseps.shar
A brief tour of applications of thresholding of wavelet coefficients
for denosing, and for solving inverse problems such as deconvolution
and numerical differentiation.
From: Wei Cai, Department of Mathematics, University of North Carolina.
Subject: Preprint available:
Preprint can be requested for the following paper:
"Adaptive Wavelet Collocation Methods for
Initial Value Boundary Problems of Nonlinear PDE's"
Authors: Wei Cai
Department of Mathematics,
University of North Carolina at Charlotte
Charlotte, NC 28223
JianZhong Wang
Department of Mathematics, Wuhan University
Wuhan, P.R. China
ABSTRACT
We have designed a cubic spline wavelet decomposition for the
Sobolev space $H^2_0(I)$ where $I$ is a bounded interval.
Based on a special ``point-wise orthogonality'' of the wavelet
basis functions, a fast Discrete Wavelet Transform (DWT) is constructed.
This DWT transform will map discrete samples of a function to its
wavelet expansion coefficients in $O(N\log{N})$ operations.
Using this transform, we propose a collocation method
for the initial value boundary problem of nonlinear PDE's.
Then, we test the efficiency of the DWT transform and
apply the collocation method to solve linear and nonlinear PDE's.
point of contact for preprint:
wcai@mosaic.uncc.edu
From: Laurenz Baltzer
Subject: Contents Numerical Algorithms
Editor-in-Chief:
Claude Brezinski
Laboratoire d'Analyse Numerique et d'Optimization
VOLUME 4, NO. 3:
Y. Xu, W.A. Light and E.W. Cheney, Constructive methods of approximation by
ridge functions and radial functions
P. Levrie and A. Bultheel, A note on Thiele n-fractions
M.A. Diniz-Ehrhardt and J.M. Martinez, A parallel projection method for
overdetermined nonlinear systems of equations
Nguyen huu Cong, A-stable diagonally implicit Runge-Kutta-Nystrom methods
for parallel computers
M. Calvo, J.I. Montijano and L. Randez, On the change of step size in
multistep codes
VOLUME 4, NO. 4:
S. Durand, Convergence of cascade algorithms introduced by I. Daubechies
K. Strom, Products of B-patches
C. Clavero and F. Lisbona, Uniformly convergent finite difference methods
for singularly perturbed problems with turning points
K. Jbilou, A general projection algorithm for solving systems of linear
equations
P. Joly and G. Meurant, Complex conjugate gradient methods
Orders and requests for sample copies to be sent to J.C. Baltzer AG,
Science Publishers, Wettsteinplatz 10, CH-4058 Basel, Switzerland, fax:
+41-61-692-42-62, e-mail: publish@baltzer.nl
Laurenz Baltzer, J.C.Baltzer AG, Science Publishers
Asterweg 1A, 1031 HL Amsterdam, The Netherlands
Tel: +31 20 6370061, Fax: +31 20 6323651
From: Laurenz Baltzer
Subject: Contents Advances in Computational Mathematics
Editors-in-Chief:
John C. Mason
Applied & Computational Mathematics Group
Royal Military College of Science
Charles A. Micchelli
Mathematical Sciences Department
IBM Research Center
Volume 1, no. 1
W. Dahmen & C.A. Micchelli, Continuous refinement equations and subdivision
P.J. van der Houwen, Preconditioning in implicit initial value problem
methods on parallel computers
H.N. Mhaskar, Approximation properties of a multilayered feedforward
artificial neural network
A.R. Champneys & A. Spence, Hunting for homoclinic orbits in reversible
systems: a shooting technique
T.N.T. Goodman, S.L. Lee & W.S. Tang, Wavelet bases for a set of commuting
unitary operators
R.E. Bank & C.C. Douglas, Sparse matrix multiplication package (SMMP)
Volume 1, no. 2
P.J. Barry, R.N. Goldman & C.A. Micchelli, Knot insertion algorithms for
piecewise polynomial spaces determined by connection matrices
J.M. Carnicer & J. M. Pena, Shape preserving representations and
optimality of the Bernstein basis
R.A. DeVore, G. Kyriazis, D. Leviaton & V.M. Tikhomirov,
Wavelet-compression and nonlinear n-widths
D.E. Gonsor, Nonnegative masks and stationary subdivision
W.B. Liu & J.W. Barrett, Error bounds for the finite element approximation
of a degenerate quasilinear parabolic variational inequality
L. Reichel, Construction of polynomials that are orthogonal with respect to
a discrete bilinear form
Orders and requests for sample copies to be sent to J.C. Baltzer AG,
Science Publishers, Wettsteinplatz 10, CH-4058 Basel, Switzerland, fax:
+41-61-692-42-62, e-mail: publish@baltzer.nl
From: Afshin Amini, Hughes Aircraft Co.
Subject: Question: wavelets and remote sensing.
Hi,
I am trying to collect information on the usage of wavelets in the field of
remote sensing. I came across a paper by Thierry Ranchin and Lucien Wald of
Center d'Energetique-Groupe Teledection & Modelisation, Ecole des Mines de
Paris named " The wavelet transform for the analysis of remotely sensed images"
which was published in the INT. J. REMOTE SENSING, 1993, VOL 14, NO. 3
In there there are references to a proceeding : "Proceedings of the 12th EARSEL
symposium on Remote sensing for monitoring the changing environment of Europe,
8-11 September 1992, Eger, Hungary" which has been since published by
Rotterdam, The Netherlands: A. A. Balkema.
I am interested to see if anybody has those papers in that Proceeding which
are also by Ranchin. Also, any other source of information would be greatly
appreciated.
I will post the info, if i get anything.
Thanks,
A. Amini, Hughes Aircraft Co.
EO/E51/B282, PO Box 902, El Segundo, CA 90245
email : amini@newt.edsg.hac.com
From: G. P. Nason, School of Mathematical Sciences, University of Bath
Sujbect: Wavelet software in S: version 2.2
Wavelet transforms and thresholding in 1 and 2 dimensions for s
Version 2.2
WHAT: S software to compute the 1- and 2-dimensional wavelet transform
using Mallat's pyramidal algorithm with Daubechies compactly supported
orthonormal wavelets and incorporating an implementation of the
thresholding ideas of Donoho and Johnstone.
Package consists of:
* S functions that compute the 1- and 2-dimensional
discrete wavelet transform, and inverse. (Uses
dynamically loaded C code)
* S functions to perform thresholding
* S functions to plot and interpret sets of wavelet coefficients
* Full on-line S help
NEW IN RELEASE 2.2
* extra method of boundary handling, periodic functions
* new family of wavelets added, Daubechies' least-asymmetric
* new function "draw" that produces nice pictures of
one- and two dimensional wavelets
* new class iwmdc added and facilities to automatically
compress thresholded image wavelet decomp. objects
* improvements to Makefile and automatic dynamic loading.
(Thanks to Peter Clifford, Howard Grubb, and Martin Maechler for
providing suggestions and improvements for wavethresh 2.2)
WHERE: Obtain via anonymous FTP from gdr.bath.ac.uk
Userid "anonymous" and your email address as the password.
Software is in directory /pub/masgpn as the file "wavethresh2.2.Z"
The transfer should be done using the BINARY transfer mode of ftp
and then the files should be uncompressed using the UNIX command
"uncompress". The software can then be unpacked by typing
(on a UNIX machine)
% sh wavethresh2.2
Extra draft documentation is in "dws.ps.Z" - a compressed PostScript
file (for Release 2.1).
***> FOR RELEASE 2.2 documentation contact Guy Nason directly at the
address below.
ALSO available from the statlib archive (ftp: lib.stat.cmu.edu)
userid "statlib", your email address as password. The software
is in the "S" directory as "wavethresh".
CONTACT: gpn@maths.bath.ac.uk for further information
After Release 2.1 I received many questions along the lines of "what is S?".
The following information is culled from the S frequently asked questions
list and from the s-news digest.
WHAT ARE S & SPlus?
From the Frequently asked questions (FAQ) list:
4) What is S? What can S be used for?
S is a very high level language and an environment for data
analysis and graphics. S was written by Richard A. Becker,
John M. Chambers, and Allan R. Wilks of AT&T Bell Laboratories
Statistics Research Department. More recently, other Bell Labs
researchers have made major contributions to a new modeling
capability in S.
The S language is the form in which S users express their
computations. The environment provides facilities for data
management, support for many graphics devices, etc.
S is useful for computation in a wide range of applications.
It's a very general tool, so that applications are not res-
tricted to any particular subject area. One way to think of it
is to imagine the wide range of applications that can be han-
dled by a spreadsheet program - but think of an even broader
range of applications because S is much more flexible for com-
plex computations. As examples, S has been used for computing
in business, finance, experimental science, etc.
The authors of S prefer that you not call S a statistics package.
Most of the people who use S have no attachment to statistics,
and most of the S applications involve basic quantitative
computations and graphics. ``Package'' really doesn't apply well
to S, either. The word ``package'' often connotes a collection
of unrelated tools put together under one name; this is unlike S,
where all functions are tightly integrated and controlled by the
S language.
6) What is S-PLUS? What does it have that S doesn't?
S-PLUS is a cleverly-named version of S sold by Statisti-
cal Sciences, Inc. It contains various extensions to S added
by StatSci, is supported, and has a large installed base. It
tends to track the latest AT&T release, but it is not ``more
recent'' than S itself. StatSci was founded by Douglas Martin.
One can use S-PLUS to do all that one does in S.
The major areas in which S-PLUS extends S are time-series, survival
analysis, `modern regression' (including LMS regression and
projection pursuit regression), classical statistical tests,
graphical device drivers and dynamic loading.
From the s-news digest (8 Jun 1993; digest107):
Information about the S Language Software and S-PLUS can be obtained
from StatSci sales, 1700 Westlake Avenue North, Suite 500, Seattle, Washington
98109, by telephoning 1-800-569-0123 (North America), or 1-206-283-8802;
FAXING 1-206-283-8691; or by using Internet Email at mktg@statsci.com.
StatSci also offers a free instructional video explaining advanced, modern
data analysis using S-PLUS Software.
From: Cormac Herley (cormac@gothic.research.att.com)
Subject: Phd Thesis available
Author: Cormac Herley
Advisor: Martin Vetterli
Title: Wavelets and Filter Banks
Institution: Columbia University
Copies can be obtained via anonymous ftp from: ftp.ctr.columbia.edu
directory: CTR-Research/advent/public/papers/PhD-theses/Herley
Abstract:
Recent work has made it clear that the design of multirate filter
banks for Signal Processing, and of wavelet bases for the analysis of
functions address essentially two versions of the same problem: construction
of structured bases for the linear expansion of signals. In the filter bank
case the signals are elements of some sequence space, while in the wavelet
case they are from some function space, but the objectives, and designs
in both cases are very similar.
The work of this thesis is to firmly establish the relation between these two
fields, to use filter bank designs to derive novel bases of wavelets, and to
use the structure used by the wavelet approach to better understand
filter banks.
Among the main results is a complete study of finite impulse response
filter banks, and their relation to wavelets of bounded support. Examples
of new symmetric bases of bounded support wavelets are given.
A complete constructive characterization of orthogonal infinite
impulse response filter banks is given which leads to orthonormal
wavelet bases with exponential decay. Particular cases include orthonormal
wavelets bases generated by halfband Butterworth filters, orthogonal
symmetric filter banks and wavelets, and orthonormal bases of wavelets
for the spline function spaces based on realizable filter banks.
On the open question of changing between orthogonal filter banks we show
that the transition between finite impulse response filter banks
can be achieved using a Gram-Schmidt procedure, and that the disruption
affects only the region of the transition. This also gives a complete
constructive way of finding all possible orthogonal solutions of the
finite duration filter bank problem.
A number of novel applications of filter banks are given. It is shown that
multirate structures can be used to implement realizable projection
operators and that they can perform exact interpolation of certain
types of continuous-time functions. It is demonstrated that time-varying
filter banks can be used to generate orthogonal bases where the
energy localization of the basis functions are distributed in the
time-frequency plane in an essentially arbitrary fashion, which is
useful for signal compression applications.
<webmaster@wavelet.org>