[Home]
[Back Issues]
[Search]
[Vol 1]
[Vol 2]
[Vol 3]
[Vol 4]
[Vol 5]
The Wavelet Digest - Volume 2, Issue 1 (January 22, 1993)
Today's Editor: Wim Sweldens
Today's Topics:
1. Wavelet Softwares Availables
2. Technical Memorandum available: A Fast Discrete Periodic Wavelet Transform
3. Question concerning Numerical Recipes
4. Question concerning Pollen's parametrization of wavelets
5. Question concerning wavelets and computer graphics
6. Papers on wavelet de_noising available
7. Question concerning wavelet books
8. Looking for a Mathematica package that does wavelets
9. Question concerning the cascade algorithm
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.
Archive site: (for retrieval of 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: 2403
From: Stephane Mallat
Date: Tue, 22 Dec 92 12:56:39 -0500
Subject: Wavelet Softwares Availables
/****************************************************************/
/* Wave1 Software */
/* Authors: Emmanuel Bacry, Wen-Liang Hwang, */
/* Stephane Mallat and Sifen Zhong */
/* */
/* (c) Copyright 1992 New York University */
/* All rights reserved */
/****************************************************************/
/****************************************************************/
/* Wave2 Software */
/* Authors: Wen-Liang Hwang, Stephane Mallat, Sifen Zhong */
/* */
/* (c) Copyright 1992 New York University */
/* All rights reserved */
/****************************************************************/
Wave1 and Wave2 are two softwares written in C
to process signals with the wavelet transform.
These software run under Unix and X11 windows.
They provide shell environements that include
image displays, plotting and postscript facilities,
as well as general signal processing subroutines.
They can be particularly useful for researchers or engineers who
want to make experiments with the wavelet tranform.
The wavelet transform algorithms implemented in these softwares are
mainly based on two published papers:
[1] "Characterization of signals from multiscale edges" by Stephane Mallat
and Sifen Zhong,
IEEE Transactions on Pattern Analysis and Machine Intelligence,
Vol. 14, No. 7, p. 710-732, July 1992,
[2] "Singularity detection and processing with wavelets", by Stephane Mallat
and Wen Liang Hwang, IEEE Transactions on Information Theory,
Vol. 38, No. 2, p. 617-643, March 1992.
The Wave1 software processes one-dimensional signals whereas Wave2
processes images. Dyadic wavelet tranform decompositions and reconstruction
are implemented. Signal singularities and edges are detected from the
local maxima of the wavelet transform. We implemented the
subroutines that reconstruct signals from the local maxima of their wavelet
transform, with the algorithm described in [1]. One-dimensional signals
as well as images can thus be processed through the local
maxima of their wavelet transform (multiscale edges). Many subroutines
to process these local maxima are available. For images, applications to noise
removal and optical flow detection are implemented. An on-line
documentation is available.
A nonexclusive license to use this software and its documentation
for scholarly and research purposes only is hereby granted by
New York University. There is no fee to use this software for these
purposes. In using the software and documentation for scholarly and
research purposes you may copy or modify them but (a) you must include
the NYU copyright notice and the original authors' names on each copy
or modification you make of the software and of the supporting documentation;
and (b) you may not use, rewrite, or adapt the software or the documentation
(or any part of either) as the basis for any commercial software or hardware
product, without in each instance obtaining the prior written consent of
NYU or an appropriate license from NYU. You may not use this software
and its documentation (or any part of either) for any other purpose
without obtaining an appropriate license from NYU. To obtain any
license or consent from NYU, please contact: Patrick Franc, Office of
Industrial Liaison, New York University, 251 Mercer Street, New York,
NY 10012.
The source codes of Wave1 and Wave2 are available via anonymous ftp on the
machine cs.nyu.edu (IP number 128.122.140.24). After login with login name
"anonymous", do "cd pub/wave". The wave1 and wave2 softwares are
respectively in the compressed tarfiles "wave1.tar.Z" and "wave2.tar.Z".
These are unix-compressed tarfiles, so don't forget to put ftp under "binary"
mode before getting them. You must use the "uncompress" and "tar" unix
commands to restore the software.
Instructions for compilation are in the README files.
From: Neil Getz, University of California at Berkeley
Date: Tue, 22 Dec 92 11:20:14 PST
Subject: Technical Memorandum available
A Fast Discrete Periodic Wavelet Transform
Neil Getz
Department of Electrical Engineering and Computer Sciences
and
Electronics Research Laboratory
University of California
Berkeley, California 94720
email: getz@robotics.Berkeley.EDU
Abstract
The discrete wavelet transform (DWT) is extended to functions
on the discrete circle to create a fast and complete discrete
periodic wavelet transform (DPWT) for bounded periodic sequences.
This extension also solves the problem of non-invertibility that
arises in the application of the DWT to finite dimensional sequences
as well as provides the proper theoretical setting for previous
incomplete solutions to the invertibility problem. It is shown how and
proven that the same filter coefficients used with the DWT to create
orthonormal wavelets on compact support in the space of square summable
sequences over the integers may be incorporated through the DPWT to
create an orthonormal basis of discrete periodic wavelets. By exploiting
transform symmetry and periodicity, easily implementable and fast
synthesis and analysis algorithms are derived. Matlab functions for DPWT
experimentation are included.
Electronics Research Laboratory technical memo M92/138.
Requests for a copy of this memo may be sent to the author
via email to getz@robotics.Berkeley.EDU.
From: Doug Lamb, University of Virginia
Date: Tue, 22 Dec 1992 18:58:15 -0500
Subject: Question concerning Numerical Recipes
Does anyone know the planned publication date for the 2nd
edition of Numerical Recipes in C etc. If it's too far distant,
I'll just get the FORTRAN code and translate it.
Doug Lamb
University of Virginia
dtl8v@Virginia.EDU
From: Davids Stanhill, Department of electrical engineering, Technion, Israel
Date: Thu, 24 Dec 92 14:11:22 +0200
Subject: question concerning Pollen's parametrization of wavelets
Dear Wavelet'ers,
Does any one know of papers written on
(or using) Pollen's parametrization of wavelets ?
If so, I would appreciate getting the reference, if the
paper has been published, or the preprint
(hard copy or PS file) if it has not.
Thank you very much.
David Stanhill
Department of electrical engineering,
Technion,
Haifa 32000
ISRAEL
e-mail: davids@techunix.technion.ac.il
Date: Wed, 6 Jan 1993 11:52:31 -0500
From: sassoj@rpi.edu
Subject: Question concerning wavelets and computer graphics
Does anyone know if there is any research and/or applications of wavelets
to computer graphics (i.e. 3-D modeling, shading, and other computer
graphics related areas)? If so, could someone provide me with references.
-- John
From: David Donoho, Department of Statistics, Stanford University
Date: Sat, 9 Jan 93 19:37:04 -0800
Subject: 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 Besov-type 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 spatially-adaptive estimation--- {\it
selective wavelet reconstruction}. We show that %variable-bandwidth
kernels, variable-knot spline fits and piecewise-polynomial 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
variable-knot 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 $\theta$ from data $N_n( \theta ,
\sigma^2 I )$ with $l_q$ norm loss, $q \geq 1$, when $\theta$ is known
to lie in an $n$-dimensional $l_p$ ball, $p \in (0, \infty )$. For
large $n$, the ratio of minimax \sl linear \rm 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 non-linear co-ordinatewise threshold rules are
asymptotically minimax at small signal-to-noise 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 Wavelet-Vaguelette
Decomposition"
TR 403 July 1992, Submitted for publication
nslip.dvi
We describe the Wavelet-Vaguelette 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 Abel-type transforms, certain
convolution transforms, and the Radon Transform.
We propose to solve ill-posed 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)
\begin{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 re-interpret
the empirical wavelet transform, i.e. the common practice
of applying pyramid filters to samples of a function.
\end{abstract}
{\bf Key Words and Phrases.} Interpolating
Wavelet Transform. Interpolating Spline Wavelets.
Interpolating Deslauriers-Dubuc 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)
\begin{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}
{\bf 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
"De-Noising via Soft Thresholding"
TR 409 November 1992, Submitted for publication
denoiserelease3.tex (LATEX)
\begin{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 higher-dimensional samples
and area samples.
\end{abstract}
{\bf Key Words and Phrases.} Empirical Wavelet Transform. Minimax
Estimation. Adaptive Estimation. Optimal Recovery.
From: Lode Vermeersch, Rijksuniversiteit Gent, Belgium
Date: Mon, 18 Jan 93 12:15:54 GMT
Subject: question concerning wavelet books
Hello fellow waves,
Is there someone, who can give me some indication on the contents of the
following books ?
- "Ten Lectures on Wavelets" by I. Daubechies.
- "An Introduction to Wavelets" by C. Chui.
- "Wavelets : An elementary treatment of theory and applications" by
T. Koornwinder, editor.
- "Wavelet Theory and its Applications" by R. Young.
To which audience are these books addressed ? Is it also possible to
give me some positive and negative critiques on the different books ?
Thanks in advance for possible reactions,
Lode Vermeersch.
University of Gent (Belgium)
lode@fland.rug.ac.be
From: Gideon Yuval, Microsoft
Date: Mon, 18 Jan 93 17:31:36 PST
Subject: looking for a Mathematica package that does wavelets
Is there a Mathematica package that does wavelets?
Thanks
Gideon Yuval (gideony@microsoft.com)
From: Norman C. Corbett, University of Waterloo, Canada
Date: Wed, 20 Jan 1993 10:27:57 -0500
Subject: question concerning cascade algorithm
Dear Digest Readers,
I am trying to implement the "Cascade Algorith", as described in
Daubechies' "Ten Lectures on Wavelets". This algorithm is suppose
to allow for the computation of the inner-products
C^j_k=<\phi(x), 2^{j/2} \phi(2^j x-k) >
C^j_k=\sum_l h_{k-2l} C^{j-1}_l,
where {h_k} is the associated two-scale sequence. Since \phi is in
L^1 and is unimodular, we can use the numbers 2^{j/2} C^j_k to
approximate the value of \phi at the dyadic rationals k/2^j
(for j large enough). However, when I use my program to compute
the C^j_k, my results to not agree with those of Daubechies. Has
anyone implemented this algorithm? I would appreciate any advice
(pseudo-code would be nice). Thanks
Norm Corbett
Dept. of Applied Mathematics
University of Waterloo
nccorbett@violet.waterloo.edu
<webmaster@wavelet.org>