The Discrete Wavelet Transform in S

Abstract

The theory of wavelets has recently undergone a period of rapid development. We introduce a software package called wavethresh that works within the statistical language S to perform one- and two-dimensional discrete wavelet transforms. The transforms and their inverses can be computed using any particular wavelet selected from a range of different families of wavelets. Pictures can be drawn of any of the one- or two-dimensional wavelets available in the package. The wavelet coefficients can be presented in a variety of ways to aid in the interpretation of data. The package's wavelet transform “engine” is written in C for speed and the object-oriented functionality of S makes wavethresh easy to use. We provide a tutorial introduction to wavelets and the wavethresh software. We also discuss how the software may be used to carry out nonlinear regression and image compression. In particular, thresholding of wavelet coefficients is a method for attempting to extract signal from noise and wavethresh includes functions to perform thresholding according to methods in the literature.     

Basic properties of wavelets

A wavelet multiplier is a function whose product with the Fourier transform of a wavelet is the Fourier transform of a wavelet. We characterize the wavelet multipliers, as well as the scaling function multipliers and low pass filter multipliers. We then prove that if the set of all wavelet multipliers acts on the set of all MRA wavelets, the orbits are the sets of all MRA wavelets whose Fourier transforms have equal absolute values, and these are also equal to the sets, of all MRA wavelets with the corresponding scaling functions having the same absolute values of their Fourier transforms. As an application of these techniques, we prove that the set of MRA wavelets is arcwise connected in L²(R). Dedicated to Eugene Fabes The Wutam Consortium     

A two-dimensional wavelet-packet transform for matrix compression of integral equations with highly oscillatory kernel

We examine the use of wavelet packets for the fast solution of integral equations with a highly oscillatory kernel. The redundancy of the wavelet packet transform allows the selection of a basis tailored to the problem at hand. It is shown that a well chosen wavelet packet basis is better suited to compress the discretized system than wavelets. The complexity of the matrix–vector product in an iterative solution method is then substantially reduced. A two-dimensional wavelet packet transform is derived and compared with a number of one-dimensional transforms that were presented earlier in literature. By means of some numerical experiments we illustrate the improved efficiency of the two-dimensional approach.     

Gibbs Phenomenon in Wavelet Analysis

We prove Dirichlet-type pointwise convergence theorems for the wavelet transforms and series of discontinuous functions and we examine the Gibbs ripples close to the jump location. Examples are given of wavelets without ripples, and an example (the Mexican hat) shows that the Gibbs ripple in continuous wavelet analysis can be 3.54% instead of 8.9% of the Fourier case. For the discrete case we show that there exist two Meyer type wavelets the first one has maximum ripple 3.58% and the second 9.8%. Moreover we describe several examples and methods for estimating Gibbs ripples both in continuous and discrete cases. Finally we discuss how a wavelet transform generates a summability method for the Fourier case.     

A certain family of fractional wavelet transformations

In the present paper, a fractional wavelet transform of real order α is introduced, and various useful properties and results are derived for it. These include (for example) Perseval's formula and inversion formula for the fractional wavelet transform. Multiresolution analysis and orthonormal fractional wavelets associated with the fractional wavelet transform are studied systematically. Fractional Fourier transforms of the Mexican hat wavelet for different values of the order α are compared with the classical Fourier transform graphically, and various remarkable observations are presented. A comparative study of the various results, which we have presented in this paper, is also represented graphically.     

Construction of Biorthogonal Discrete Wavelet Transforms Using Interpolatory Splines

We present a new family of biorthogonal wavelet and wavelet packet transforms for discrete periodic signals and a related library of biorthogonal periodic symmetric waveforms. The construction is based on the superconvergence property of the interpolatory polynomial splines of even degrees. The construction of the transforms is performed in a “lifting” manner that allows more efficient implementation and provides tools for custom design of the filters and wavelets. As is common in lifting schemes, the computations can be carried out “in place” and the inverse transform is performed in a reverse order. The difference with the conventional lifting scheme is that all the transforms are implemented in the frequency domain with the use of the fast Fourier transform. Our algorithm allows a stable construction of filters with many vanishing moments. The computational complexity of the algorithm is comparable with the complexity of the standard wavelet transform. Our scheme is based on interpolation and, as such, it involves only samples of signals and it does not require any use of quadrature formulas. In addition, these filters yield perfect frequency resolution.     

The Calderón reproducing formula, windowed X-ray transforms, and radon transforms in LP-spaces

The generalized Calderón reproducing formula involving “wavelet measure” is established for functions f ∈ L^p(ℝⁿ). The special choice of the wavelet measure in the reproducing formula gives rise to the continuous decomposition of f into wavelets, and enables one to obtain inversion formulae for generalized windowed X-ray transforms, the Radon transform, and k-plane transforms. The admissibility conditions for the wavelet measure μ are presented in terms of μ itself and in terms of the Fourier transform of μ. Acknowledgements and Notes. Partially sponsored by the Edmund Landau Center for research in Mathematical Analysis, supported by the Minerva Foundation (Germany).     

分数阶尺度函数的分解与重构算法

引入分数阶多分辨分析与分数阶尺度函数的概念.运用时频分析方法与分数阶小波变换,研究了分数阶正交小波的构造方法,得到分数阶正交小波存在的充要条件.给出分数阶尺度函数与小波的分解与重构算法,算法比经典的尺度函数与小波的分解与重构算法更具有一般性.     

Orthogonal and Nonorthogonal Multiresolution Analysis, Scale Discrete and Exact Fully Discrete Wavelet Transform on the Sphere

Based on a new definition of dilation a scale discrete version of spherical multiresolution is described, starting from a scale discrete wavelet transform on the sphere. Depending on the type of application, different families of wavelets are chosen. In particular, spherical Shannon wavelets are constructed that form an orthogonal multiresolution analysis. Finally fully discrete wavelet approximation is discussed in the case of band-limited wavelets. June 18, 1996. Date revised: January 14, 1997.     

Homogeneous Approximation Property for Multivariate Continuous Wavelet Transforms

The homogeneous approximation property (HAP) for the continuous wavelet transform is useful in practice because it means that the measure of the building area involved in a reconstruction of a function up to some error is essentially invariant under timescale shifts. For the univariate case, it was shown that the pointwise HAP holds if and only if the Fourier transforms of both wavelets and the function to be reconstructed are compactly supported on ??{0}. In this paper, we study the HAP for multivariate wavelet transforms. We show that similar results hold for this case. However, the above condition is only sufficient but not necessary if the dimension of the variable is greater than 1, which is different from the univariate case. We also get a convergence result on the inverse of wavelet transforms, which improves similar results by Daubechies and Holschneider and Tchamitchain.     

Polar Wavelet Transforms and Localization Operators

The notion of a polar wavelet transform is introduced. The underlying non-unimodular Lie group, the associated square-integrable representations and admissible wavelets are studied. The resolution of the identity formula for the polar wavelet transform is then formulated and proved. Localization operators corresponding to the polar wavelet transforms are then defined. It is proved that under suitable conditions on the symbols, the localization operators are, in descending order of complexity, paracommutators, paraproducts and Fourier multipliers. This research was supported by the Natural Sciences and Engineering Research Council of Canada.     

Wavelet Frames on Groups and Hypergroups via Discretization of Calderón Formulas

Continuous wavelets are often studied in the general framework of representation theory of square-integrable representations, or by using convolution relations and Fourier transforms. We consider the well-known problem whether these continuous wavelets can be discretized to yield wavelet frames. In this paper we use Calderón-Zygmund singular integral operators and atomic decompositions on spaces of homogeneous type, endowed with families of general translations and dilations, to attack this problem, and obtain strong convergence results for wavelets expansions in a variety of classical functional spaces and smooth molecule spaces. This approach is powerful enough to yield, in a uniform way, for example, frames of smooth wavelets for matrix dilations in ⁿ, for an affine extension of the Heisenberg group, and on many commutative hypergroups.     

Wavelet Frames on Groups and Hypergroups via Discretization of Calderón Formulas

Continuous wavelets are often studied in the general framework of representation theory of square-integrable representations, or by using convolution relations and Fourier transforms. We consider the well-known problem whether these continuous wavelets can be discretized to yield wavelet frames. In this paper we use Calderón-Zygmund singular integral operators and atomic decompositions on spaces of homogeneous type, endowed with families of general translations and dilations, to attack this problem, and obtain strong convergence results for wavelets expansions in a variety of classical functional spaces and smooth molecule spaces. This approach is powerful enough to yield, in a uniform way, for example, frames of smooth wavelets for matrix dilations in ⁿ, for an affine extension of the Heisenberg group, and on many commutative hypergroups.     

Biorthogonal bases of compactly supported wavelets

Orthonormal bases of compactly supported wavelet bases correspond to subband coding schemes with exact reconstruction in which the analysis and synthesis filters coincide. We show here that under fairly general conditions, exact reconstruction schemes with synthesis filters different from the analysis filters give rise to two dual Riesz bases of compactly supported wavelets. We give necessary and sufficient conditions for biorthogonality of the corresponding scaling functions, and we present a sufficient conditions for the decay of their Fourier transforms. We study the regularity of these biorthogonal bases. We provide several families of examples, all symmetric (corresponding to “linear phase” filters). In particular we can construct symmetric biorthogonal wavelet bases with arbitraily high preassigned regularity; we also show how to construct symmetric biorthogonal wavelet bases “close” to a (nonsymmetric) orthonormal basis.     

Some remarks on “On the windowed Fourier transform and wavelet transform of almost periodic functions,” by J.R. Partington and B. Ünalmı

J.R. Partington and B. Ünalmı consider in their 2001 paper [J.R. Partington, B. Ünalmı , Appl. Comput. Harmon. Anal. 10 (1) (2001) 45–60] the windowed Fourier transform and wavelet transform as tools for analyzing almost periodic signals. They establish Parseval-type identities and consider discretized versions of these transforms in order to construct generalized frame decompositions. We have found a gap in the construction of generalized frames in the windowed Fourier transform case; we comment on this gap and give an alternative proof. As for the wavelet transform case, in [J.R. Partington, B. Ünalmı , Appl. Comput. Harmon. Anal. 10 (1) (2001) 45–60] the generalized frame decomposition is done only for the simplest wavelet, the Haar wavelet; we show how to construct generalized frame decompositions for a wide family of wavelets.     

A characterization of wavelets on general lattices

In the context of a general lattice Γ in Rⁿ and a strictly expanding map M which preserves the lattice, we characterize all the wavelet families. This result generalizes the characterization of Frazier, Garrigós, Wang, and Weis about the wavelet families with Γ = Zⁿ and M = 21. In the second part of the paper, we characterize all the MSF wavelets. Moreover, we give a constructive method for the support of the Fourier transform of an MSF wavelet and apply this method by giving examples with particular attention to the quincunx lattice.     

A class of solutions for the inverse diffusion problem

The close relation between Hermitian wavelets transforms and the diffusion equation is used to derive a one-parameter family of distributed sources as solutions to the inverse diffusion problem in R^N × R_. The class of solutions is interpreted in terms of energetically dominant events in the wavelet representation, where the scale of the event is proportional to its age. The construction procedure is a straightforward extension of the inverse wavelet transform formula. Simple examples illustrate the method.     

Detection of Singularities by Discrete Multiscale Directional Representations

One of the most remarkable properties of the continuous curvelet and shearlet transforms is their sensitivity to the directional regularity of functions and distributions. As a consequence of this property, these transforms can be used to characterize the geometry of edge singularities of functions and distributions by their asymptotic decay at fine scales. This ability is a major extension of the conventional continuous wavelet transform which can only describe pointwise regularity properties. However, while in the case of wavelets it is relatively easy to relate the asymptotic properties of the continuous transform to properties of discrete wavelet coefficients, this problem is surprisingly challenging in the case of discrete curvelets and shearlets where one wants to handle also the geometry of the singularity. No result for the discrete case was known so far. In this paper, we derive non-asymptotic estimates showing that discrete shearlet coefficients can detect, in a precise sense, the location and orientation of curvilinear edges. We discuss connections and implications of this result to sparse approximations and other applications.     

The high frequency behaviour of continuous wavelet transforms

The high frequency behaviour of continuous wavelet transforms is characterized by the number of vanishing moments of the corresponding basic wavelets. As a consequence we give satisfying answers to the following questions of theoretical as well as practical interest:

What are the differences or similarities between transforms to different wavelets?

Why do wavelet transforms react so sensitively to abrupt signal changes ?     

Numerical stability of biorthogonal wavelet transforms

For orthogonal wavelets, the discrete wavelet and wave packet transforms and their inverses are orthogonal operators with perfect numerical stability. For biorthogonal wavelets, numerical instabilities can occur. We derive bounds for the 2-norm and average 2-norm of these transforms, including efficient numerical estimates if the numberL of decomposition levels is small, as well as growth estimates forL . These estimates allow easy determination of numerical stability directly from the wavelet coefficients. Examples show that many biorthogonal wavelets are in fact numerically well behaved.