Best Basis Selection for Approximation in L p

We study the approximation of a function class F in L _p by choosing first a basis B and then using n -term approximation with the elements of B . Into the competition for best bases we enter all greedy (i.e., democratic and unconditional [20]) bases for L _p . We show that if the function class F is well-oriented with respect to a particular basis B then, in a certain sense, this basis is the best choice for this type of approximation. Our results extend the recent results of Donoho [9] from L ₂ to L _p , p\neq 2 .     

The Thresholding Greedy Algorithm, Greedy Bases, and Duality

Some new conditions that arise naturally in the study of the Thresholding Greedy Algorithm are introduced for bases of Banach spaces. We relate these conditions to best n-term approximation and we study their duality theory. In particular, we obtain a complete duality theory for greedy bases.     

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.     

Entropy,Universal Coding,Approximation, and Bases Properties

We shall present here results concerning the metric entropy of spaces of linear and nonlinear approximation under very general conditions. Our first result computes the metric entropy of the linear and m-terms approximation classes according to a quasi-greedy basis verifying the Temlyakov property. This theorem shows that the second index r is not visible throughout the behavior of the metric entropy. However, metric entropy does discriminate between linear and nonlinear approximation. Our second result extends and refines a result obtained in a Hilbertian framework by Donoho, proving that under orthosymmetry conditions, m-terms approximation classes are characterized by the metric entropy. Since these theorems are given under the general context of quasi-greedy bases verifying the Temlyakov property, they have a large spectrum of applications. For instance, it is proved in the last section that they can be applied in the case of L _p norms for R ^d for 1 < p < \infty. We show that the lower bounds needed for this paper in fact follow from quite simple large deviation inequalities concerning hypergeometric or binomial distributions. To prove the upper bounds, we provide a very simple universal coding based on a thresholding-quantizing constructive procedure.     

Best N Term Approximation Spaces for Tensor Product Wavelet Bases

We consider best N term approximation using anisotropic tensor product wavelet bases ("sparse grids"). We introduce a tensor product structure ⊗_q on certain quasi-Banach spaces. We prove that the approximation spaces A^α_q(L₂) and A^α_q(H¹) equal tensor products of Besov spaces B^α_q(L_q), e.g., A^α_q(L₂([0,1]^d)) = B^α_q(L_q([0,1])) ⊗_q · ⊗_q B^α_{q · ·}(L_q([0,1])). Solutions to elliptic partial differential equations on polygonal/polyhedral domains belong to these new scales of Besov spaces.     

Weighted Best Local Approximation

In this survey, the notion of a balanced best multipoint local approximation is fully exposed since they were treated in the Lpspaces and recent results in Orlicz spaces. The notion of balanced point, which was introduced by Chui et al. in 1984 are extensively used.     

Cp Condition and the Best Local Approximation

In this paper, we introduce a condition weaker than the Lpdifferentiability,which we call Cpcondition. We prove that if a function satisfies this condition at a point, then there exists the best local approximation at that point. We also give a necessary and sufficient condition for that a function be Lpdifferentiable. In addition, we study the convexity of the set of cluster points of the net of best appoximations of f,{Pe( f)} as e → 0.     

Weak Type Inequalities for Best Simultaneous Approximation in Banach Spaces

For arbitrary Banach spaces Butzer and Scherer in 1968 showed that the approximation order of best approximation can characterized by the order of certain K-functionals. This general theorem has many applications such as the characterization of the best approximation of algebraic polynomials by moduli of smoothness involving the Legendre, Chebyshev, or more general the Jacobi transform. In this paper we introduce a family of seminorms on the underlying approximation space which leads to a generalization of the Butzer–Scherer theorems. Now the characterization of the weighted best algebraic approximation in terms of the so-called main part modulus of Ditzian and Totik is included in our frame as another particular application. The goal of the paper is to show that for the characterization of the orders of best approximation, simultaneous approximation (in different spaces), reduction theorems, and K-functionals one has (essentially) only to verify three types of inequalities, namely inequalities of Jackson-, Bernstein-type and an equivalence condition which guarantees the equivalence of the seminorm and the underlying norm on certain subspaces. All the results are given in weak-type estimates for almost arbitrary approximation orders, the proofs use only functional analytic methods.     

"Push-the-Error" Algorithm for Nonlinear n-Term Approximation

This paper is concerned with further developing and refining the analysis of a recent algorithmic paradigm for nonlinear approximation, termed the "Push-the-Error" scheme. It is especially designed to deal with L_∞-approximation in a multilevel framework. The original version is extended considerably to cover all commonly used multiresolution frameworks. The main conceptually new result is the proof of the quasi-semi-additivity of the functional N(ε) counting the number of terms needed to achieve accuracy ε. This allows one to show that the improved scheme captures all rates of best n-term approximation.     

Best Local Approximation in Orlicz Spaces

We get results in Orlicz spaces L ^φ about best local approximation on non-balanced neighborhoods when φ satisfies a certain asymptotic condition. This fact generalizes known previous results in L ^p spaces.     

Best Approximation in Numerical Radius

Let X be a reflexive Banach space. In this article, we give a necessary and sufficient condition for an operator T ∈ 𝒦(X) to have the best approximation in numerical radius from the convex subset 𝒰 ? 𝒦(X), where 𝒦(X) denotes the set of all linear, compact operators from X into X. We also present an application to minimal extensions with respect to the numerical radius. In particular, some results on best approximation in norm are generalized to the case of the numerical radius.     

赋Amemiya-Orlicz范数的Musielak-Orlicz-Sobolev空间单调性在最佳逼近中的应用

利用Musielak-Orlicz-Sobolev空间的构成特点,借鉴Orlicz-Sobolev空间的单调性在最佳逼近中的一些应用,以Orlicz空间中Jensen'S不等式的推广为主要工具,讨论了赋Amemiya-Orlicz范数的Musielak-Orlicz-Sobolev空间中的最佳逼近问题,主要是唯一性、存在性、稳定性.     

Extended Best Polynomial Approximation Operator in Orlicz Spaces

In this article we consider the best polynomial approximation operator, defined in an Orlicz space L ^Φ(B), and its extension to L ^?(B) where ? is the derivative function of Φ. A characterization of these operators and several properties are obtained.     

Approximation characteristics for diagonal operators in different computational settings

First we study several extremal problems on minimax, and prove that they are equivalent. Then we connect this result with the exact values of some approximation characteristics of diagonal operators in different settings, such as the best n-term approximation, the linear average and stochastic n-widths, and the Kolmogorov and linear n-widths. Most of these exact values were known before, but in terms of equivalence of these extremal problems, we present a unified approach to give them a direct proof.     

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.     

Besov类上的贪婪算法

我们讨论了Besov类MBpr,θ上的相应于张量积小波词典Wd的最佳m-项 逼近问题,证明了其最佳m-项逼近的阶可以通过简单的贪婪算法得到.     

单纯形上的Stancu多项式与最佳多项式逼近

作为Bernstein多项式的推广,本文定义单纯形上的多元Stancu多项式.以最佳多项式逼近为度量,建立Stancu多项式对连续函数的逼近定理与逼近阶估计,给出Stancu多项式的一个逼近逆定理,从而用最佳多项式逼近刻划Stancu多项式的逼近特征.     

Reliability Approximation for Markov Chain Imbeddable Systems

In the present article, a simple method is developed for approximating the reliability of Markov chain imbeddable systems. The approximating formula reduces the problem to the reliability assessment of smaller systems with structure similar to the original systems. Two specific reliability structures which have attracted considerable research interest recently (r-within-consecutive-k-out-of-n system and two dimensional r-within-k₁ × k₂-out-of-n₁ × n₂ system) are studied by the new approach and numerical calculations are carried out, which reveal the high quality of our approximations. Several possible extensions and generalizations are also presented in brief.     

Toward Best Approximation of Nonlinear Systems: A Case of Models with Memory

The problem of nonlinear dynamical system modeling, considered in this paper, is motivated by restrictions arising in real-world tasks. The restrictions are that first, a system input cannot be entirely observed for one trial. Second, the system model must be subjected to the causality principle. Third, the input is corrupted by noise so that no relationship between the reference input and noise is known. Fourth, the model should have some degrees of freedom so that the associated accuracy can be regulated by a variation of these freedom degrees. We propose and justify new procedures for the nonlinear system modeling that are initialized by these motivations. The models are nonlinear and given by so called r-degree operators that can be reduced to a matrix form presentation. To satisfy the restrictions above, the matrices have special structures that we call the lower p-band matrices. The degree r of the models is the required degree of freedom. The rigorous analysis of errors associated with the presented techniques is given. Numerical experiments with real data demonstrate the efficiency of the proposed approach.