Convergence of Some Greedy Algorithms in Banach Spaces

We consider some theoretical greedy algorithms for approximation in Banach spaces with respect to a general dictionary. We prove convergence of the algorithms for Banach spaces which satisfy certain smoothness assumptions. We compare the algorithms and their rates of convergence when the Banach space is L_p(\mathbbT^d)L_p(\mathbb{T}^d) ($1相似文献   

On the construction of bodies of constant width containing a given set

We discuss the problem of sparse representation of domains in ℝ ^d . We demonstrate how the recently developed general theory of greedy approximation in Banach spaces can be used in this problem. The use of greedy approximation has two important advantages: (1) it works for an arbitrary dictionary of sets used for sparse representation and (2) the method of approximation does not depend on smoothness properties of the domains and automatically provides a near optimal rate of approximation for domains with different smoothness properties. We also give some lower estimates of the approximation error and discuss a specific greedy algorithm for approximation of convex domains in ℝ².     

A Lower Bound on the Greedy Weights of Product Codes

A greedy 1-subcode is a one-dimensional subcode of minimum (support) weight. A greedy r-subcode is an r-dimensional subcode with minimum support weight under the constraint that it contain a greedy (r - 1)-subcode. The r-th greedy weight e _r is the support weight of a greedy r-subcode. The greedy weights are related to the weight hierarchy. We use recent results on the weight hierarchy of product codes to develop a lower bound on the greedy weights of product codes.     

Substitution and atomic extension on greedy posets

In this paper, we study the operations of substitution and atomic extension on greedy posets. For the substitution operation, if P=(P ₁ , x, P ₂ )is a greedy poset, then P ₁ and P ₂ are greedy posets, the converse being false. However, for the atomic extension, P=P ₁ (x, P ₂ )is a greedy poset if and only if P ₁ and P ₂ are greedy posets. We prove also that the class of greedy semi-partitive lattices is the smallest one containing M _n (n2), B ₃ and closed by atomic extension. The class C _n of greedy posets with jump number n is infinite. However, we show that C _n can be obtained, in a very simple way, from a subclass D _n of finite cardinal ity. We construct D _n for n=1, 2.     

Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Anisotropic smoothness spaces via level sets

It has been understood for sometime that the classical smoothness spaces, such as the Sobolev and Besov classes, are not satisfactory for certain problems in image processing and nonlinear PDEs. Their deficiency lies in their isotropy. Functions in these smoothness spaces must be simultaneously smooth in all directions. The anisotropic generalizations of these spaces also have the deficiency that they are biased in coordinate directions. While they allow different smoothness in certain directions, these directions must be aligned to the coordinate axes. In the application areas mentioned above, it would be desirable to measure smoothness in new ways that would allow one to have more local control over the smoothness directions. We introduce one possible approach to this problem based on defining smoothness via level sets. We present this approach in the case of functions defined on ?^d. Our smoothness spaces depend on two smoothness indices (s₁, s₂). The first reflects the smoothness of the level sets of the function, while the second index reflects how smoothly the level sets themselves are changing. As a motivation, we start with d = 2 and investigate Besov smooth domains. © 2007 Wiley Periodicals, Inc.     

Greedy posets for the bump-minimizing problem

A bump (x _i,x _i+1) occurs in a linear extension L={x ₁<...n} of a poset P, if x _ii+1 in P. L. is greedy if x _ij for every j>i, whenever (x _i x _i+1) in a bump in L. The purpose of this paper is to give a characterization of all greedy posets. These are the posets for which every greedy linear extension has a minimum number of bumps.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

An example of an almost greedy uniformly bounded orthonormal basis for

We construct a uniformly bounded orthonormal almost greedy basis for L_p(0,1), 1<p<∞. The example shows that it is not possible to extend Orlicz's theorem, stating that there are no uniformly bounded orthonormal unconditional bases for L_p(0,1), p≠2, to the class of almost greedy bases.     

On the convergence of greedy approximants of trigonometric Fourier series

Efficient versions of the Cauchy criterion for the convergence in L _p of greedy approximants of trigonometric Fourier series are discussed.     

Best m-ter m trigono metric approxi mation for the classes $ B_{p,{{\uptheta }}}^r $ of functions of low s moothness

We obtain an exact-order estimate for the best m-term trigonometric approximation of the Besov classes B_p,\uptheta ^r B_{p,{{\uptheta }}}^r of periodic functions of many variables of low smoothness in the space L _q , 1 < p ≤ 2 < q < ∞.     

Inequalities for the greedy dimensions of ordered sets

Every linear extension L: [x ₁<x ₂<...<x _m ] of an ordered set P on m points arises from the simple algorithm: For each i with 0i<m, choose x _i+1 as a minimal element of P–{x _j :ji}. A linear extension is said to be greedy, if we also require that x _i+1 covers x _i in P whenever possible. The greedy dimension of an ordered set is defined as the minimum number of greedy linear extensions of P whose intersection is P. In this paper, we develop several inequalities bounding the greedy dimension of P as a function of other parameters of P. We show that the greedy dimension of P does not exceed the width of P. If A is an antichain in P and |P–A|2, we show that the greedy dimension of P does not exceed |P–A|. As a consequence, the greedy dimension of P does not exceed |P|/2 when |P|4. If the width of P–A is n and n2, we show that the greedy dimension of P does not exceed n ²+n. If A is the set of minimal elements of P, then this inequality can be strengthened to 2n–1. If A is the set of maximal elements, then the inequality can be further strengthened to n+1. Examples are presented to show that each of these inequalities is best possible.Research supported in part by the National Science Foundation under ISP-80110451.Research supported in part by the National Science Foundation under ISP-80110451 and DMS-8401281.     

Characterization of Sobolev spaces of arbitrary smoothness using nonstationary tight wavelet frames

In this paper we shall characterize Sobolev spaces of an arbitrary order of smoothness using nonstationary tight wavelet frames for L ₂(ℝ). In particular, we show that a Sobolev space of an arbitrary fixed order of smoothness can be characterized in terms of the weighted ℓ₂-norm of the analysis wavelet coefficient sequences using a fixed compactly supported nonstationary tight wavelet frame in L ₂(ℝ) derived from masks of pseudosplines in [15]. This implies that any compactly supported nonstationary tight wavelet frame of L ₂(ℝ) in [15] can be properly normalized into a pair of dual frames in the corresponding pair of dual Sobolev spaces of an arbitrary fixed order of smoothness. Research supported in part by NSERC Canada under Grant RGP 228051. Research supported in part by Grant R-146-000-060-112 at the National University of Singapore.     

On Kolmogorov widths of classesB p,θ r of periodic functions of many variables with low smoothness in the spacel q

We study the Kolmogorov widths of Besov classesB _p, ^r of periodic functions of many variables with low smoothness in the spaceLq, 1相似文献   

Limiting smoothness of the solution of a nonstationary problem with one or two obstacles

The regularity of the solution of a nonstationary problem with an obstable for various forms of parabolic operators has been thoroughly investigated. Under the condition of sufficient smoothness of the data of the problem, one proves that the solutionW _q ^2,1 (Q) belongs to the Sobolev space In the present paper one establishes that the limiting possible smoothness of the solution of a nonstationary problem with one or two obstacles is the boundedness of the second derivatives of the solution with respect to the spatial variables and of the first derivatives with respect to t. One assumes that the operator is linear and the functions defining the obstacles have the minimal possible smoothness.Translated from Problemy Matematicheskogo Analiza, No. 9, pp. 149–157, 1984.     

Approximation by a class of modified Szász-Durrmeyer operators

We modify Szász-Durrmeyer operators by means of three-diagonal generalized matrix which overcomes a difficulty in extending a Berens-Lorentz result to the Szász-Durrmeyer operators for second order of smoothness. The direct and converse theorems for these operators inL _p are also presented by Ditzian-Totik modulus of smoothness.This project is supported by Zhejiang Provincial Foundation of China.     

Sum List Coloring Graphs

Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs K_n are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum choice greedy is also sum choice greedy. We also determine the sum choice number of K_2,n, and we show that every tree on n vertices can be obtained from K_n by consecutively deleting single edges where all intermediate graphs are sc-greedy.     

Asymptotic structure, -estimates of sequences, and compactness of multilinear mappings

We relate the moduli of asymptotic uniform smoothness and convexity of a Banach space with the existence of upper and lower ℓ_p-estimates of sequences in the space. To this end, we introduce two properties which are related to the (m_p)-property defined by Kalton and Werner. In this way we obtain a connection between the moduli of asymptotic uniform smoothness and convexity, and compactness or weak-sequential continuity of multilinear mappings. Finally, we give some applications to the existence of analytic and asymptotically flat norms on a Banach space.     

全纯A_μ空间中K-泛函和光滑模的等价性

本文研究了Cn中星型圆形域D上的全纯Aμ空间中两个逼近工具光滑模与K-泛函的关系问题,通过得到Aμ空间中的Bernstein不等式,获得了利用径向导数定义新的K-泛函与光滑模与K-泛函的等价性以及Marchaud不等式,推广了实函数空间中的结果.