共查询到20条相似文献,搜索用时 31 毫秒
1.
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). 相似文献
2.
A. S. Orlova 《Moscow University Mathematics Bulletin》2017,72(2):84-87
The convergence rate of a weak orthogonal greedy algorithm is studied for the subspace ?1 ? ?2 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. 相似文献
3.
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. 相似文献
4.
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. 相似文献
5.
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 ?2, 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 1×?×D N contained in ? Nd , where each set D i , i=1,…,N, is a bounded open ball in ? d , d=2,3. 相似文献
6.
J. L. Nelson V. N. Temlyakov 《Proceedings of the Steklov Institute of Mathematics》2013,280(1):227-239
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 1(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}}$ . 相似文献
7.
Jonathan Elbaz 《Order》1986,3(3):235-244
In this paper, we study the operations of substitution and atomic extension on greedy posets. For the substitution operation, if P=(P
1
, x, P
2
)is a greedy poset, then P
1
and P
2
are greedy posets, the converse being false. However, for the atomic extension, P=P
1
(x, P
2
)is a greedy poset if and only if P
1
and P
2
are greedy posets. We prove also that the class of greedy semi-partitive lattices is the smallest one containing M
n
(n2), B
3
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. 相似文献
8.
G. Amirkhanyan 《Journal of Contemporary Mathematical Analysis (Armenian Academy of Sciences)》2008,43(3):127-134
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. 相似文献
9.
Sean McGuinness 《Combinatorica》1994,14(3):321-334
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 2/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( n ) cliques. Heret p-1( n ) 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/2. We prove this conjecture forK 4-free graphs and show that in the case of equality forC andG there are only two possibilities:
- G?K n/2,n/2
- G is complete 3-partite, where each part hasn/3 vertices.
10.
L. A. Wolsey 《Combinatorica》1982,2(4):385-393
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. 相似文献
11.
V. N. Temlyakov 《Constructive Approximation》2002,18(4):529-550
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 Du 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. 相似文献
12.
Ievgen V. Bondarenko Rostyslav V. Kravchenko 《Discrete and Computational Geometry》2011,46(2):389-393
Let A be an expanding integer n×n matrix and D be a finite subset of ? n . 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∈? n , and the measure of the intersection of self-affine sets T(A,D 1)∩T(A,D 2) for different sets D 1, D 2?? n . 相似文献
13.
《Journal of Complexity》2003,19(4):458-473
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. 相似文献
14.
A. Escassut 《P-Adic Numbers, Ultrametric Analysis, and Applications》2016,8(2):115-124
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 1(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 1(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 1(A, ‖. ‖), which suggest that Mult 1(A, ‖. ‖)might be dense in Mult(A, ‖. ‖). 相似文献
15.
Alberto Baider 《Journal of Mathematical Analysis and Applications》1978,62(2):247-256
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 D0(A) = D1(A) to hold. Here D0(A) and D1(A) are the domains of the minimal and maximal extensions of A respectively. Under the general assumption that are bounded above it is proven that under certain conditions D0(A) = D1(A) if functions which are constant near the boundaries of J are in whenever they are in . In particular if A is formally selfadjoint and 1 ?D1(A) then D1(A) = D0(A) if and only if 1 ?D0(A). When the measure of J is infinite at both ends D0(A) is always equal to D1(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 D0 = D1 holds. 相似文献
16.
S. A. Episkoposyan 《Siberian Mathematical Journal》2013,54(5):810-816
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. 相似文献
17.
Every linear extension L: [x
1<x
2<...<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
2+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. 相似文献
18.
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. 相似文献
19.
Divergence of the greedy algorithm in the Faber-Schauder system on a continuum cardinality set 总被引:1,自引:0,他引:1
A. A. Sargsyan 《Journal of Contemporary Mathematical Analysis (Armenian Academy of Sciences)》2007,42(2):109-115
The paper establishes that there exist a continuum cardinality set E 0 ? [0, 1] and a function f 0(x) ∈ C [0,1], such that the greedy algorithm of f 0(x) with respect to the Faber-Schauder system converges to +∞ at all points of E 0. 相似文献
20.
Let CA(±) be the additive complexity of a (bi)linear algorithm A for a given problem; D(A) and 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. , do(D(A)), and ir(D(A)) characterize the logical complexity of A. It is shown that CA(±) + do(D(A)) + ir(D(A)) = ω(K + Q)log(K + Q) and in the cases of DFT, vector convolution, and matrix multiplication. Also lower bounds on CA(±) + do(D(A)) and on CA(±) are expressed in terms of algebraic quantities such as the ranks of matrices and of multidimensional tensors associated with the problems. 相似文献