Unique reconstruction of band-limited signals by a Mallat-Zhong wavelet transform algorithm

We show that uniqueness and existence for signal reconstruction from multiscale edges in the Mallat and Zhong algorithm become possible if we restrict our signals to Paley-Wiener space, band-limit our wavelets, and irregularly sample at the wavelet transform (absolute) maxima—the edges—while possibly including (enough) extra points at each level. We do this in a setting that closely resembles the numerical analysis setting of Mallat and Zhong and that seems to capture something of the essence of their (practical) reconstruction method. Our work builds on a uniqueness result for reconstructing an L² signal from irregular sampling of its wavelet transform of Grochenig and the related work of Benedetto, Heller, Mallat, and Zhong. We show that the rate of convergence for this reconstruction algorithm is geometric and computable in advance. Finally, we consider the effect on the rate of convergence of not sampling enough local maxima.     

Unique Reconstruction of Band-limited Signals by a Mallat-Zhong Wavelet Transform Algorithm

We show that uniqueness and existence for signal reconstruction from multiscale edges in the Mallat and Zhong algorithm become possible if we restrict our signals to Paley-Wiener space, band-limit our wavelets, and irregularly sample at the wavelet transform (absolute) maxima—the edges—while possibly including (enough) extra points at each level. We do this in a setting that closely resembles the numerical analysis setting of Mallat and Zhong and that seems to capture something of the essence of their (practical) reconstruction method. Our work builds on a uniqueness result for reconstructing an L² signal from irregular sampling of its wavelet transform of Gröchenig and the related work of Benedetto, Heller, Mallat, and Zhong. We show that the rate of convergence for this reconstruction algorithm is geometric and computable in advance. Finally, we consider the effect on the rate of convergence of not sampling enough local maxima.     

Traces in Complex Hyperbolic Triangle Groups

We present several formulas for the traces of elements in complex hyperbolic triangle groups generated by complex reflections. The space of such groups of fixed signature is of real dimension one. We parameterise this space by a real invariant α of triangles in the complex hyperbolic plane. The main result of the paper is a formula, which expresses the trace of an element of the group as a Laurent polynomial in e^{i α} with coefficients independent of α and computable using a certain combinatorial winding number. We also give a recursion formula for these Laurent polynomials and generalise the trace formulas for the groups generated by complex μ-reflections. We apply these formulas to prove some discreteness and some non-discreteness results for complex hyperbolic triangle groups.Research partially supported by NSF grant DMS-0072607 and by SFB 611 of the DFG.     

The butterfly decomposition of plane trees

We introduce the notion of doubly rooted plane trees and give a decomposition of these trees, called the butterfly decomposition, which turns out to have many applications. From the butterfly decomposition we obtain a one-to-one correspondence between doubly rooted plane trees and free Dyck paths, which implies a simple derivation of a relation between the Catalan numbers and the central binomial coefficients. We also establish a one-to-one correspondence between leaf-colored doubly rooted plane trees and free Schröder paths. The classical Chung-Feller theorem as well as some generalizations and variations follow quickly from the butterfly decomposition. We next obtain two involutions on free Dyck paths and free Schröder paths, leading to parity results and combinatorial identities. We also use the butterfly decomposition to give a combinatorial treatment of Klazar's generating function for the number of chains in plane trees. Finally we study the total size of chains in plane trees with n edges and show that the average size of such chains tends asymptotically to (n+9)/6.     

Restricted Nonlinear Approximation

We introduce a new form of nonlinear approximation called restricted approximation . It is a generalization of n -term wavelet approximation in which a weight function is used to control the terms in the wavelet expansion of the approximant. This form of approximation occurs in statistical estimation and in the characterization of interpolation spaces for certain pairs of L _p and Besov spaces. We characterize, both in terms of their wavelet coefficients and also in terms of their smoothness, the functions which are approximated with a specified rate by restricted approximation. We also show the relation of this form of approximation with certain types of thresholding of wavelet coefficients. March 31, 1998. Date accepted: January 28, 1999.     

A Consistent and Stable Approach to Generalized Sampling

We consider the problem of generalized sampling, in which one seeks to obtain reconstructions in arbitrary finite dimensional spaces from a finite number of samples taken with respect to an arbitrary orthonormal basis. Typical approaches to this problem consider solutions obtained via the consistent reconstruction technique or as solutions of an overcomplete linear systems. However, the consistent reconstruction technique is known to be non-convergent and ill-conditioned in important cases, such as the recovery of wavelet coefficients from Fourier samples, and whilst the latter approach presents solutions which are convergent and well-conditioned when the system is sufficiently overcomplete, the solution becomes inconsistent with the original measurements. In this paper, we consider generalized sampling via a non-linear minimization problem and prove that the minimizers present solutions which are convergent, stable and consistent with the original measurements. We also provide analysis in the case of recovering wavelets coefficients from Fourier samples. We show that for compactly supported wavelets of sufficient smoothness, there is a linear relationship between the number of wavelet coefficients which can be accurately recovered and the number of Fourier samples available.     

Double node neighborhoods and families of simply connected -manifolds with

We introduce a new technique that is used to show that the complex projective plane blown up at 6, 7, or 8 points has infinitely many distinct smooth structures. None of these smooth structures admits smoothly embedded spheres with self-intersection , i.e., they are minimal. In addition, none of these smooth structures admits an underlying symplectic structure. Shortly after the appearance of a preliminary version of this article, Park, Stipsicz, and Szabo used the techniques described herein to show that the complex projective plane blown up at 5 points has infinitely many distinct smooth structures. In the final section of this paper we give a construction of such a family of examples.

     

Nonlinear functionals of wavelet expansions – adaptive reconstruction and fast evaluation

Summary. This paper is concerned with the efficient evaluation of nonlinear expressions of wavelet expansions obtained through an adaptive process. In particular, evaluation covers here the computation of inner products of such expressions with wavelets which arise, for instance, in the context of Galerkin or Petrov Galerkin schemes for the solution of differential equations. The central objective is to develop schemes that facilitate such evaluations at a computational expense exceeding the complexity of the given expansion, i.e., the number of nonzero wavelet coefficients, as little as possible. The following issues are addressed. First, motivated by previous treatments of the subject, we discuss the type of regularity assumptions that are appropriate in this context and explain the relevance of Besov norms. The principal strategy is to relate the computation of inner products of wavelets with compositions to approximations of compositions in terms of possibly few dual wavelets. The analysis of these approximations finally leads to a concrete evaluation scheme which is shown to be in a certain sense asymptotically optimal. We conclude with a simple numerical example. Received June 25, 1998 / Revised version received June 5, 1999 / Published online April 20, 2000 –? Springer-Verlag 2000     

An algebraic approach to discrete dilations. Application to discrete wavelet transforms

We investigate the connections between continuous and discrete wavelet transforms on the basis of algebraic arguments. The discrete approach is formulated abstractly in terms of the action of a semidirect product A×Γ on ℓ²(Γ), with Γ a lattice and A an abelian semigroup acting of Γ. We show that several such actions may be considered, and investigate those which may be written as deformations of the canonical one. The corresponding deformed dilations (the pseudodilations) turn out to be characterized by compatibility relations of a cohomological nature. The connection with multiresolution wavelet analysis is based on families of pseudodilations of a different type.     

An analogue of continued fractions in number theory for Nevanlinna theory

We show an analogue of continued fractions in approximation to irrational numbers by rationals for Nevanlinna theory. The analogue is a sequence of points in the complex plane which approaches a given finite set of points and at a given rate in the sense of Nevanlinna theory.

     

On Isolation of Real and Nearly Real Zeros of a Univariate Polynomial and Its Splitting into Factors

We show two simple algorithms for isolation of the real and nearly real zeros of a univariate polynomial, as well as of those zeros that lie on or near a fixed circle on the complex plane. We also simplify slightly approximation of complex zeros of a polynomial with real coefficients.     

Angle orders

A finite poset is an angle order if its points can be mapped into angular regions in the plane so thatx precedesy in the poset precisely when the region forx is properly included in the region fory. We show that all posets of dimension four or less are angle orders, all interval orders are angle orders, and that some angle orders must have an angular region less than 180° (or more than 180°). The latter result is used to prove that there are posets that are not angle orders.The smallest verified poset that is not an angle order has 198 points. We suspect that the minimum is around 30 points. Other open problems are noted, including whether there are dimension-5 posets that are not angle orders.Research supported in part by the National Science Foundation, grant number DMS-8401281.     

Singularity spectrum of multifractal functions involving oscillating singularities

We give general mathematical results concerning oscillating singularities and we study examples of functions composed only of oscillating singularities. These functions are defined by explicit coefficients on an orthonormal wavelet basis. We compute their Hölder regularity and oscillation at every point and we deduce their spectrum of oscillating singularities.     

Automatic Smoothing With Wavelets for a Wide Class of Distributions

Wavelet-based denoising techniques are well suited to estimate spatially inhomogeneous signals. Waveshrink (Donoho and Johnstone) assumes independent Gaussian errors and equispaced sampling of the signal. Various articles have relaxed some of these assumptions, but a systematic generalization to distributions such as Poisson, binomial, or Bernoulli is missing. We consider a unifying l₁-penalized likelihood approach to regularize the maximum likelihood estimation by adding an l₁ penalty of the wavelet coefficients. Our approach works for all types of wavelets and for a range of noise distributions. We develop both an algorithm to solve the estimation problem and rules to select the smoothing parameter automatically. In particular, using results from Poisson processes, we give an explicit formula for the universal smoothing parameter to denoise Poisson measurements. Simulations show that the procedure is an improvement over other methods. An astronomy example is given.     

A summability method for the arithmetic Fourier transform

The Arithmetic Fourier Transform (AFT) is an algorithm for the computation of Fourier coefficients, which is suitable for parallel processing and in which there are no multiplications by complex exponentials. This is accomplished by the use of the Möbius function and Möbius inversion. However, the algorithm does require the evaluation of the function at an array of irregularly spaced points. In the case that the function has been sampled at regularly spaced points, interpolation is used at the intermediate points of the array. Generally theAFT is most effective when used to calculate the Fourier cosine coefficients of an even function.In this paper a summability method is used to derive a modification of theAFT algorithm. The proof of the modification is quite independent of theAFT itself and involves a summation by primes. One advantage of the new algorithm is that with a suitable sampling scheme low order Fourier coefficients may be calculated without interpolation.     

Nonlinear wavelet thresholding: A recursive method to determine the optimal denoising threshold

Nonlinear thresholding of wavelet coefficients is an efficient method for denoising signals with isolated singularities. The quasi-optimal value of the threshold depends on the sample size and on the variance of the noise, which is in many situations unknown. We present a recursive algorithm to estimate the variance of the noise, prove its convergence and investigate its mathematical properties. We show that the limit threshold depends on the probability density function (PDF) of the noisy signal and that it is equal to the theoretical threshold provided that the wavelet representation of the signal is sufficiently sparse. Numerical tests confirm these results and show the competitiveness of the algorithm compared to the median absolute deviation method (MAD) in terms of computational cost for strongly noised signals.     

Asymptotics of determinants of 4-th order operators at zero

We consider fourth order ordinary differential operators on the half-line and on the line, where the perturbation has compactly supported coefficients. The Fredholm determinant for this operator is an analytic function in the whole complex plane without zero. We describe the determinant at zero. We show that in the generic case it has a pole of order 4 in the case of the line and of order 1 in the case of the half-line.     

Localisation of directional scale-discretised wavelets on the sphere

Scale-discretised wavelets yield a directional wavelet framework on the sphere where a signal can be probed not only in scale and position but also in orientation. Furthermore, a signal can be synthesised from its wavelet coefficients exactly, in theory and practice (to machine precision). Scale-discretised wavelets are closely related to spherical needlets (both were developed independently at about the same time) but relax the axisymmetric property of needlets so that directional signal content can be probed. Needlets have been shown to satisfy important quasi-exponential localisation and asymptotic uncorrelation properties. We show that these properties also hold for directional scale-discretised wavelets on the sphere and derive similar localisation and uncorrelation bounds in both the scalar and spin settings. Scale-discretised wavelets can thus be considered as directional needlets.     

Theory, implementation and applications of nonstationary Gabor frames

Signal analysis with classical Gabor frames leads to a fixed time-frequency resolution over the whole time-frequency plane. To overcome the limitations imposed by this rigidity, we propose an extension of Gabor theory that leads to the construction of frames with time-frequency resolution changing over time or frequency. We describe the construction of the resulting nonstationary Gabor frames and give the explicit formula for the canonical dual frame for a particular case, the painless case. We show that wavelet transforms, constant-Q transforms and more general filter banks may be modeled in the framework of nonstationary Gabor frames. Further, we present the results in the finite-dimensional case, which provides a method for implementing the above-mentioned transforms with perfect reconstruction. Finally, we elaborate on two applications of nonstationary Gabor frames in audio signal processing, namely a method for automatic adaptation to transients and an algorithm for an invertible constant-Q transform.     

Quilted Gabor frames – A new concept for adaptive time-frequency representation

Certain signal classes such as audio signals call for signal representations with the ability to adapt to the signalʼs properties. In this article we introduce the new concept of quilted frames, which aim at adaptivity in time-frequency representations. As opposed to Gabor or wavelet frames, this new class of frames allows for the adaptation of the signal analysis to the local requirements of signals under consideration. Quilted frames are constructed directly in the time-frequency domain in a signal-adaptive manner. Validity of the frame property guarantees the possibility to reconstruct the original signal. The frame property is shown for specific situations and the Bessel property is proved for the general setting. Strategies for reconstruction from coefficients obtained with quilted Gabor frames and numerical simulations are provided as well.