Application of wavelet bases in linear and nonlinear approximation to functions from Besov spaces

Linear and nonlinear approximations to functions from Besov spaces B _{p, q} ^σ ([0, 1]), σ > 0, 1 ≤ p, q ≤ ∞ in a wavelet basis are considered. It is shown that an optimal linear approximation by a D-dimensional subspace of basis wavelet functions has an error of order D ^{-min(σ, σ + 1/2 ? 1/p)} for all 1 ≤ p ≤ ∞ and σ > max(1/p ? 1/2, 0). An original scheme is proposed for optimal nonlinear approximation. It is shown how a D-dimensional subspace of basis wavelet functions is to be chosen depending on the approximated function so that the error is on the order of D ^?σ for all 1 ≤ p ≤ ∞ and σ > max(1/p ? 1/2, 0). The nonlinear approximation scheme proposed does not require any a priori information on the approximated function.     

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.     

Near Best Tree Approximation

Tree approximation is a form of nonlinear wavelet approximation that appears naturally in applications such as image compression and entropy encoding. The distinction between tree approximation and the more familiar n-term wavelet approximation is that the wavelets appearing in the approximant are required to align themselves in a certain connected tree structure. This makes their positions easy to encode. Previous work [4,6] has established upper bounds for the error of tree approximation for certain (Besov) classes of functions. This paper, in contrast, studies tree approximation of individual functions with the aim of characterizing those functions with a prescribed approximation error. We accomplish this in the case that the approximation error is measured in L ₂, or in the case p2, in the Besov spaces B _p ⁰(L _p ), which are close to (but not the same as) L _p . Our characterization of functions with a prescribed approximation order in these cases is given in terms of a certain maximal function applied to the wavelet coefficients.     

Ridge Functions and Orthonormal Ridgelets

Orthonormal ridgelets provide an orthonormal basis for L²(R²) built from special angularly-integrated ridge functions. In this paper we explore the relationship between orthonormal ridgelets and true ridge functions r(x₁ cos θ+x₂ sin θ). We derive a formula for the ridgelet coefficients of a ridge function in terms of the 1-D wavelet coefficients of the ridge profile r(t). The formula shows that the ridgelet coefficients of a ridge function are heavily concentrated in ridge parameter space near the underlying scale, direction, and location of the ridge function. It also shows that the rearranged weighted ridgelet coefficients of a ridge function decay at essentially the same rate as the rearranged weighted 1-D wavelet coefficients of the 1-D ridge profile r(t). In short, the full ridgelet expansion of a ridge function is in a certain sense equally as sparse as the 1-D wavelet expansion of the ridge profile. It follows that partial ridgelet expansions can give good approximations to objects which are countable superpositions of well-behaved ridge functions. We study the nonlinear approximation operator which “kills” coefficients below certain thresholds (depending on angular- and ridge-scale); we show that for approximating objects which are countable superpositions of ridge functions with 1-D ridge profiles in the Besov space B^1/p_p, p(R), 0<p<1, the thresholded ridgelet approximation achieves optimal rates of N-term approximation. This implies that appropriate thresholding in the ridgelet basis is equally as good, for certain purposes, as an ideally-adapted N-term nonlinear ridge approximation, based on perfect choice of N-directions.     

Asymptotic expansions for the variance of stopping times in nonlinear renewal theory

We treat the problem of finding asymptotic expansions for the variance of stopping times for Wiener processes with positive drift (continuous time case) as well as sums of i.i.d. random variables with positive mean (discrete time case). Carrying over the setting of nonlinear renewal theory to Wiener processes, we obtain an asymptotic expansion up to vanishing terms in the continuous time case. Applying the same methods to sums of i.i.d. random variables, we also provide an expansion in the discrete time case up to terms of order o(b^1/2) where the leading term is of order O(b), as b → ∞. The possibly unbounded term is the covariance of nonlinear excess and stopping time.     

Best approximation with wavelets in weighted Orlicz spaces

Democracy functions of wavelet admissible bases are computed for weighted Orlicz Spaces L ^??(w) in terms of the fundamental function of L ^??(w). In particular, we prove that these bases are greedy in L ^??(w) if and only if L ^??(w) =?L ^p (w), 1?<?p?<???. Also, sharp embeddings for the approximation spaces are given in terms of weighted discrete Lorentz spaces. For L ^p (w) the approximation spaces are identified with weighted Besov spaces.     

A note on adaptive approximation in Sobolev spaces

In this article, we consider the adaptive approximation in Sobolev spaces. After establishing some norm equivalences and inequalities in Besov spaces, we are able to prove that the best N terms approximation with wavelet‐like basis in Sobolev spaces exhibits the proper approximation order in terms of N^?1. This indicates that the computational load in adaptive approximation is proportional to the approximation accuracy. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

A new approach to fuzzy wavelet system modeling

In this paper, we propose simple but effective two different fuzzy wavelet networks (FWNs) for system identification. The FWNs combine the traditional Takagi–Sugeno–Kang (TSK) fuzzy model and discrete wavelet transforms (DWT). The proposed FWNs consist of a set of if–then rules and, then parts are series expansion in terms of wavelets functions. In the first system, while the only one scale parameter is changing with it corresponding rule number, translation parameter sets are fixed in each rule. As for the second system, DWT is used completely by using wavelet frames. The performance of proposed fuzzy models is illustrated by examples and compared with previously published examples. Simulation results indicate the remarkable capabilities of the proposed methods. It is worth noting that the second FWN achieves high function approximation accuracy and fast convergence.     

Vanishing moment conditions for wavelet atoms in higher dimensions

We provide explicit criteria for wavelets to give rise to frames and atomic decompositions in L²(?^d), but also in more general Banach function spaces. We consider wavelet systems that arise by translating and dilating the mother wavelet, with the dilations taken from a suitable subgroup of GL(?^d), the so-called dilation group.The paper provides a unified approach that is applicable to a wide range of dilation groups, thus giving rise to new atomic decompositions for homogeneous Besov spaces in arbitrary dimensions, but also for other function spaces such as shearlet coorbit spaces. The atomic decomposition results are obtained by applying the coorbit theory developed by Feichtinger and Gröchenig, and they can be informally described as follows: Given a function ψ ∈ L²(?^d) satisfying fairly mild decay, smoothness and vanishing moment conditions, any sufficiently fine sampling of the translations and dilations will give rise to a wavelet frame. Furthermore, the containment of the analyzed signal in certain smoothness spaces (generalizing the homogeneous Besov spaces) can be decided by looking at the frame coefficients, and convergence of the frame expansion holds in the norms of these spaces. We motivate these results by discussing nonlinear approximation.     

On Approximation with Spline Generated Framelets

We characterize the approximation spaces associated with the best n-term approximation in L_p(R) by elements from a tight wavelet frame associated with a spline scaling function. The approximation spaces are shown to be interpolation spaces between L_p and classical Besov spaces, and the result coincides with the result for nonlinear approximation with an orthonormal wavelet with the same smoothness as the spline scaling function. We also show that, under certain conditions, the Besov smoothness can be measured in terms of the sparsity of expansions in the wavelet frame, just like the nonredundant wavelet case. However, the characterization now holds even for wavelet frame systems that do not have the usually required number of vanishing moments, e.g., for systems built through the Unitary Extension Principle, which can have no more than one vanishing moment. Using these results, we describe a fast algorithm that takes as input any function and provides a near sparsest expansion of it in the framelet system as well as approximants that reach the optimal rate of nonlinear approximation. Together with the existence of a fast algorithm, the absence of the need for vanishing moments may have an important qualitative impact for applications to signal compression, as high vanishing moments usually introduce a Gibbs-type phenomenon (or ringing artifacts)in the approximants.     

Democracy functions and optimal embeddings for approximation spaces

We prove optimal embeddings for nonlinear approximation spaces $\mathcal{A}^{\alpha}_q$ , in terms of weighted Lorentz sequence spaces, with the weights depending on the democracy functions of the basis. As applications we recover known embeddings for N-term wavelet approximation in L ^p , Orlicz, and Lorentz norms. We also study the ??greedy classes?? ${\mathcal{G}_{q}^{\alpha}}$ introduced by Gribonval and Nielsen, obtaining new counterexamples which show that ${\mathcal{G}_{q}^{\alpha}}\not=\mathcal{A}^{\alpha}_q$ for most non-democratic unconditional bases.     

Uncertainty investigations in nonlinear aeroelastic systems

In this paper, the stochastic collocation method (SCM) is applied to investigate the nonlinear behavior of an aeroelastic system with uncertainties in the system parameter and the initial condition. Numerical case studies for problems with uncertainties are carried out. In particular, the performance of the SCM is compared with solutions based on other computational techniques such as Monte Carlo simulation, Wiener chaos expansion and wavelet chaos expansion. From the computational results, we conclude that the SCM is an effective tool to study a nonlinear aeroelastic system with random parameters.     

A combination between the reduced basis method and the ANOVA expansion: On the computation of sensitivity indices

We consider a method to efficiently evaluate in a real-time context an output based on the numerical solution of a partial differential equation depending on a large number of parameters. We state a result allowing to improve the computational performance of a three-step RB–ANOVA–RB method. This is a combination of the reduced basis (RB) method and the analysis of variations (ANOVA) expansion, aiming at compressing the parameter space without affecting the accuracy of the output. The idea of this method is to compute a first (coarse) RB approximation of the output of interest involving all the parameter components, but with a large tolerance on the a posteriori error estimate; then, we evaluate the ANOVA expansion of the output and freeze the least important parameter components; finally, considering a restricted model involving just the retained parameter components, we compute a second (fine) RB approximation with a smaller tolerance on the a posteriori error estimate. The fine RB approximation entails lower computational costs than the coarse one, because of the reduction of parameter dimensionality. Our result provides a criterion to avoid the computation of those terms in the ANOVA expansion that are related to the interaction between parameters in the bilinear form, thus making the RB–ANOVA–RB procedure computationally more feasible.     

Nonlinear Methods of Approximation

Abstract. Our main interest in this paper is nonlinear approximation. The basic idea behind nonlinear approximation is that the elements used in the approximation do not come from a fixed linear space but are allowed to depend on the function being approximated. While the scope of this paper is mostly theoretical, we should note that this form of approximation appears in many numerical applications such as adaptive PDE solvers, compression of images and signals, statistical classification, and so on. The standard problem in this regard is the problem of m -term approximation where one fixes a basis and looks to approximate a target function by a linear combination of m terms of the basis. When the basis is a wavelet basis or a basis of other waveforms, then this type of approximation is the starting point for compression algorithms. We are interested in the quantitative aspects of this type of approximation. Namely, we want to understand the properties (usually smoothness) of the function which govern its rate of approximation in some given norm (or metric). We are also interested in stable algorithms for finding good or near best approximations using m terms. Some of our earlier work has introduced and analyzed such algorithms. More recently, there has emerged another more complicated form of nonlinear approximation which we call highly nonlinear approximation. It takes many forms but has the basic ingredient that a basis is replaced by a larger system of functions that is usually redundant. Some types of approximation that fall into this general category are mathematical frames, adaptive pursuit (or greedy algorithms), and adaptive basis selection. Redundancy on the one hand offers much promise for greater efficiency in terms of approximation rate, but on the other hand gives rise to highly nontrivial theoretical and practical problems. With this motivation, our recent work and the current activity focuses on nonlinear approximation both in the classical form of m -term approximation (where several important problems remain unsolved) and in the form of highly nonlinear approximation where a theory is only now emerging.     

Nonlinear approximation schemes associated with nonseparable wavelet bi-frames

In the present paper, we study nonlinear approximation properties of multivariate wavelet bi-frames. For a certain range of parameters, the approximation classes associated with best N-term approximation are determined to be Besov spaces and thresholding the wavelet bi-frame expansion realizes the approximation rate. Our findings extend results about dyadic wavelets to more general scalings. Finally, we verify that the required linear independence assumption is satisfied for particular families of nondyadic wavelet bi-frames in arbitrary dimensions.     

Polynomial approximations of a class of stochastic multiscale elasticity problems

We consider a class of elasticity equations in \({\mathbb{R}^d}\) whose elastic moduli depend on n separated microscopic scales. The moduli are random and expressed as a linear expansion of a countable sequence of random variables which are independently and identically uniformly distributed in a compact interval. The multiscale Hellinger–Reissner mixed problem that allows for computing the stress directly and the multiscale mixed problem with a penalty term for nearly incompressible isotropic materials are considered. The stochastic problems are studied via deterministic problems that depend on a countable number of real parameters which represent the probabilistic law of the stochastic equations. We study the multiscale homogenized problems that contain all the macroscopic and microscopic information. The solutions of these multiscale homogenized problems are written as generalized polynomial chaos (gpc) expansions. We approximate these solutions by semidiscrete Galerkin approximating problems that project into the spaces of functions with only a finite number of N gpc modes. Assuming summability properties for the coefficients of the elastic moduli’s expansion, we deduce bounds and summability properties for the solutions’ gpc expansion coefficients. These bounds imply explicit rates of convergence in terms of N when the gpc modes used for the Galerkin approximation are chosen to correspond to the best N terms in the gpc expansion. For the mixed problem with a penalty term for nearly incompressible materials, we show that the rate of convergence for the best N term approximation is independent of the Lamé constants’ ratio when it goes to \({\infty}\). Correctors for the homogenization problem are deduced. From these we establish correctors for the solutions of the parametric multiscale problems in terms of the semidiscrete Galerkin approximations. For two-scale problems, an explicit homogenization error which is uniform with respect to the parameters is deduced. Together with the best N term approximation error, it provides an explicit convergence rate for the correctors of the parametric multiscale problems. For nearly incompressible materials, we obtain a homogenization error that is independent of the ratio of the Lamé constants, so that the error for the corrector is also independent of this ratio.     

Weak Convergence of Cardaliaguet-Euvrard Neural Network Operators Studied Asymptotically

An Nth order asymptotic expansion is established for the error of weak approximation of a special class of functions by the well-known Cardaliaguet-Euvrard neural network operators. This class is made out of functions f that are N times continuously differentiable over R, so that all f,f′,…, f ^(N) have the same compact support and f ^(N) is of bounded variation. This asymptotic expansion involves products of integrals of the network activation bell-shaped function b and f. The rate of the above convergence depends only on the first derivative of involved functions.     

Locally adaptive fitting of semiparametric models to nonstationary time series

We fit a class of semiparametric models to a nonstationary process. This class is parametrized by a mean function μ(·) and a p-dimensional function θ(·)=(θ⁽¹⁾(·),…,θ^(p)(·))′ that parametrizes the time-varying spectral density f_θ(·)(λ). Whereas the mean function is estimated by a usual kernel estimator, each component of θ(·) is estimated by a nonlinear wavelet method. According to a truncated wavelet series expansion of θ⁽ⁱ⁾(·), we define empirical versions of the corresponding wavelet coefficients by minimizing an empirical version of the Kullback–Leibler distance. In the main smoothing step, we perform nonlinear thresholding on these coefficients, which finally provides a locally adaptive estimator of θ⁽ⁱ⁾(·). This method is fully automatic and adapts to different smoothness classes. It is shown that usual rates of convergence in Besov smoothness classes are attained up to a logarithmic factor.     

On the block thresholding wavelet estimators with censored data

We consider block thresholding wavelet-based density estimators with randomly right-censored data and investigate their asymptotic convergence rates. Unlike for the complete data case, the empirical wavelet coefficients are constructed through the Kaplan-Meier estimators of the distribution functions in the censored data case. On the basis of a result of Stute [W. Stute, The central limit theorem under random censorship, Ann. Statist. 23 (1995) 422-439] that approximates the Kaplan-Meier integrals as averages of i.i.d. random variables with a certain rate in probability, we can show that these wavelet empirical coefficients can be approximated by averages of i.i.d. random variables with a certain error rate in L². Therefore we can show that these estimators, based on block thresholding of empirical wavelet coefficients, achieve optimal convergence rates over a large range of Besov function classes , p≥2, q≥1 and nearly optimal convergence rates when 1≤p<2. We also show that these estimators achieve optimal convergence rates over a large class of functions that involve many irregularities of a wide variety of types, including chirp and Doppler functions, and jump discontinuities. Therefore, in the presence of random censoring, wavelet estimators still provide extensive adaptivity to many irregularities of large function classes. The performance of the estimators is tested via a modest simulation study.     

A survey of published programs for best approximation

We list and discuss published programs for best approximation of functions by linear and nonlinear families in all standard forms.In this note we list and discuss the published programs for obtaining best approximations. Let X be a set on which we wish to approximate. Most sets will be finite (an equivalent terms is discrete). Let 6 6 be a norm on the continuous functions on X. Let G be a familiy of continuous functions on X. For a given basis {φ₁…,φ_n}, the linear family G is the set of all functions of the form

$\text{L(A,x)=}\text{∑}\text{k=1}\text{n}\text{a}{}_{\mathrm{k}}\text{φ}{}_{\mathrm{k}}\text{(x)}$

The problem of best approximation is given a continuous function f, to find g¹ to minimize e(g) = ∥f-g∥ over g?G. Such g¹ is called a best approximation to f.Discrete linear approximation problems are sometimes formulated as solution of an overdetermined system of linear equations Ax = b with respect to a norm where a_ij = φ_j(x_i) and b_i = f(x)_i).