Statistical Signal and Image Modeling and Approximation using Wavelets ^{1}

Richard G. Baraniuk

The wavelet domain provides a natural setting for processing real-world signals and images, especially those rich in singularities (edges, ridges, textures, and other transients). Since wavelets form a basis, they can reproduce arbitrary functions, from highly structured real-world signals and images to completely unstructured noise. In linguistic terms, the wavelet vocabulary can be too expressive. To perform useful modeling of real-world signals and images, we must narrow this vocabulary’s scope by imposing a set of constraints — a grammar — that captures the salient structures of singularities. While much research has concentrated on developing new wavelet vocabularies, there remain many challenges in grammatical modeling.

Signal and image models play a central rôle in approximation theory. For instance, it is natural to model a signal as a member of a Besov or Sobolev smoothness space. In this case, the wavelet coefficients of a “grammatical signal” must decay at a certain rate; slower decay rates are ungrammatical. Besov models form the foundation for a number of sophisticated signal and image processing algorithms, from wavelet denoising to tree-structured compression.

Clearly, the more realistic and accurate the model or grammar, the more powerful the processing derived from it. As an alternative to deterministic smoothness space models, we have turned to wavelet-domain statistical models. Here, we interpret the signal at hand as a realization from a distribution or family of random signals and attempt to characterize the joint probability density function (pdf) f(w) of its wavelet transform w.

Viewed statistically, the wavelet transforms of a large class of real-world signals and images share two common features: (1) non-Gaussian marginal statistics (due to the two populations of wavelet coefficients: small coefficients from smooth regions and large coefficients from singularity regions) and (2) strong local correlations (due to the persistence of large and small values along the branches of the wavelet tree). We have developed a number of statistical models that accurately, realistically, and efficiently capture these structures. Here we will focus on wavelet-domain hidden Markov trees.

1Joint work with Hyeokho Choi, Matthew Crouse, Robert Nowak, and Justin Romberg.

Supported by NSF grants MIP–9457438 and CCR–9973188, ONR grant N00014–99–1– 0813, and DARPA/AFOSR grant F49620–97–1–0513.

Statistical models complement deterministic models, but also have some distinct advantages: (1) Statistical models lead immediately to Bayesian inference algorithms for solving problems best posed statistically, such as estimation, detection, classification, segmentation, and synthesis. (2) Statistical models yield new insights into their deterministics counterparts and lead directly to their generalization. For example, we have shown that the (deterministic) Besov norm of a signal equals the likelihood of that signal under an independent, generalized Gaussian statistical model for the wavelet coefficients. Thus, using a statistical, likelihood approach, we can generalize the notions of Besov norms and spaces and attempt to overcome their known shortcomings (Besov norms are invariant under arbitrary sign changes and permutations within scale of the wavelet coefficients). Our goal is a Besovinspired “statistical smoothness” measure for natural images.

Our ongoing results indicate that grammar-based processing can lead to significant performance gains — analogous to those brought by zero-trees to image compression — in a number of signal and image processing problems.

Email: richb@rice.edu. For papers, see: www.dsp.rice.edu

Department of Electrical and Computer Engineering Rice University 6100 Main Street Houston, TX 77005–1892

Nonlinear Functionals of Wavelet Expansions

Arne Barinka

We are concerned with the efficient evaluation of nonlinear expressions of wavelet expansions obtained in an adaptive process. The principle strategy is to construct a suitable approximation of this composition in terms of the dual wavelet system. Especially, we are interested in the computation of inner products involving such expressions, which arise e.g., in adaptive Galerkin or Petrov-Galerkin schemes.

On direct solvers, multigrid and numerical homogenization

Beylkin Gregory

We will review connections between the direct solvers which use multiresolution LU decomposition, multigrid and multiresolution reduction (homogenization) for self-adjoint, strictly elliptic operators. The multiresolution LU decomposition is, in essence, the Gaussian elimination interlaced with projections. The forward and backward substitution may then be interpreted as the “direct” multigrid (a multigrid method without the W-cycles). The corrective W-cycles are not needed since on each scale we construct equations for the orthogonal projection of the true solution. Once these equations are solved, there is no need to return to a coarser scale to correct the solution. Moreover, equations on coarser scales obtained in this manner are of interest by themselves, since they can be interpreted as reduced or “homogenized” equations, leading to numerical multiresolution homogenization. The key to our approach is the use of basis functions with vanishing moments since this property assures sparsity of matrices for a finite but arbitrary accuracy. The sparsity of matrices, in turn, leads to fast algorithms. The approach generalizes to multiple dimensions although additional steps have to be taken to improve the constants in complexity estimates of these algorithms.

Curvelets and Linear Inverse Problems

Emmanuel Candes

Inverse linear problems are considered, especially the problem of Radon inversion in the presence of noise (tomography). The object to be recovered is a function on R^{2} assumed smooth apart from a discontinuity along a C^{2} curve – i.e. an edge. Both sinusoids and wavelets are known to be relatively poor representations of edges, and as a consequence, both the popular SVD and perhaps less-known WVD (Donoho, 1995) approaches are substantially suboptimal.

We apply the rececently-introduced tight frames of curvelets in this setting. Curvelets provide near-optimal representations of otherwise smooth objects with discontinuities along C^{2} curves. Inspired by WVD, we construct a curvelet-based biorthogonal decomposition of the Radon operator and build estimators based on the shrinkage (or thresholding) of the noisy curvelet coefficients. We prove that the shrinkage can be tuned so that the estimator will attain, within logarithmic factors, the optimal estimation rate. In comparison, linear procedures – SVD included – obtain markedly suboptimal rates of convergence, as do WVD shrinkage methods.

Nonlinear multiresolution representations

Albert Cohen

In this talk, I shall discuss data-dependent reconstruction techniques introduced by Ami Harten, which lead to nonlinear multiresolution representations. Some new results concerning stability and approximation properties of these representations will be given, together with some numerical experiments, as well as several open problems.

On the Realization of Adaptive Multiscale Methods

Stephan Dahlke Institut für Geometrie und Praktische Mathematik RWTH Aachen Templergraben 55 52056 Aachen Germany

It can be shown that for a wide class of problems adaptive schemes provide asymptotically better convergence rates than methods based on uniform grid refinement if the solution has higher regularity in a specific scale of Besov spaces than in the usual Sobolev scale. We shall be concerned with a concrete adaptive wavelet scheme that achieves this goal. It aims at determining in the course of the solution process a possibly small set of wavelets needed to recover the solution within some desired error tolerance. N of degrees of freedom (provided that full This talk is primarily concerned with the practical realization and the implementation of the above adaptive scheme. The various building blocks of a first realization are discussed and the performance of the algorithm is studied in detail for some simple but instructive model problems. (Joint work with A. Barinka, T. Barsch, P. Charton, A. Cohen, W. Dahmen, and K. Urban)

Adaptive Wavelet Methods - Elliptic Problems and Extensions

Wolfgang Dahmen, RWTH Aachen joint work with A. Cohen and R. DeVore

This talk is concerned with the adaptive solution of elliptic operator equations.

Typical examples are boundary value problems for elliptic partial differential equations as well as many classical singular integral operators such as the single layer potential, double layer potential and hypersingular operator. The efficient numerical treatment of such problems is obstructed by several factors such as the size of the resulting discrete problems, a possibly growing ill conditioning when the operator has an order different from zero or by the fact that densely populated matrices arise in connection with integral operators. An adaptive wavelet scheme is outlined that aims at determining in the course of the solution process a possibly small set of wavelets needed to recover the solution within some desired error tolerance. It is based on a-posteriori error estimates for the current approximate solution in terms of residuals. The main result is its asymptotic optimality in the sense that (within a certain range of Besov regularity) the convergence rate of best N-term approximation is achieved at a computational expense which stays proportional to the number N of significant degrees of freedom provided that full information on the given data is available. residuals The main ingredients of the analysis are norm equivalences for Sobolev and Besov spaces induced by wavelet expansions, related preconditioning effects, the near sparseness of the wavelet representations of the operators under consideration and the elements of Besov spaces, a new fast approximate matrix-vector multiplication scheme suggested by the analysis and a judicious use of intermediate thresholding of current approximate solutions. While so far ellipticity and symmetry of the problem is crucial for the analysis we indicate several ways of using the results as core ingredients for the treatment of a much wider range of applications covering indefinite systems of operator equations.

Analogue to Digital Conversion with Redundant Systems

Ron DeVore

During August of 1999, a group of mathematicians and engineers met at AT&T Research to try to understand why the most popular and effective methods for Analogue to Digital conversion utilize oversampling and one bit quantizers. In fact this approach seems contrary to mathematical intuition. We shall show that the main advantage of redundancy is in error correcting. We shall point out some related problems whose solution could improve on existing A/D conversion methods.

Non-linear Approximations Using Integer Translates of Mixed Dyadic Scales of a

Single Function

Dinh-Dung Hanoi Institute of Information Technology

We investigate non-linear approximations of multivariate periodic functions with mixed smoothness using the family V formed from the integer translates of the mixed dyadic scales of the tensor product multivariate de la Vallée Poussin kernel. The metric which measures the approximation error is the metric of the space L_{q} = L_{q}(T^{d}) of functions defined on the d-dimensional torus T^{d}. The functions with common mixed smoothness to be approximated are in the unit ball W = SB_{p,θ}^{r} of mixed smoothness Besov space or the unit ball W = SW_{p}^{r} of mixed smoothness Sobolev space. We are interested in the following non-linear L_{q}-approximations of functions from W:

• n-term approximation with regard to the family V via the worst case error σ_{n}(W, V, L_{q}),

• Approximation using continuous algorithms of n-term approximation via the n-widths α_{n}(W, L_{q}) and τ_{n}(W, L_{q}) measuring the error of the optimal continuous algorithm from certain colections of such ones.

• Approximation by functions from finite sets of cardinality ≤ n via the well-known ε-entropy numbers ε_{n}(W, L_{q}) measuring the error of the optimal approximation from all such ones,

• Approximation by functions from sets of psedo-dimension ≤ n via the n-widths ρ_{n}(W, L_{q}) measuring the error of the optimal approximation from all such ones.

For 1 < p, q < ∞, 0 < θ ≤ ∞ and r > 1/p, we established asymptotic orders of these quantities and for each non-linear approximation, constructed corresponding algorithm of n-term approximation with regard to V which gives their upper bound. As well known, these asymptotic orders for both Besov and Sobolev classes in the univariate case are the same n^{−r} independently of any parametres p, q, θ determing (quasi)-norms, and any smoothness r. We proved particularly that the asymptotic order of these quantities for the Besov class SB_{p,θ}^{r} in the multivariate case is the same and equals

n^{−r}(log n)^{(d−1)(r+1/2−1/θ)}.

Surprising is the case when δ = (d − 1)(1/θ − 1/2 − r) > 0, or equivalently, the number of variables of functions d is greater than 1 and for given mixed smoothness r, the Besov quasi-norm scale θ is smaller than (r + 1/2)^{−1}. The asymptotic order of these quantities in this case is n^{−r}(log n)^{−δ} = o(n^{−r}). Thus, the ”paradox” is that the multivariate non-linear approximation can be ”better” than the univariate non-linear one.

Abstract

Fang Jingrong (scip8220@durian.math.nus.edu.sg) Department of Mathematics National University of Singapore Singapore 119260

The nonlinear system modeling problem can be regarded as a scattered data interpolation. In this paper, we develop a new method that computes interpolants that minimize a wavelet-based norm subject to interpolatory constraints. The norm is that of a Reproducing Kernel Hilbert Space(RKHS) for which the wavelet functions that form an orthonormal basis for L^{2}(R) are orthogonal. Comparing with radial basis function kernels, these kernels are not translation invariant and they may be designed to provide spatially varying resolution useful for interpolating from unevenly distributed data samples. Moreover, the discrete wavelet transform can be exploited to efficiently compute the values of the interpolant on a uniform grid. Numerical examples in Sobolev space are given in the details.

Fast Chirp Matching Pursuit for Acoustic Signal Analysis

Remi Gribonval

The Matching Pursuit algorithm is a powerful tool to decompose signals into elementary components chosen among an overcomplete (redundant) dictionary of unit vectors, or atoms.

The basic algorithm, using the Gabor multiscale time-frequency dictionary, is able to decompose acoustic signals into “transients” (associated to short scale atoms) and “stationary parts” (large scale atoms). When a larger dictionary is used, such as the Chirp Dictionary suggested, the computational complexity of this algorithm can become nearly intractable. We will show how it is possible to modify the algorithm, using ridge techniques, to make it tractable. On our way, we will get some insight on the information carried by the ridges of the Gaussian Chirp dictionary.

Hermite Interpolants and Biorthogonal Multiwavelets with Arbitrary Order of

Vanishing Moments

Bin Han

Biorthogonal multiwavelets are generated from refinable function vectors by using multiresolution analyses. To obtain a biorthogonal multiwavelet, we need to construct a pair of primal and dual masks, from which two refinable function vectors are obtained so that a multiresolution analysis is formed to derive a biorthogonal multiwavelet. It is well known that the order of vanishing moments of a biorthogonal multiwavelet is one of the most desirable properties of a biorthogonal multiwavelet in various applications. To design a biorthogonal multiwavelet with high order of vanishing moments, we have to design a pair of primal and dual masks with high order of sum rules. In this talk, we shall discuss an important family of primal masks — Hermite interpolatory masks. A general way for constructing Hermite interpolatory masks with increasing order of sum rules is presented. Such family of Hermite interpolants from the Hermite interpolatory masks includes the piecewise Hermite cubics as a special case. In particular, a C^{3} Hermite interpolant is constructed with support [−3, 3] and multiplicity 2. Next, we shall present a coset by coset (CBC) algorithm to construct biorthogonal multiwavelets with arbitrary order of vanishing moments. By employing the CBC algorithm, several examples of biorthogonal multiwavelets are provided to illustrate the general theory. In particular, a C^{1} dual function vector of the well-known piecewise Hermite cubics is given. For any matrix mask a with any dilation matrix in any multidimensional space, if there exists a dual mask of a, then we shall prove that a dual mask can be constructed by the CBC algorithm such that it satisfies the sum rules of any given order.

Bayesian wavelet shrinkage for nonparametric mixed-effects models

Su-Yun Huang Institute of Statistical Science Academia Sinica, Taipei 11529 Taiwan, Republic of China email:syhuang@stat.sinica.edu.tw

The main purpose of this article is to study the wavelet shrinkage method from a Bayesian viewpoint. Nonparametric mixed-effects models are proposed and used for interpretation of the Bayesian structure. Bayesian and empirical Bayesian estimation are discussed.The latter is shown to have the Gauss-Markov type optimality (i.e., BLUP), to be equivalent to a method of regularization estimator and to be minimax in a certain class. Characterization of prior and posterior regularity is discussed. The smoothness of posterior estimators is controlled via prior parameters. Computational issues including the usage of generalized cross validation are discussed and examples are presented. (This is joint work with H.S. Lu)

Wavelet Least Square Methods for Boundary Value Problems

Angela Kunoth Institut für Angewandte Mathematik Universität Bonn, Germany

                    kunoth@iam.uni-bonn.de
             http://www.igpm.rwth-aachen.de/kunoth

For the numerical solution of stationary operator equations, least square methods will be considered. The primary focus is the combination of the following conceptual issues: the selection of appropriate least square functionals, their numerical evaluation in the context of wavelet methods and a natural way of preconditioning the resulting systems of linear equations.

First the problem is formulated in a general setting to bring out the essential driving mechanisms. Then some special cases that fit into this framework are identified, among them saddle point problems resulting from the separate treatment of essential non-homogeneous boundary conditions for second order elliptic operators. One primary motivation has been the well-known fact that a major obstacle in the context of least square methods based on finite element discretizations is the evaluation of certain norms such as the H^{−1}–norm. In this regard the fact that weighted sequence norms of wavelet coefficients are equivalent to relevant function norms arising in the least squares context are exploited. Truncating the (infinite) wavelet series appropriately leads to stable Galerkin schemes.

This talk is based on:

W. Dahmen, A. Kunoth, R. Schneider, Wavelet least square methods for boundary value problems, IGPM–Preprint #175, RWTH Aachen, September 1999.

New bases for Triebel-Lizorkin and Besov spaces

G. Kyriazis, P. Petrushev

We give a new method for the construction of unconditional bases for general classes of Triebel-Lizorkin and Besov spaces. These include the L_{p}, H_{p}, potential, and Sobolev spaces.The main feature of our method is that the character of the basis functionscan be prescribed in a very general way. In particular, if Φ is any sufficiently smooth and rapidly decaying function, then our method constructs a basis whose elementsare a linear combinations of a fixed (small) number of shifts and dilates of the single function Φ. Typical examples of such Φ’s are the rational function Φ(·) = (1 + | · |^{2})^{−N} and the Gaussian function Φ(·) = e^{−|·|^{2}}. We also show how the new bases can be utilized innonlinear approximation.

The construction of nonstationary orthonormal wavelets

Qi Li and Wai-Shing Tang

Starting from the exponential splines, we construct the nonstationary orthonormal wavelets by establishing the nonstationary refinable sequence of functions. The orthonormality of the nonstationary refinable sequence of functions is characterized by the orthonormality of its limit.

To guarantee the orthonormality of the wavelets we construct, we solve three main problems: 1.the solution of general polynomial equations; 2.the structure of the roots of polynomials. 3. the decreasing rate of the masks in each level.

Size Properties of Wavelet Packets

Morten Nielsen

Wavelet analysis has provided a new class of orthonormal expansions in L^{2} with good time-frequency, regularity, and approximation properties which have been successfully applied to signal processing, numerical analysis, and quantum mechanics. Wavelet packet analysis extends such an orthonormal wavelet expansion to a whole library of orthonormal expansions with different time-frequency properties. The convergence properties of the expansion of a signal in the wavelet basis have been thoroughly studied, whereas the convergence properties of the expansion of a signal in other bases within the wavelet packet library are still unresolved. We will present some new results about the behavior in L^{p} for basic wavelet packets generated using finite filters. We will give an example of a well behaved family of basic wavelet packets related to the Walsh functions that do constitute a basis for the L^{p}- spaces, 1 < p < ∞, and for which the wavelet packet expansions converge pointwise a.e. Then we will show that even “nice” basic wavelet packets can fail to be a basis for L^{p} for p large. The failure is due to the size of the basic wavelet packets in the L^{p}-spaces.

Time-frequency uncertainty of compactly supported wavelets

Novikov Igor Ya.

Time-frequency uncertainty is a significant parameter characterizing time and frequency concentration of wavelets. Chui and Wang have shown that time-frequency uncertainty of classical Daubechies wavelets increases without bound as the wavelets are made arbitrary smooth [ChW]. In [N] a modification of Daubechies construction was considered which leads to compactly supported wavelets with uniformly bounded time-frequency uncertainty constants with respect to regularity parameter.

The aim of the talk is to present in details one special kind of such modification (the simplest one). Using spectral factorization, modified wavelets with minimum time-frequency uncertainty are defined. They are compared with classical Daubechies wavelets of the same order.

[ChW]. Chui C., and J. Wang. High-order orthonormal scaling functions and wavelets give poor time-frequency localization. Techn. report # 322, Center for approximation theory, Department of mathematics, Texas A& M University 1994. [N]. Novikov I.Ya. Modified Daubechies wavelets preserving localization with growth of smoothness. East J. Approximation 1 (1995), 341-348.

Novikov Igor Ya. Associate Professor, Dr. Voronezh State University. Voronezh State University University Square 1, 394693 Voronezh, Russia mail@igorno.vrn.ru

Ridge approximation, gridge algorithms and optimization of cubature formulas

Konstantin Oskolkov

Let d ≥ 2 x := ⟨x_{1}, …, x_{d}⟩ ∈ IR^{d}, θ ∈ S^{d−1}, N – a natural number, f(x) – a function of d real variables.

Ridge approximation (free) consists in the solution of the extremal problem of approximation of f(x) by N term linear combinations of planar waves

R_{N}^{fr}[f] := inf_{{θ_{j}}_{1}^{N} ⊂S^{d−1}} inf_{{W_{j}(t)}_{1}^{N}} ∥f(x) − ∑_{j=1}^{N} W_{j}(x · θ_{j})∥ ,

where ∥ · ∥ denotes a functional norm for d-variate functions.

In gridge algorithm, planar wave functions W (x · θ) appear stepwise (recursively):

(θ^{(N)}, W^{(N)}(t)) := arg \{{min \atop θ} min_{W (t)} ∥(f(x) − ∑_{j=0}^{N−1} W^{(j)} (x · θ^{(j)})) − W (x · θ)∥\} .

Obviously, R_{N}^{fr}[f] ≤ R_{N}^{gr}[f] := ∥f(x) − ∑_{0}^{N−1} W^{(j)}(x · θ^{(j))}∥.

The talk will be dedicated to non-trivial estimates of R_{N}^{fr}[f] from below and those of R_{N}^{gr}[f] from above, in terms of the classical best polynomial approximations

E_{M}[f] := min_{P ∈P^{d,M}} ∥f(x) − P (x)∥, P^{d,M} := Span {x_{1}^{k_{1}} ⋯ x_{d}^{k_{d}}}_{k_{1}+···+k_{d}≤M} .

In particular, realization of the gridge algorithm, the role of Radon compass and dual problems of optimal cubature formulas on the sphere S^{d−1}, with the elements of adaptivity in the case of gridge algorithms, will be discussed.

On some inverse estimates for nonlinear approximation

P. Petrushev

We obtain inverse estimates for nonlinear approximation by non-nested piecewise polynomial functions. This is a case when the Bernstein inequality fails to exist. We will formulate and discuss some open problems regarding inverse estimates for nonlinear approximation and, in particular, nonlinear n-term approximation.

Wavelet bases, associated with recursive filters, and their applications to image

and video compression

Alexander Petukhov

For the last 10 years the theory of compactly supported wavelet bases became a powerful tool for many theoretical and applied problems, relating to signal processing. The algorithms of expansion of functions in such bases are implemented as a collection of discrete convolutions with numerical sequences, which has only finite number of non-zero coefficients, i.e., finite impulse response (FIR) filters. The frequency characteristic of FIR filter is a trigonometric polynomial.

We consider wavelet bases, such that expansion in them is implemented with filters with a rational frequency response. The new types of wavelet bases give new opportunities for image and video compression.

Despite the fact, that this types of filters has infinite impulse response (IIR-filters), there is an effective numerical realization in the form of a composition of well known in a radio engineering, so-called, recursive filters. The computional complexity for realization of filters with a rational frequency response are proportional to a sum of degrees of the numerator and the denominator, that is comparable to complexity of expansions in compactly supported bases.

Regularized Shannon Sampling Formula and its numerical application on PDEs

Liwen Qian and G. W. Wei Department of Computational Science, National University of Singapore Singapore 117543

Error estimation is given for a regularized Shannon’s sampling formula, which was found to be accurate and robust for numerically solving partial differential equations.

Key words. Shannon’s sampling formula, compactly supported wavelets, error estimate, regularization AMS subject classifications: 41A80, 41A30, 65D25, 65G99, 94A24.

Approximation by discrete translates of functions on Euclidean domains and sphere

Amos Ron

Given a function ϕ and a discrete subset Ξ ⊂ R^{d}, we are interested in the approximation properties of the space

S_{Ξ}(ϕ) := span{ϕ(· − ξ) : ξ ∈ Ξ}.

An analogous problem can be defined on the sphere, and on general manifolds and topological groups.

This problem is of fundamental importance in Approximation Theory and in many other areas of mathematics, and has vast applications. Substantial progress was achieved in the last ten years in developing suitable theories and tools for special cases of the above problem. Most notably are the theory of shift-invariant spaces, and the approximation by scattered shifts of positive definite basis functions. Very little progress was recorded on the general theory. Of major significance is the identification of basis functions ϕ that are ‘universal’ for approximation, i.e., that yield ‘good’ space S_{Ξ}(ϕ) regardless of the actual geometric configuration of the pointset Ξ.

I will review some of main achievements of the last ten years on this problem, primarily in the area of shift-invariant spaces. I will then describe the directions that were tried 4-5 years ago to extend the tools of shiftinvariant spaces to the general non-structured case. The tools created via shift-invariance theory allow us, on Euclidean domains, to handle basis functions whose Fourier transform is singular at the origin, but left many gaps and unanswered questions.

Moreover, the above-mentioned theory does not apply to approximation to more general domains. To this end, we are developing now a general theory that will apply to Euclidean domains, spheres and, perhaps, more general domains. Currently, the analysis is done simultaneously on the space and the Fourier domains. The theory enables us to identify the ‘universal’ basis functions ϕ, and to devise general approximation maps into spaces of the form S_{Ξ}(ϕ).

Weyl-Heisenberg frames and Riesz bases in L_{2}(R^{d})

Zuowei Shen Department of Mathematics National University of Singapore

We study Weyl-Heisenberg (=Gabor) expansions for either L_{2}(R^{d}) or a subspace of it. These are expansions in terms of the spanning set,

X = (E^{k}M^{l}ϕ : k ∈ K, l ∈ L, ϕ ∈ Φ),

where K and L are some discrete lattices in R^{d}, Φ ⊂ L_{2}(R^{d}) is finite, E is the translation operator, and M is a modulation operator. Such sets X are known as WH systems. The analysis of the “basis” properties of WH systems (e.g. being a frame or a Riesz basis) is our central topic, with the fiberization-decomposition techniques of shift-invariant systems, developed in our earlier work, being the main tool.

Of particular interest is the notion of the adjoint of a WH set, and the duality principle which characterizes a WH (tight) frame in term of the stability (orthonormality) of its adjoint. The actions of passing to the adjoint and passing to the dual system commute, hence the dual WH frame can be computed via the dual basis of the adjoint.

This is a joint work with Amos Ron.

Universal Bases and Greedy Algorithms

Vladimir Temlyakov

We work this strategy out in the model case of anisotropic function classes and the set of orthogonal bases. The results are positive. We construct a natural tensor-product-wavelet type basis and prove that it is universal. Moreover, we prove that greedy algorithm realizes near best m-term approximation with regard to this basis for all anisotropic function classes.

Wavelets and distortion invariant properties of signals and images

Hans Wallin

In signal processing the original signal or image can be disturbed in different ways. For instance, the measurement of the signal is not exact and there may be a time delay in the transmission. Furthermore, in the mathematical treatment we use an approximation of the signal. Consequently, the problem arises to find properties of the signal which are preserved under distortion. By distortion we mean composition of the signal with a continuous one-to-one function. It turns out that distortion invariants may be characterized by using wavelet expansions. In fact, under certain conditions on the wavelet and the distortion, the absolute convergence of the series of Fourier coefficients of the wavelet expansion is such an invariant. Reporting on joint work with Amiran Ambroladze and Vassil Bugadze I shall discuss some results in this direction.

A CFL-Free, Explicit Scheme for Linear Hyperbolic PDEs, a Contradiction to the

CFL Condition?

Hong Wang

Linear Hyperbolic PDEs arise in many important applications. The solutions of these PDEs present sharp fronts and even shock discontinuities, which need to be resolved accurately in applications and often present severe numerical difficulties. Because of their simplicity and locality, explicit methods have traditionally been the dominating methods for linear hyperbolic equations. Unfortunately, they are subject to the CFL constraint, and sometimes the Courant number has to be siginificantly less than one.

We develop an unconditionally stable, explicit scheme for advection-reaction PDEs in multiple spatial dimensions by using wavelets and multi-resolution analysis. The methods resolve sharp fronts and capture shock discontinuities in a systematical and adaptive way. Moreover, the numerical solutions can be compressed in a mass-conservative manner.

Tree Approximation in F_{p}

R. Baraniuk, R. A. DeVore, G. Kyriazis and X. M. Yu

In this draft, we investigate the ways of generating tree approximation, which is a new form of nonlinear approximation with a tree-structure. The Jackson and Bernstein inequalities are established for near best tree approximation to functions in F_{p}.

Joint Spectral Radius and Its Applications in Wavelets

Ding-Xuan Zhou Department of Mathematics City University of Hong Kong Email: mazhou@math.cityu.edu.hk

Let A be a finite multiset of square complex matrices of the same order and ∥ · ∥ be a matrix norm. For 0 < p < ∞, the p-norm joint spectral radius ρ_{p}(A) of A is defined by

ρ_{p}(A) := lim_{n→∞}{ ∑_{A_{1},···,A_{n}∈A} ∥A_{1} ⋯ A_{n}∥^{p}}^{1/np}.

This concept plays an important role in the investigation of wavelets and subdivision schemes. However, the limit is reached very slowly, and usually it is uneffective to compute the p-norm joint spectral radius by the definition.

The purpose of this talk is to give a formula for computing ρ_{p}(A) in terms of the spectral radius of some finite matrix when p is an even integer:

ρ_{2k}(A) = \{ρ( ∑_{A∈A}(\overline{A} ⊗ A)^{[k]})\}^{1/2k}, k ∈ IN,

where for A ∈ C^{m×m}, B ∈ C^{n×n}, A ⊗ B is the Kronecker product defined to be the blockmatrix

A ⊗ B = (a_{jk}B)_{j,k=1}^{m} ∈ C^{mn×mn},

and for k ∈ IN, A^{[k+1]} = A ⊗ A^{[k]}, A^{[1]} = A.

Some applications of the p-norm joint spectral radius in wavelets will be discussed.

On Müntz Rational Approximation Rate in L^{p} Spaces

Wei Xiao and Songping Zhou ^{2}

1991 Mathematics Subject Classification: 41A20 41A30

Let L_{[0,1]}^{p} be the space of all p-power integrable functions on [0, 1], 1 ≤ p < ∞, and C_{[0,1]} = L_{[0,1]}^{∞}, for convenience, the space of all continuous functions on [0, 1]. Given a nonnegative (strict) increasing sequence {λ_{n}},denote by Π_{n}(Λ) the set of Müntz polynomials of degree n, that is, all linear combinations of {x^{λ_{1}}, x^{λ_{2}}, ⋯, x^{λ_{n}}}, and by R_{n}(Λ) the Müntz rational functions of degree n, that is^{3},

R_{n}(Λ) = {P (x)/Q(x) : P, Q ∈ Π_{n}(Λ); Q(x) ≥ 0, x ∈ (0, 1]}.

For f ∈ L_{[0,1]}^{p},1 ≤ p ≤ ∞, define

R_{n}(f)_{L^{p}} = inf_{r∈R_{n}(Λ)} ∥f − r∥_{L^{p}},

ω(f, t)_{L^{p}} = sup_{|h|≤t} (∫_{E} |f(x + h) − f(x)|^{p}dx)^{1/p} , 1 ≤ p < ∞,

where E = [0, 1 − h] for 0 ≤ h ≤ 1, or E = [−h, 1] for −1 ≤ h < 0 , and

ω(f, t)_{L^{∞}} = sup_{|h|≤t} max_{0≤x,x+h≤1} |f(x + h) − f(x)|.

As we know, it is a hard subject how to estimate general Müntz rational approximation rate. In last dozens years, there are some pretty works done in [1-4], and a very hard open problem left in [3]. Among them, we citea result of Bak [1] here. Theorem 1. Given M > 0. If λ_{n+1} − λ_{n} ≥ Mn for all n ≥ 1, then there is a positive constant C_{M} only depending upon M such that

2Supported in part by National and Zhejiang Provincial Natural Science Foundations, and by State Key Laboratory of Southwest Institute of Petroleum.

3If Q(0) = 0, we require that lim_{x→0+} P (x)/Q(x) exist and be finite.

R_{n}(f)_{L^{∞}} ≤ C_{M}ω(f, n^{−1})_{L^{∞}}.

The present paper considers to generalize the above thereom to conclude the general L^{p} spaces. In Müntz rational approximation case, as one can see from the proof, this work is not so easy to be done as in usual polynomial approximation case.Exactly, we establish the following theorem. Theorem

2. Given M > 0, 1 ≤ p ≤ ∞. If λ_{n+1} − λ_{n} ≥ Mn for all n ≥ 1, then there is a positive constant C_{M} only depending upon M such that

R_{n}(f)_{L^{p}} ≤ C_{M}ω(f, n^{−1})_{L^{p}}.

Remark. For positive linear polynomial operators with the form ∑_{k=1}^{n} n ∫_{(k−1)/n}^{k/n} f(t)dt×

P_{n,k}(x) (for example, the Bernstein-Baskakov operators), to consider the approximation in L^{p} space people usually use some asymptotic formula of P_{n,k}(x) to achieve the required estimates, that method usually cannot be applied to rational operators, especially to our case. From this point of view, the method used in this paper could be useful in estimating the approximation rate by rational operators.

References

1. J. Bak, On the efficiency of general rational approximation, J.Aprrox. theory 20(1977), 46-50.

2. M. von Golitschek and D. Leviatan, Rational Müntz approximation, Ann. Numer. Math. 2(1995), 425-437.

3. D. G. Newman, Approximation with rational functions, The American Mathematical Society, the Providence, Rhode Island, 1979.

4. S. P. Zhou: Rational approximation rate for Müntz system {x^{λ_{n}}} with λ_{n} ↘ 0, J. Comput.Appl. Math. 53(1994), 11-19.

5. S. P. Zhou: A note on rational approximation for Müntz system {x^{λ_{n}}} with λ_{n} ↘ 0, Anal. Math. 20(1994), 155-159.

Songping Zhou: The Mathematical Institute Ningbo University Ningbo, Zhejiang 315211 China

Wei Xiao: Department of Mathematics Zhejiang University Hangzhou, Zhejiang 310028 China

and

State Key Laboratory Southwest Institute of Petroleum Nangchong, Sichuan 637001 China