[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>