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.     

Greedy algorithms and bestm-term approximation with respect to biorthogonal systems

The article extends upon previous work by Temlyakov, Konyagin, and Wojtaszczyk on comparing the error of certain greedy algorithms with that of best m-term approximation with respect to a general biorthogonal system in a Banach space X. We consider both necessary and sufficient conditions which cover most of the special cases previously considered. Some new results concerning the Haar system in L₁, L_∞, and BMO are also included.     

On Multivariate Adaptive Approximation

Recently, A. Cohen, R. A. DeVore, P. Petrushev, and H. Xu investigated nonlinear approximation in the space BV (R ² ). They modified the classical adaptive algorithm to solve related extremal problems. In this paper, we further study the modified adaptive approximation and obtain results on some extremal problems related to the spaces V _σ,p ^r (R ^d ) of functions of ``Bounded Variation" and Besov spaces B ^α (R ^d ). November 23, 1998. Date revised: June 25, 1999. Date accepted: September 13, 1999.     

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.     

On the Degree of Approximation by Manifolds of Finite Pseudo-Dimension

The pseudo-dimension of a real-valued function class is an extension of the VC dimension for set-indicator function classes. A class of finite pseudo-dimension possesses a useful statistical smoothness property. In [10] we introduced a nonlinear approximation width = which measures the worst-case approximation error over all functions by the best manifold of pseudo-dimension n . In this paper we obtain tight upper and lower bounds on ρ _n (W ^r,d _p , L _q ) , both being a constant factor of n ^-r/d , for a Sobolev class W ^r,d _p , . As this is also the estimate of the classical Alexandrov nonlinear n -width, our result proves that approximation of W ^r,d _p by the family of manifolds of pseudo-dimension n is as powerful as approximation by the family of all nonlinear manifolds with continuous selection operators. March 12, 1997. Dates revised: August 26, 1997, October 24, 1997, March 16, 1998, June 15, 1998. Date accepted: June 25, 1998.     

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.     

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.     

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.     

Note on the Approximation of Powers of the Distance in Two-Dimensional Domains

Although Newman's trick has been mainly applied to the approximation of univariate functions, it is also appropriate for the approximation of multivariate functions that are encountered in connection with Green's functions for elliptic differential equations. The asymptotics of the real-valued function on a ball in 2-space coincides with that for an approximation problem in the complex plane. The note contains an open problem. May 17, 1999. Date revised: October 20, 1999. Date accepted: March 17, 2000.     

Piecewise Monotone Pointwise Approximation

Let r, k, s be three integers such that , or We prove the following: Proposition. Let Y:={y _i } _i=1 ^s be a fixed collection of distinct points y _i ∈ (-1,1) and Π (x):= (x-y ₁ ). ... .(x-y _s ). Let I:=[-1,1]. If f ∈ C ^(r) (I) and f'(x)Π(x) ≥ 0, x ∈ I, then for each integer n ≥ k+r-1 there is an algebraic polynomial P _n =P _n (x) of degree ≤ n such that P _n '(x) Π (x) ≥ 0 and $$ \vert f(x)-P_n(x) \vert \le B\left(\frac{1}{n^2}+\frac{1}{n}\sqrt{1-x^2}\right)^r \omega_k \left(f^{(r)};\frac{1}{n^2}+\frac{1}{n}\sqrt{1-x^2}\right) \legno{(1)}$$ for all x∈ I, where ω _k (f ^(r) ;t) is the modulus of smoothness of the k -th order of the function f ^(r) and B is a constant depending only on r , k , and Y. If s=1, the constant B does not depend on Y except in the case (r=1, k=3). In addition it is shown that (1) does not hold for r=1, k>3. March 20, 1995. Dates revised: March 11, 1996; December 20, 1996; and August 7, 1997.     

Interpolatory Pointwise Estimates for Polynomial Approximation

We discuss whether or not it is possible to have interpolatory pointwise estimates in the approximation of a function f∈ C[0,1] , by polynomials. For the sake of completeness, as well as in order to strengthen some existing results, we discuss briefly the situation in unconstrained approximation. Then we deal with positive and monotone constraints where we show exactly when such interpolatory estimates are achievable by proving affirmative results and by providing the necessary counterexamples in all other cases. November 16, 1998. Date revised: July 12, 1999. Date accepted: September 13, 1999.     

More on Comonotone Polynomial Approximation

The main achievement of this paper is that we show, what was to us, a surprising conclusion, namely, twice continuously differentiable functions in (0,1) (with some regular behavior at the endpoints) which change monotonicity at least once in the interval, are approximable better by comonotone polynomials, than are such functions that are merely monotone. We obtain Jackson-type estimates for the comonotone polynomial approximation of such functions that are impossible to achieve for monotone approximation. July 7, 1998. Date revised: May 5, 1999. Date accepted: July 23, 1999.     

Interpolation by Polynomials and Radial Basis Functions on Spheres

The paper obtains error estimates for approximation by radial basis functions on the sphere. The approximations are generated by interpolation at scattered points on the sphere. The estimate is given in terms of the appropriate power of the fill distance for the interpolation points, in a similar manner to the estimates for interpolation in Euclidean space. A fundamental ingredient of our work is an estimate for the Lebesgue constant associated with certain interpolation processes by spherical harmonics. These interpolation processes take place in ``spherical caps' whose size is controlled by the fill distance, and the important aim is to keep the relevant Lebesgue constant bounded. This result seems to us to be of independent interest. March 27, 1997. Dates revised: March 19, 1998; August 5, 1999. Date accepted: December 15, 1999.     

Uniqueness of Markov-Extremal Polynomials on Symmetric Convex Bodies

For a compact set K\subset R ^d with nonempty interior, the Markov constants M _n (K) can be defined as the maximal possible absolute value attained on K by the gradient vector of an n -degree polynomial p with maximum norm 1 on K . It is known that for convex, symmetric bodies M _n (K) = n ² /r(K) , where r(K) is the ``half-width' (i.e., the radius of the maximal inscribed ball) of the body K . We study extremal polynomials of this Markov inequality, and show that they are essentially unique if and only if K has a certain geometric property, called flatness. For example, for the unit ball B ^d (\smallbf 0, 1) we do not have uniqueness, while for the unit cube [-1,1] ^d the extremal polynomials are essentially unique. September 9, 1999. Date revised: September 28, 2000. Date accepted: November 14, 2000.     

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.     

Stabilization of Infinite-Dimensional Semilinear Systems with Dissipative Drift

In this paper we study feedback stabilization for distributed semilinear control systems . Here, A is the infinitesimal generator of a linear C ₀ -semigroup of contractions on a real Hilbert space H and is a nonlinear operator on H into itself. A sufficient ad-condition is provided for strong feedback stabilization. The result is illustrated by means of partial differential systems. Accepted 31 July 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.     

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.     

Bounds on Projections onto Bivariate Polynomial Spline Spaces with Stable Local Bases

L _& ∞ bounds for norms of projections onto bivariate polynomial spline spaces on regular triangulations with stable local bases are established. The general results are then applied to obtain error bounds for best L ₂ - and l ₂ -approximation by splines on quasi-uniform triangulations. March 8, 2000. Date revised: November 20, 2000. Date accepted: July 9, 2001.