An Equivalence Relation between Multiresolution Analysis ofL(R)

This paper is concerned with the development of an equivalence relation between two multiresolution analysis ofL²(R). The relation called unitary equivalence is created by the action of a unitary operator in such a way that the multiresolution structure and the decomposition and reconstruction algorithms remain invariant. A characterization in terms of the scaling functions of the multiresolution analysis is given. Distinct equivalence classes of multiresolution analysis are derived. Finally, we prove that B-splines give rise to nonequivalent examples.     

Radial Multiresolution, Cuntz Algebras Representations and an Application to Fractals

We study Bernoulli type convolution measures on attractor sets arising from iterated function systems on R. In particular we examine orthogonality for Hankel frequencies in the Hilbert space of square integrable functions on the attractor coming from a radial multiresolution analysis on R³. A class of fractals emerges from a finite system of contractive affine mappings on the zeros of Bessel functions. We have then fractal measures on one hand and the geometry of radial wavelets on the other hand. More generally, multiresolutions serve as an operator theoretic framework for the study of such selfsimilar structures as wavelets, fractals, and recursive basis algorithms. The purpose of the present paper is to show that this can be done for a certain Bessel–Hankel transform. Submitted: February 20, 2008., Accepted: March 6, 2008.     

Fully adaptive multiresolution finite volume schemes for conservation laws

The use of multiresolution decompositions in the context of finite volume schemes for conservation laws was first proposed by A. Harten for the purpose of accelerating the evaluation of numerical fluxes through an adaptive computation. In this approach the solution is still represented at each time step on the finest grid, resulting in an inherent limitation of the potential gain in memory space and computational time. The present paper is concerned with the development and the numerical analysis of fully adaptive multiresolution schemes, in which the solution is represented and computed in a dynamically evolved adaptive grid. A crucial problem is then the accurate computation of the flux without the full knowledge of fine grid cell averages. Several solutions to this problem are proposed, analyzed, and compared in terms of accuracy and complexity.

     

Characterizations of orthonormal scale functions: A probabilistic approach

The construction of a multiresolution analysis starts with the specification of a scale function. The Fourier transform of this function is defined by an infinite product. The convergence of this product is usually discussed in the context of L ²(R).Here, we treat the convergence problem by viewing the partial products as probabilities, converging weakly to a probability defined on an appropriate sequence space. We obtain a sufficient condition for this convergence, which is also necessary in the case where the scale function is continuous. These results extend and clarify those of Cohen [2] and Hernández et al. [4]. The method also applies to more general dilation schemes that commute with translations by Z ^d .     

Wavelet decompositions of L 2-functionals

Based on distribution-theoretical definitions of L ₂ and Sobolev spaces given by Werner in [P. Werner (1970). A distribution-theoretical approach to certain Lebesgue and Sobolev spaces. J. Math. Anal. Appl., 29, 19–78.] real interpolation, Besov type spaces and approximation spaces with respect to multiresolution approximations are considered. The key for the investigation are generalized moduli of smoothness introduced by Haf in [H. Haf (1992). On the approximation of functionals in Sobolev spaces by singular integrals. Applicable Analysis, 45, 295–308.]. Those moduli of smoothness allow to connect the concept of L ₂-functionals with more recent developments in multiscale analysis, see e.g. [W. Dahmen (1995). Multiscale analysis, approximation, and interpolation spaces. In: C.K. Chui and L.L. Schumaker (Eds.), Approximation Theory VIII, Vol. 2: Wavelets and Multilevel Approximation, pp. 47–88.]. In particular, we derive wavelet characterizations for the Sobolev spaces introduced by Werner and establish stable wavelet decompositions of L ₂-functionals. Generalizations to more general spaces of functionals and applications are also mentioned.     

Deconvolution: a wavelet frame approach

This paper devotes to analyzing deconvolution algorithms based on wavelet frame approaches, which has already appeared in Chan et al. (SIAM J. Sci. Comput. 24(4), 1408–1432, 2003; Appl. Comput. Hormon. Anal. 17, 91–115, 2004a; Int. J. Imaging Syst. Technol. 14, 91–104, 2004b) as wavelet frame based high resolution image reconstruction methods. We first give a complete formulation of deconvolution in terms of multiresolution analysis and its approximation, which completes the formulation given in Chan et al. (SIAM J. Sci. Comput. 24(4), 1408–1432, 2003; Appl. Comput. Hormon. Anal. 17, 91–115, 2004a; Int. J. Imaging Syst. Technol. 14, 91–104, 2004b). This formulation converts deconvolution to a problem of filling the missing coefficients of wavelet frames which satisfy certain minimization properties. These missing coefficients are recovered iteratively together with a built-in denoising scheme that removes noise in the data set such that noise in the data will not blow up while iterating. This approach has already been proven to be efficient in solving various problems in high resolution image reconstructions as shown by the simulation results given in Chan et al. (SIAM J. Sci. Comput. 24(4), 1408–1432, 2003; Appl. Comput. Hormon. Anal. 17, 91–115, 2004a; Int. J. Imaging Syst. Technol. 14, 91–104, 2004b). However, an analysis of convergence as well as the stability of algorithms and the minimization properties of solutions were absent in those papers. This paper is to establish the theoretical foundation of this wavelet frame approach. In particular, a proof of convergence, an analysis of the stability of algorithms and a study of the minimization property of solutions are given.     

Normal Multiresolution Approximation of Curves

A multiresolution analysis of a curve is normal if each wavelet detail vector with respect to a certain subdivision scheme lies in the local normal direction. In this paper we study properties such as regularity, convergence, and stability of a normal multiresolution analysis. In particular, we show that these properties critically depend on the underlying subdivision scheme and that, in general, the convergence of normal multiresolution approximations equals the convergence of the underlying subdivision scheme.     

An adaptive multiresolution method on dyadic grids: Application to transport equations

We propose a modified adaptive multiresolution scheme for solving d$d$-dimensional hyperbolic conservation laws which is based on cell-average discretization in dyadic grids. Adaptivity is obtained by interrupting the refinement at the locations where appropriate scale (wavelet) coefficients are sufficiently small. One important aspect of such a multiresolution representation is that we can use the same binary tree data structure for domains of any dimension. The tree structure allows us to succinctly represent the data and efficiently navigate through it. Dyadic grids also provide a more gradual refinement as compared with the traditional quad-trees (2D) or oct-trees (3D) that are commonly used for multiresolution analysis. We show some examples of adaptive binary tree representations, with significant savings in data storage when compared to quad-tree based schemes. As a test problem, we also consider this modified adaptive multiresolution method, using a dynamic binary tree data structure, applied to a transport equation in 2D domain, based on a second-order finite volume discretization.     

Adaptive Isotopic Approximation of Nonsingular Curves: the Parameterizability and Nonlocal Isotopy Approach

We consider domain subdivision algorithms for computing isotopic approximations of a nonsingular algebraic curve. The curve is given by a polynomial equation f(X,Y)=0. Two algorithms in this area are from Snyder (1992) SIGGRAPH Comput. Graphics, 26(2), 121 and Plantinga and Vegter (2004) In Proc. Eurographics Symposium on Geometry Processing, pp. 245–254. We introduce a new algorithm that combines the advantages of these two algorithms: like Snyder, we use the parameterizability criterion for subdivision, and like Plantinga and Vegter, we exploit nonlocal isotopy. We further extend our algorithm in two important and practical directions: first, we allow subdivision cells to be rectangles with arbitrary but bounded aspect ratios. Second, we extend the input domains to be regions R ₀ with arbitrary geometry and which might not be simply connected. Our algorithm halts as long as the curve has no singularities in the region, and intersects the boundary of R ₀ transversally. Our algorithm is practical and easy to implement exactly. We report some very encouraging experimental results, showing that our algorithms can be much more efficient than the algorithms of Plantinga–Vegter and Snyder.     

Data compression based on the cubic B-spline wavelet with uniform two-scale relation

The aim of this paper is to investigate the potential artificial compression which can be achieved using an interval multiresolution analysis based on a semiorthogonal cubic B-spline wavelet. The Chui-Quak [1] spline multiresolution analysis for the finite interval has been modified [2] so as to be characterized by natural spline projection and uniform two-scale relation. Strengths and weaknesses of the semiorthogonal wavelet as regards artificial compression and data smoothing by the method of thresholding wavelet coefficients are indicated.     

Bi-frames with 4-fold axial symmetry for quadrilateral surface multiresolution processing

When bivariate filter banks and wavelets are used for surface multiresolution processing, it is required that the decomposition and reconstruction algorithms for regular vertices derived from them have high symmetry. This symmetry requirement makes it possible to design the corresponding multiresolution algorithms for extraordinary vertices. Recently lifting-scheme based biorthogonal bivariate wavelets with high symmetry have been constructed for surface multiresolution processing. If biorthogonal wavelets have certain smoothness, then the analysis or synthesis scaling function or both have big supports in general. In particular, when the synthesis low-pass filter is a commonly used scheme such as Loop’s scheme or Catmull-Clark’s scheme, the corresponding analysis low-pass filter has a big support and the corresponding analysis scaling function and wavelets have poor smoothness. Big supports of scaling functions, or in other words big templates of multiresolution algorithms, are undesirable for surface processing. On the other hand, a frame provides flexibility for the construction of “basis” systems. This paper concerns the construction of wavelet (or affine) bi-frames with high symmetry.In this paper we study the construction of wavelet bi-frames with 4-fold symmetry for quadrilateral surface multiresolution processing, with both the dyadic and refinements considered. The constructed bi-frames have 4 framelets (or frame generators) for the dyadic refinement, and 2 framelets for the refinement. Namely, with either the dyadic or refinement, a frame system constructed in this paper has only one more generator than a wavelet system. The constructed bi-frames have better smoothness and smaller supports than biorthogonal wavelets. Furthermore, all the frame algorithms considered in this paper are given by templates so that one can easily implement them.     

Biorthogonal wavelets with 4-fold axial symmetry for quadrilateral surface multiresolution processing

Surface multiresolution processing is an important subject in CAGD. It also poses many challenging problems including the design of multiresolution algorithms. Unlike images which are in general sampled on a regular square or hexagonal lattice, the meshes in surfaces processing could have an arbitrary topology, namely, they consist of not only regular vertices but also extraordinary vertices, which requires the multiresolution algorithms have high symmetry. With the idea of lifting scheme, Bertram (Computing 72(1–2):29–39, 2004) introduces a novel triangle surface multiresolution algorithm which works for both regular and extraordinary vertices. This method is also successfully used to develop multiresolution algorithms for quad surface and \(\sqrt 3\) triangle surface processing in Wang et al. (Vis Comput 22(9–11):874–884, 2006; IEEE Trans Vis Comput Graph 13(5):914–925, 2007) respectively. When considering the biorthogonality, these papers do not use the conventional \(L^2({{\rm I}\kern-.2em{\rm R}}^2)\) inner product, and they do not consider the corresponding lowpass filter, highpass filters, scaling function and wavelets. Hence, some basic properties such as smoothness and approximation power of the scaling functions and wavelets for regular vertices are unclear. On the other hand, the symmetry of subdivision masks (namely, the lowpass filters of filter banks) for surface subdivision is well studied, while the symmetry of the highpass filters for surface processing is rarely considered in the literature. In this paper we introduce the notion of 4-fold symmetry for biorthogonal filter banks. We demonstrate that 4-fold symmetric filter banks result in multiresolution algorithms with the required symmetry for quad surface processing. In addition, we provide 4-fold symmetric biorthogonal FIR filter banks and construct the associated wavelets, with both the dyadic and \(\sqrt 2\) refinements. Furthermore, we show that some filter banks constructed in this paper result in very simple multiresolution decomposition and reconstruction algorithms as those in Bertram (Computing 72(1–2):29–39, 2004) and Wang et al. (Vis Comput 22(9–11):874–884, 2006; IEEE Trans Vis Comput Graph 13(5):914–925, 2007). Our method can provide the filter banks corresponding to the multiresolution algorithms in Wang et al. (Vis Comput 22(9–11):874–884, 2006) for dyadic multiresolution quad surface processing. Therefore, the properties of the scaling functions and wavelets corresponding to those algorithms can be obtained by analyzing the corresponding filter banks.     

On the Problem of the Flow of an Ideal Gas around Bodies

We construct biorthogonal bases of spaces of an n-separate multiresolution analysis and wavelets for n scaling functions. Fast algorithms are presented for finding the coefficients of expansions of functions in such bases.     

A General Multiresolution Method for Fitting Functions on the Sphere

In [7], Lyche and Schumaker have described a method for fitting functions of class C ¹ on the sphere which is based on tensor products of quadratic polynomial splines and trigonometric splines of order three associated with uniform knots. In this paper, we present a multiresolution method leading to C ²-functions on the sphere, using tensor products of polynomial and trigonometric splines of odd order with arbitrary simple knot sequences. We determine the decomposition and reconstruction matrices corresponding to the polynomial and trigonometric spline spaces. We describe the general tensor product decomposition and reconstruction algorithms in matrix form which are convenient for the compression of surfaces. We give the different steps of the computer implementation of these algorithms and, finally, we present a test example.     

Nonseparable Radial Frame Multiresolution Analysis in Multidimensions

Abstract

In this article we present a nonseparable multiresolution structure based on frames which is defined by radial frame scaling functions. The Fourier transform of these functions is the indicator (characteristic) function of a measurable set. We also construct the resulting frame multiwavelets, which can be isotropic as well. Our construction can be carried out in any number of dimensions and for a big variety of dilation matrices.     

Quick Approximation to Matrices and Applications

m ×n matrix A with entries between say −1 and 1, and an error parameter ε between 0 and 1, we find a matrix D (implicitly) which is the sum of simple rank 1 matrices so that the sum of entries of any submatrix (among the ) of (A−D) is at most εmn in absolute value. Our algorithm takes time dependent only on ε and the allowed probability of failure (not on m, n). We draw on two lines of research to develop the algorithms: one is built around the fundamental Regularity Lemma of Szemerédi in Graph Theory and the constructive version of Alon, Duke, Leffman, R?dl and Yuster. The second one is from the papers of Arora, Karger and Karpinski, Fernandez de la Vega and most directly Goldwasser, Goldreich and Ron who develop approximation algorithms for a set of graph problems, typical of which is the maximum cut problem. From our matrix approximation, the above graph algorithms and the Regularity Lemma and several other results follow in a simple way. We generalize our approximations to multi-dimensional arrays and from that derive approximation algorithms for all dense Max-SNP problems. Received: July 25, 1997     

Biorthogonal Multiwavelets on the Interval: Cubic Hermite Splines

Starting with Hermite cubic splines as the primal multigenerator, first a dual multigenerator on R is constructed that consists of continuous functions, has small support, and is exact of order 2. We then derive multiresolution sequences on the interval while retaining the polynomial exactness on the primal and dual sides. This guarantees moment conditions of the corresponding wavelets. The concept of stable completions [CDP] is then used to construct the corresponding primal and dual multiwavelets on the interval as follows. An appropriate variation of what is known as a hierarchical basis in finite element methods is shown to be an initial completion. This is then, in a second step, projected into the desired complements spanned by compactly supported biorthogonal multiwavelets. The masks of all multigenerators and multiwavelets are finite so that decomposition and reconstruction algorithms are simple and efficient. Furthermore, in addition to the Jackson estimates which follow from the exactness, one can also show Bernstein inequalities for the primal and dual multiresolutions. Consequently, sequence norms for the coefficients based on such multiwavelet expansions characterize Sobolev norms ||⋅|| _Hs([0,1]) for s∈ (-0.824926,2.5) . In particular, the multiwavelets form Riesz bases for L ₂ ([0,1]) . February 2, 1998. Date revised: February 19, 1999. Date accepted: March 5, 1999.     

A General Approach to Gibbs Phenomenon

Gibbs phenomenon occurs for most approximations based on standard orthogonal expansions, as well as for those based on integral operators. It also occurs in interpolations and other types of approximations. We consider a general approach to approximation based on delta sequences in an attempt to better understand the concept.     

A generalization of de Boor’s stability result and symmetric preconditioning

We provide a symmetric preconditioning method based on weighted divided differences which can be applied in order to solve certain ill-conditioned scattered-data interpolation problems in a stable way; more precisely, our method applies to cases where the ill-conditioning comes from the fact that the basis function is slowly growing, and the number of interpolation points is large. Concerning the theoretical background, an a priori unbounded operator on ?₂(?) is preconditioned so as to get a bounded and coercive operator. The method has another and probably even more interesting interpretation in terms of constructing certain Riesz bases of appropriate closed subspaces ofL ₂(?). In extending Mallat’s multiresolution analysis to the scattered data case, we construct nested sequences of spaces giving rise to orthogonal decompositions of functions inL ₂(?); in this way the idea of wavelet decompositions is (theoretically) carried over to scattered-data methods.