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.     

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.     

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.     

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.     

On Approximation by Ridge Functions

Ridge functions are defined as functions of the form , where , belongs to the given ``direction' set . In this paper we study the fundamentality of ridge functions for variable directions sets A and discuss the rate of approximation by ridge functions. Date received: June 7, 1994. Date revised: August 3, 1995.     

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.     

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.     

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.     

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.     

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.     

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.     

Best Approximation with Walsh Atoms

We consider the approximation in L ² R of a given function using finite linear combinations of Walsh atoms, which are Walsh functions localized to dyadic intervals, also called Haar—Walsh wavelet packets. It is shown that up to a constant factor, a linear combination of K atoms can be represented to relative error ɛ by a linear combination of orthogonal atoms. In finite dimension N, best approximation with K orthogonal atoms can be realized with an algorithm of order . A faster algorithm of order solves the problem with indirect control over K. Therefore the above result connects algorithmic and theoretical best approximation. Date received: July 6, 1995. Date revised: January 8, 1996.     

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.     

Approximation order provided by refinable function vectors

In this paper we considerL _p-approximation by integer translates of a finite set of functionsϕ _v (v=0, ...,r − 1) which are not necessarily compactly supported, but have a suitable decay rate. Assuming that the function vectorϕ=(ϕ ^=0/ r−1 is refinable, necessary and sufficient conditions for the refinement mask are derived. In particular, if algebraic polynomials can be exactly reproduced by integer translates ofϕ _v, then a factorization of the refinement mask ofϕ can be given. This result is a natural generalization of the result for a single functionϕ, where the refinement mask ofϕ contains the factor ((1 +e ^−iu )/2) ^m if approximation orderm is achieved. Dedicated to Professor L. Berg on the occasion of his 65th birthday     

Shape-Preserving Widths of Weighted Sobolev-Type Classes of Positive, Monotone, and Convex Functions on a Finite Interval

   Abstract. Let I be a finite interval, r∈ N and ρ(t)= dist {t, I} , t∈ I . Denote by Δ ^s ₊ L _q the subset of all functions y∈ L _q such that the s -difference Δ ^s _τ y(t) is nonnegative on I ,

Weighted Polynomial Approximation for Convex External Fields

It is proven that if Q is convex and w(x)= exp(-Q(x)) is the corresponding weight, then every continuous function that vanishes outside the support of the extremal measure associated with w can be uniformly approximated by weighted polynomials of the form w ⁿ P _n . This solves a problem of P. Borwein and E. B. Saff. Actually, a similar result is true locally for any parts of the extremal support where Q is convex. February 10, 1998. Date revised: July 23, 1998. Date accepted: August 17, 1998.     

Polynomial Approximation on Convex Subsets of R n

Let K be a closed bounded convex subset of R ⁿ ; then by a result of the first author, which extends a classical theorem of Whitney there is a constant w _m (K) so that for every continuous function f on K there is a polynomial ϕ of degree at most m-1 so that |f(x)-ϕ(x)|≤ w_m(K) sup _{x,x+mh∈ K} |Δ_h^m(f;x)|. The aim of this paper is to study the constant w _m (K) in terms of the dimension n and the geometry of K . For example, we show that w ₂ (K)≤ (1/2) [ log ₂ n]+5/4 and that for suitable K this bound is almost attained. We place special emphasis on the case when K is symmetric and so can be identified as the unit ball of finite-dimensional Banach space; then there are connections between the behavior of w _m (K) and the geometry (particularly the Rademacher type) of the underlying Banach space. It is shown, for example, that if K is an ellipsoid then w ₂ (K) is bounded, independent of dimension, and w ₃ (K)\sim log n . We also give estimates for w ₂ and w ₃ for the unit ball of the spaces l _p ⁿ where 1≤ p≤∈fty. September 24, 1997. Dates revised: January 18, 1999 and June 10, 1999. Date accepted: June 25, 1999.     

Greedy Algorithms with Regard to Multivariate Systems with Special Structure

The question of finding an optimal dictionary for nonlinear m -term approximation is studied in this paper. We consider this problem in the periodic multivariate (d variables) case for classes of functions with mixed smoothness. We prove that the well-known dictionary U ^d which consists of trigonometric polynomials (shifts of the Dirichlet kernels) is nearly optimal among orthonormal dictionaries. Next, it is established that for these classes near-best m -term approximation, with regard to U ^d , can be achieved by simple greedy-type (thresholding-type) algorithms. The univariate dictionary U is used to construct a dictionary which is optimal among dictionaries with the tensor product structure. June 22, 1998. Date revised: March 26, 1999. Date accepted: March 22, 1999.     

On Rational Interpolation to |x|

We consider Newman-type rational interpolation to |x| induced by arbitrary sets of interpolation nodes, and we show that under mild restrictions on the location of the interpolation nodes, the corresponding sequence of rational interpolants converges to |x|. Date received: August 18, 1995. Date revised: January 10, 1996.     

Constrained Approximation in Banach Spaces

   Abstract. We consider the problem of approximating vectors from a complemented subspace Z ₊ of a Banach space X by the projections onto Z ₊ of vectors from a subspace Y ₊ with a norm constraint on their projections onto the complementary subspace. Sufficient conditions are found for the existence of a unique best approximant and a characterization via a critical point equation is provided, thus extending known results on Hilbert spaces. These results are then applied in the case that X is L ^p (T), where T denotes the unit circle, Z ₊ consists of functions supported on a subset of the circle, and Y ₊ is the corresponding Hardy space.