Rate of Convergence of Pure Greedy Algorithms

This paper is devoted to the study of the rate of convergence of pure greedy algorithms in Hilbert space. We obtain upper bounds for the rate of convergence of pure greedy algorithms for functions from the class A _{α, β}(D).     

The rate of convergence of weak greedy approximations over orthogonal dictionaries

The convergence rate of a weak orthogonal greedy algorithm is studied for the subspace ?¹ ? ?² and orthogonal dictionaries. It is shown that general results on convergence rate of weak orthogonal greedy algorithms can be essentially improved in the studied case. It is also shown that this improvement is asymptotically sharp.     

Asymptotic packing and the random greedy algorithm

Let H be an r-uniform hypergraph satisfying deg(x) = D(1 + o(1)) for each vertex xϵ V(H) and deg(x, y) = o(D) for each pair of vertices x, y ϵ V(H), where D → infinity. Recently, J. Spencer [5] showed, using a branching process approach, that almost surely the random greedy algorithm finds a packing of size at least n/r(1 − o(1)) for this class of hypergraphs. In this paper, we show an alternative proof of this via “nibbles.” Further, let T_α be the number of edges that the random greedy algorithm has to consider before yielding a packing of size [n/r · (1 − α)]. We show that almost surely T_α ∼ (1/α)^r−1 · n/r(r − 1) as α → 0⁺ holds. © 1996 John Wiley & Sons, Inc.     

Efficiency of weak greedy algorithms for m-term approximations

We investigate the efficiency of weak greedy algorithms for m-term expansional approximation with respect to quasi-greedy bases in general Banach spaces.We estimate the corresponding Lebesgue constants for the weak thresholding greedy algorithm(WTGA) and weak Chebyshev thresholding greedy algorithm.Then we discuss the greedy approximation on some function classes.For some sparse classes induced by uniformly bounded quasi-greedy bases of L_p,1p∞,we show that the WTGA realizes the order of the best m-term approximation.Finally,we compare the efficiency of the weak Chebyshev greedy algorithm(WCGA) with the thresholding greedy algorithm(TGA) when applying them to quasi-greedy bases in L_p,1≤p∞,by establishing the corresponding Lebesgue-type inequalities.It seems that when p2 the WCGA is better than the TGA.     

Greedy Approximation of High-Dimensional Ornstein–Uhlenbeck Operators

We investigate the convergence of a nonlinear approximation method introduced by Ammar et?al. (J. Non-Newtonian Fluid Mech. 139:153–176, 2006) for the numerical solution of high-dimensional Fokker–Planck equations featuring in Navier–Stokes–Fokker–Planck systems that arise in kinetic models of dilute polymers. In the case of Poisson’s equation on a rectangular domain in ?², subject to a homogeneous Dirichlet boundary condition, the mathematical analysis of the algorithm was carried out recently by Le Bris, Lelièvre and Maday (Const. Approx. 30:621–651, 2009), by exploiting its connection to greedy algorithms from nonlinear approximation theory, explored, for example, by DeVore and Temlyakov (Adv. Comput. Math. 5:173–187, 1996); hence, the variational version of the algorithm, based on the minimization of a sequence of Dirichlet energies, was shown to converge. Here, we extend the convergence analysis of the pure greedy and orthogonal greedy algorithms considered by Le Bris et al. to a technically more complicated situation, where the Laplace operator is replaced by an Ornstein–Uhlenbeck operator of the kind that appears in Fokker–Planck equations that arise in bead–spring chain type kinetic polymer models with finitely extensible nonlinear elastic potentials, posed on a high-dimensional Cartesian product configuration space D=D ₁×?×D _N contained in ? ^Nd , where each set D _i , i=1,…,N, is a bounded open ball in ? ^d , d=2,3.     

Greedy expansions in Hilbert spaces

We study the rate of convergence of expansions of elements in a Hilbert space H into series with regard to a given dictionary D. The primary goal of this paper is to study representations of an element f ∈ H by a series f ～ ∑ _j=1 ^∞ c _j (f)g _j (f), $g_j \left( f \right) \in \mathcal{D}$ . Such a representation involves two sequences: {g _j (f)} _j=1 ^∞ and {c _j (f) _j=1 ^∞ . In this paper the construction of {g _j (f)} _j=1 ^∞ is based on ideas used in greedy-type nonlinear approximation, hence the use of the term greedy expansion. An interesting open problem questions, “What is the best possible rate of convergence of greedy expansions for f ∈ A ₁(D)?” Previously it was believed that the rate of convergence was slower than $m^{ - \tfrac{1} {4}}$ . The qualitative result of this paper is that the best possible rate of convergence of greedy expansions for $f \in A_1 \left( \mathcal{D} \right)$ is faster than $m^{ - \tfrac{1} {4}}$ . In fact, we prove it is faster than $m^{ - \tfrac{2} {7}}$ .     

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.     

Convergence of greedy algorithm in Walsh system in <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>

Convergence of the greedy algorithm in Walsh system in L _p , p > 1 is studied. It is proved that there exists a function in L _p , 1 < p < 2, with greedy algorithm not converging in measure to that function. A continuous function with divergent in L _p , p > 2, greedy algorithm is constructed and sufficient conditions for convergence of the greedy algorithm in L _p , p > 1 are given.     

Restricted greedy clique decompositions and greedy clique decompositions ofK 4-free graphs

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. In this paper, we extend this result by showing that for any positive integerp, 3≤p any clique decomposisitioof a graph of ordern obtained by removing maximal cliques of order at leastp one by one until none remain, in which case the remaining edges are removed one by one, has at mostt _p-1( ⁿ ) cliques. Heret _p-1( ⁿ ) is the number of edges in the Turán graph of ordern, which has no complete subgraphs of orderp. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decompositionC of a graphG of ordern the sum over the number of vertices in each clique ofC is at mostn ²/2. We prove this conjecture forK ₄-free graphs and show that in the case of equality forC andG there are only two possibilities:

1. G?K _n/2,n/2
2. G is complete 3-partite, where each part hasn/3 vertices.

We show that in either caseC is completely determined.     

An analysis of the greedy algorithm for the submodular set covering problem

We consider the problem: min \(\{ \mathop \Sigma \limits_{j \in s} f_j :z(S) = z(N),S \subseteqq N\} \) wherez is a nondecreasing submodular set function on a finite setN. Whenz is integer-valued andz(Ø)=0, it is shown that the value of a greedy heuristic solution never exceeds the optimal value by more than a factor \(H(\mathop {\max }\limits_j z(\{ j\} ))\) where \(H(d) = \sum\limits_{i = 1}^d {\frac{1}{i}} \) . This generalises earlier results of Dobson and others on the applications of the greedy algorithm to the integer covering problem: min {fy: Ay ≧b, y ε {0, 1}} wherea _ij ,b _i } ≧ 0 are integer, and also includes the problem of finding a minimum weight basis in a matroid.     

Universal bases and greedy algorithms for anisotropic function classes

We suggest a three-step strategy to find a good basis (dictionary) for non-linear m-term approximation. The first step consists of solving an optimization problem of finding a near best basis for a given function class F, when we optimize over a collection D of bases (dictionaries). The second step is devoted to finding a universal basis (dictionary) D _u ∈ D for a given pair (F, D) of collections: F of function classes and D of bases (dictionaries). This means that D_u provides near optimal approximation for each class F from a collection F. The third step deals with constructing a theoretical algorithm that realizes near best m-term approximation with regard to D _u for function classes from F. In this paper we work this strategy out in the model case of anisotropic function classes and the set of orthogonal bases. The results are positive. We construct a natural tensor-product-wavelet-type basis and prove that it is universal. Moreover, we prove that a greedy algorithm realizes near best m-term approximation with regard to this basis for all anisotropic function classes.     

On Lebesgue Measure of Integral Self-Affine Sets

Let A be an expanding integer n×n matrix and D be a finite subset of ? ⁿ . The self-affine set T=T(A,D) is the unique compact set satisfying the equality \(A(T)=\bigcup_{d\in D}(T+d)\). We present an effective algorithm to compute the Lebesgue measure of the self-affine set T, the measure of the intersection T∩(T+u) for u∈? ⁿ , and the measure of the intersection of self-affine sets T(A,D ₁)∩T(A,D ₂) for different sets D ₁, D ₂?? ⁿ .     

Vector greedy algorithms

Our objective is to study nonlinear approximation with regard to redundant systems. 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. Greedy-type approximations proved to be convenient and efficient ways of constructing m-term approximants. We introduce and study vector greedy algorithms that are designed with aim of constructing mth greedy approximants simultaneously for a given finite number of elements. We prove convergence theorems and obtain some estimates for the rate of convergence of vector greedy algorithms when elements come from certain classes.     

The Corona problem on a complete ultrametric algebraically closed field

Let IK be a complete ultrametric algebraically closed field and let A be the Banach IK-algebra of bounded analytic functions in the ”open” unit disk D of IK provided with the Gauss norm. Let Mult(A, ‖. ‖) be the set of continuous multiplicative semi-norms of A provided with the topology of simple convergence, let Mult _m (A, ‖. ‖) be the subset of the ? ∈ Mult(A, ‖. ‖) whose kernel is amaximal ideal and let Mult ₁(A, ‖. ‖) be the subset of the ? ∈ Mult(A, ‖. ‖) whose kernel is a maximal ideal of the form (x ? a)A with a ∈ D. By analogy with the Archimedean context, one usually calls ultrametric Corona problem the question whether Mult ₁(A, ‖. ‖) is dense in Mult _m (A, ‖. ‖). In a previous paper, it was proved that when IK is spherically complete, the answer is yes. Here we generalize this result to any algebraically closed complete ultrametric field, which particularly applies to ? _p . On the other hand, we also show that the continuous multiplicative seminorms whose kernel are neither a maximal ideal nor the zero ideal, found by Jesus Araujo, also lie in the closure of Mult ₁(A, ‖. ‖), which suggest that Mult ₁(A, ‖. ‖)might be dense in Mult(A, ‖. ‖).     

Weak and strong extensions of ordinary differential operators

Let A be a second order differential operator with positive leading term defined on an interval J of R. In this paper we study conditions for the equality D₀(A) = D₁(A) to hold. Here D₀(A) and D₁(A) are the domains of the minimal and maximal extensions of A respectively. Under the general assumption that $\text{A(1)}\text{and}\text{A}{}^1\text{(1)}$ are bounded above it is proven that under certain conditions D₀(A) = D₁(A) if functions which are constant near the boundaries of J are in $\text{D}{}_0\text{(A) ∩ D}{}_0\text{(A}{}^1\text{)}$ whenever they are in $\text{D}{}_1\text{(A) ∩ D}{}_1\text{(A}{}^1\text{)}$. In particular if A is formally selfadjoint and 1 ?D₁(A) then D₁(A) = D₀(A) if and only if 1 ?D₀(A). When the measure of J is infinite at both ends D₀(A) is always equal to D₁(A). This fact is used to show that the leading term of A as well as its terminal coefficient can be chosen arbitrarily (although not independently of one another) in such a way that the equality D₀ = D₁ holds.     

On the uniform convergence of the greedy algorithm in a generalized Walsh system

We consider the problems of the uniform convergence of the greedy algorithm in the generalized Walsh system Ψ _a , a ≥ 2, after correcting a function on a set of small measure.     

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.     

Super greedy type algorithms

We study greedy-type algorithms such that at a greedy step we pick several dictionary elements contrary to a single dictionary element in standard greedy algorithms. We call such greedy algorithms super greedy type algorithms. The super greedy type algorithms are computationally simpler than their analogues from the standard greedy algorithms. In this article, we propose the Weak Super Greedy Algorithm (WSGA) and the Weak Orthogonal Super Greedy Algorithm with Thresholding (WOSGAT). Their performance (rate of convergence) are studied as well under M-coherent dictionaries.     

Divergence of the greedy algorithm in the Faber-Schauder system on a continuum cardinality set

The paper establishes that there exist a continuum cardinality set E ₀ ? [0, 1] and a function f ₀(x) ∈ C _[0,1], such that the greedy algorithm of f ₀(x) with respect to the Faber-Schauder system converges to +∞ at all points of E ₀.     

The additive and logical complexities of linear and bilinear arithmetic algorithms

Let C_A(±) be the additive complexity of a (bi)linear algorithm A for a given problem; D(A) and $\text{D}\text{(A)}$ are two acyclic diagraphs that represent A, each of them is obtained from another one by reversing directions of all edges; ir(D) and do(D) are two numbers that are introduced to measure the structural deficiencies of an acyclic digraph D. K and Q are the numbers of outputs and input-variables. $\text{do(}\text{D}\text{(A))}$, do(D(A)), and ir(D(A)) characterize the logical complexity of A. It is shown that C_A(±) + do(D(A)) + ir(D(A)) = ω(K + Q)log(K + Q) and $\text{C}{}_{\mathrm{A}}\text{(±) + do(}\text{D}\text{(A)) = ω(K + Q)}\text{log}\text{(K + Q)}$ in the cases of DFT, vector convolution, and matrix multiplication. Also lower bounds on C_A(±) + do(D(A)) and on C_A(±) are expressed in terms of algebraic quantities such as the ranks of matrices and of multidimensional tensors associated with the problems.