Adaptive frame methods for nonlinear variational problems

In this paper we develop adaptive numerical solvers for certain nonlinear variational problems. The discretization of the variational problems is done by a suitable frame decomposition of the solution, i.e., a complete, stable, and redundant expansion. The discretization yields an equivalent nonlinear problem on the space of frame coefficients. The discrete problem is then adaptively solved using approximated nested fixed point and Richardson type iterations. We investigate the convergence, stability, and optimal complexity of the scheme. A theoretical advantage, for example, with respect to adaptive finite element schemes is that convergence and complexity results for the latter are usually hard to prove. The use of frames is further motivated by their redundancy, which, at least numerically, has been shown to improve the conditioning of the discretization matrices. Also frames are usually easier to construct than Riesz bases. We present a construction of divergence-free wavelet frames suitable for applications in fluid dynamics and magnetohydrodynamics. M. Fornasier acknowledges the financial support provided through the Intra-European Individual Marie Curie Fellowship Programme, under contract MOIF-CT-2006-039438. All of the authors acknowledge the hospitality of Dipartimento di Metodi e Modelli Matematici per le Scienze Applicate, Università di Roma “La Sapienza”, Italy, during the early preparation of this work. The authors want to thank Daniele Boffi, Dorina Mitrea, and Karsten Urban for the helpful and fruitful discussions on divergence-free function spaces.     

Adaptive Mollifiers for High Resolution Recovery of Piecewise Smooth Data from its Spectral Information

We discuss the reconstruction of piecewise smooth data from its (pseudo-) spectral information. Spectral projections enjoy superior resolution provided the data is globally smooth, while the presence of jump discontinuities is responsible for spurious O (1) Gibbs oscillations in the neighborhood of edges and an overall deterioration of the unacceptable first-order convergence in rate. The purpose is to regain the superior accuracy in the piecewise smooth case, and this is achieved by mollification. Here we utilize a modified version of the two-parameter family of spectral mollifiers introduced by Gottlieb and Tadmor [GoTa85]. The ubiquitous one-parameter, finite-order mollifiers are based on dilation . In contrast, our mollifiers achieve their high resolution by an intricate process of high-order cancellation . To this end, we first implement a localization step using an edge detection procedure [GeTa00a, b]. The accurate recovery of piecewise smooth data is then carried out in the direction of smoothness away from the edges, and adaptivity is responsible for the high resolution. The resulting adaptive mollifier greatly accelerates the convergence rate, recovering piecewise analytic data within exponential accuracy while removing the spurious oscillations that remained in [GoTa85]. Thus, these adaptive mollifiers offer a robust, general-purpose ``black box' procedure for accurate post-processing of piecewise smooth data. March 29, 2001. Final version received: August 31, 2001.     

Approximation by boolean sums of positive linear operators III: Estimates for some numerical approximation schemes

In the present note we intröduce and investigate certain sequences of discrete positive linear operators and Boolean sum modifications of them. The mappings considered are obtained by discretizing a class of transformed convolution-type operators using Gaussian quadrature of appropriate order. For our operators and their modifications we prove pointwise Jackson-type theorems involving the first and second order moduli of smoothness, thus providing new and elegant proofs of earlier results by Timan, Telyakowskii, Gopengauz and DeVore. Due to their discrete structure, optimal order of approximation and ease of computation, the operators appear to be useful for numerical approximation. In an intermediate step we solve an old problem in Approximation Theory; its importance was only recently emphasized in a paper of Butzer.     

Exponentials Reproducing Subdivision Schemes

This paper is concerned with a family of nonstationary, interpolatory subdivision schemes that have the capability of reproducing functions in a finite-dimensional subspace of exponential polynomials. We give conditions for the existence and uniqueness of such schemes, and analyze their convergence and smoothness. It is shown that the refinement rules of an even-order exponentials reproducing scheme converge to the Dubuc—Deslauriers interpolatory scheme of the same order, and that both schemes have the same smoothness. Unlike the stationary case, the application of a nonstationary scheme requires the computation of a different rule for each refinement level. We show that the rules of an exponentials reproducing scheme can be efficiently derived by means of an auxiliary orthogonal scheme , using only linear operations. The orthogonal schemes are also very useful tools in fitting an appropriate space of exponential polynomials to a given data sequence.     

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.     

Representation theorems for Banach algebras

For a space X   denote by _Cb(X)$C_b(X)$ the Banach algebra of all continuous bounded scalar-valued functions on X   and denote by _C0(X)$C_0(X)$ the set of all elements in _Cb(X)$C_b(X)$ which vanish at infinity.     

On the Power of Standard Information for Weighted Approximation

We study weighted approximation of multivariate functions for classes of standard and linear information in the worst case and average case settings. Under natural assumptions, we show a relation between n th minimal errors for these two classes of information. This relation enables us to infer convergence and error bounds for standard information, as well as the equivalence of tractability and strong tractability for the two classes. April 11, 2001. Final version received: May 29, 2001.     

Approximation Orders of FSI Spaces in L 2 (R d )

A second look at the authors' [BDR1], [BDR2] characterization of the approximation order of a Finitely generated Shift-Invariant subspace S(Φ) of L ₂ (R ^d ) results in a more explicit formulation entirely in terms of the (Fourier transform of the) generators of the subspace. Further, when the generators satisfy a certain technical condition, then, under the mild assumption that the set of 1-periodizations of the generators is linearly independent, such a space is shown to provide approximation order k if and only if contains a ψ (necessarily unique) satisfying . The technical condition is satisfied, e.g., when the generators are at infinity for some ρ>k+d . In the case of compactly supported generators, this recovers an earlier result of Jia [J1], [J2]. March 19. 1996. Date revised: September 6, 1996.     

Approximation Orders of FSI Spaces in L 2 (R d )

A second look at the authors' [BDR1], [BDR2] characterization of the approximation order of a Finitely generated Shift-Invariant (FSI) subspace of L ₂(R ^d ) results in a more explicit formulation entirely in terms of the (Fourier transform of the) generators of the subspace. Further, when the generators satisfy a certain technical condition, then, under the mild assumption that the set of 1-periodizations of the generators is linearly independent, such a space is shown to provide approximation order k if and only if contains a (necessarily unique) satisfying for |j|<k , . The technical condition is satisfied, e.g., when the generators are at infinity for some >k+d. In the case of compactly supported generators, this recovers an earlier result of Jia [J1], [J2]. March 19, 1996. Dates revised: September 6, 1996, March 4, 1997.     

An update on orthogonal polynomials and weighted approximation on the real line

We briefly review the state of orthogonal polynomials on (–, ), concentrating on analytic aspects, such as asymptotics and bounds on orthogonal polynomials, their zeros and their recurrence coefficients. We emphasize results rather than proofs. We also discuss applications to mean convergence of orthogonal expansions, Lagrange interpolation, Jackson-Bernstein theorems and the weighted incomplete polynomial approximation problem.     

Linear problems (with extended range) have linear optimal algorithms

LetF ₁ andF ₂ be normed linear spaces andS:F ₀ F ₂ a linear operator on a balanced subsetF ₀ ofF ₁. IfN denotes a finite dimensional linear information operator onF ₀, it is known that there need not be alinear algorithm:N(F ₄) F ₂ which is optimal in the sense that (N(f)) –S(f is minimized. We show that the linear problem defined byS andN can be regarded as having a linear optimal algorithm if we allow the range of to be extended in a natural way. The result depends upon imbeddingF ₂ isometrically in the space of continuous functions on a compact Hausdorff spaceX. This is done by making use of a consequence of the classical Banach-Alaoglu theorem.     

On best error bounds for approximation by piecewise polynomial functions

Summary An analog of the well-known Jackson-Bernstein-Zygmund theory on best approximation by trigonometric polynomials is developed for approximation methods which use piecewise polynomial functions. Interpolation and best approximation by polynomial splines, Hermite and finite element functions are examples of such methods. A direct theorem is proven for methods which are stable, quasi-linear and optimally accurate for sufficiently smooth functions. These assumptions are known to be satisfied in many cases of practical interest. Under a certain additional assumption, on the family of meshes, an inverse theorem is proven which shows that the direct theorem is sharp.The work presented in this paper was supported by the ERDA Mathematics and Computing Laboratory, Courant Institute of Mathematical Sciences, New York University, under Contract E(11-1)-3077 with the Energy Research and Development Administration.     

Approximation of the Hausdorff distance by the distance of continuous surjections

The aim of this paper is to answer the following question: let (X,?) and (Y,d) be metric spaces, let A,B⊂Y be continuous images of the space X and let be a fixed continuous surjection. When is the inequality

     

On the convergence of von Neumann''s alternating projection algorithm for two sets

We give several unifying results, interpretations, and examples regarding the convergence of the von Neumann alternating projection algorithm for two arbitrary closed convex nonempty subsets of a Hilbert space. Our research is formulated within the framework of Fejér monotonicity, convex and set-valued analysis. We also discuss the case of finitely many sets.     

A monotone iterative technique for stationary and time dependent problems in Banach spaces

An abstract monotone iterative method is developed for operators between partially ordered Banach spaces for the nonlinear problem Lu=Nu and the nonlinear time dependent problem u^′=(L+N)u. Under appropriate assumptions on L and N we obtain maximal and minimal solutions as limits of monotone sequences of solutions of linear problems. The results are illustrated by means of concrete examples.     

Greedy Algorithm and m -Term Trigonometric Approximation

We study the following nonlinear method of approximation by trigonometric polynomials in this paper. For a periodic function f we take as an approximant a trigonometric polynomial of the form , where is a set of cardinality m containing the indices of the m biggest (in absolute value) Fourier coefficients of function f . We compare the efficiency of this method with the best m -term trigonometric approximation both for individual functions and for some function classes. It turns out that the operator G _m provides the optimal (in the sense of order) error of m -term trigonometric approximation in the L _p -norm for many classes. September 23, 1996. Date revised: February 3, 1997.     

Spectral theory for perturbed Krein Laplacians in nonsmooth domains

We study spectral properties for HK,Ω, the Krein-von Neumann extension of the perturbed Laplacian −Δ+V defined on , where V is measurable, bounded and nonnegative, in a bounded open set Ω⊂Rn belonging to a class of nonsmooth domains which contains all convex domains, along with all domains of class C1,r, r>1/2. In particular, in the aforementioned context we establish the Weyl asymptotic formula

     

On the Best Approximation by Ridge Functions in the Uniform Norm

We consider the best approximation of some function classes by the manifold M _n consisting of sums of n arbitrary ridge functions. It is proved that the deviation of the Sobolev class W _p ^r,d from the manifold M _n in the space L _q for any 2≤ q≤ p≤∈fty behaves asymptotically as n ^-r/(d-1) . In particular, we obtain this asymptotic estimate for the uniform norm p=q=∈fty . January 10, 2000. Date revised: March 1, 2001. Date accepted: March 12, 2001.     

A constructive method related to generalizations of the uniform boundedness principle and its applications

The present paper suggests a general constructive method, which improves and generalizes a result of Dickmeis, Nessel, and van Wickeren. In Section 3, three applications will be discussed.     

Nonlinear Approximation with Local Fourier Bases

It is shown that local Fourier bases are unconditional bases for the modulation spaces on R, including the Bessel potential spaces and the Segal algebra S ₀ . As a consequence, the abstract function spaces, that are defined by the approximation properties with respect to a local Fourier basis, are precisely the modulation space s. April 22, 1998. Date accepted: May 18, 1999.