Tree wavelet approximations with applications

We construct a tree wavelet approximation by using a constructive greedy scheme (CGS). We define a function class which contains the functions whose piecewise polynomial approximations generated by the CGS have a prescribed global convergence rate and establish embedding properties of this class. We provide sufficient conditions on a tree index set and on bi-orthogonal wavelet bases which ensure optimal order of convergence for the wavelet approximations encoded on the tree index set using the bi-orthogonal wavelet bases. We then show that if we use the tree index set associated with the partition generated by the CGS to encode a wavelet approximation, it gives optimal order of convergence.     

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.     

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.     

Quantifying Democracy of Wavelet Bases in Lorentz Spaces

We study the efficiency of the greedy algorithm for wavelet bases in Lorentz spaces in order to give the near best approximation. The result is used to give sharp inclusions for the approximation spaces in terms of discrete Lorentz sequence spaces.     

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 ℝ².     

Greedy Bases Are Best for m-Term Approximation

We study the approximation of a subset K in a Banach space X by choosing first basis B and then using n-term approximation. Into the competition for best bases we enter all unconditional bases for X. We show that if the subset K⊂X is well aligned with respect to a greedy basis B, then, in a certain sense, this basis is the best for this type of approximation. Our result improves the recent result of DeVore, Petrova and Temlyakov.      

Greedy Algorithm for General Biorthogonal Systems

We consider biorthogonal systems in quasi-Banach spaces such that the greedy algorithm converges for each xX (quasi-greedy systems). We construct quasi-greedy conditional bases in a wide range of Banach spaces. We also compare the greedy algorithm for the multidimensional Haar system with the optimal m-term approximation for this system. This substantiates a conjecture by Temlyakov.     

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.     

软容量约束的动态设施选址问题的近似算法

考虑软容量约束的动态设施选址问题.假设设施的开放费用及连接费用都与时间有关,而且每一个设施均有容量约束.对此问题给出了第一个近似比为6的原始对偶(组合)算法.运行贪婪增加程序后,近似比进一步改进到3.7052.     

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.     

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 .     

Lebesgue-Type Inequalities for Quasi-greedy Bases

We show that, for quasi-greedy bases in real or complex Banach spaces, an optimal bound for the ratio between greedy N-term approximation ∥x?G _N x∥ and the best N-term approximation σ _N (x) is controlled by max{μ(N),k _N }, where μ(N) and k _N are well-known constants that quantify the democracy and conditionality of the basis. In particular, for democratic bases this bound is O(logN). We show with various examples that these bounds are actually attained.     

A rough set approach to the characterization of transversal matroids

Rough sets are efficient for data pre-processing during data mining. However, some important problems such as attribute reduction in rough sets are NP-hard and the algorithms required to solve them are mostly greedy ones. The transversal matroid is an important part of matroid theory, which provides well-established platforms for greedy algorithms. In this study, we investigate transversal matroids using the rough set approach. First, we construct a covering induced by a family of subsets and we propose the approximation operators and upper approximation number based on this covering. We present a sufficient condition under which a subset is a partial transversal, and also a necessary condition. Furthermore, we characterize the transversal matroid with the covering-based approximation operator and construct some types of circuits. Second, we explore the relationships between closure operators in transversal matroids and upper approximation operators based on the covering induced by a family of subsets. Finally, we study two types of axiomatic characterizations of the covering approximation operators based on the set theory and matroid theory, respectively. These results provide more methods for investigating the combination of transversal matroids with rough sets.     

Greedy expansions in convex optimization

This paper is a follow-up to the author’s previous paper on convex optimization. In that paper we began the process of adjusting greedy-type algorithms from nonlinear approximation for finding sparse solutions of convex optimization problems. We modified there the three most popular greedy algorithms in nonlinear approximation in Banach spaces-Weak Chebyshev Greedy Algorithm, Weak Greedy Algorithm with Free Relaxation, and Weak Relaxed Greedy Algorithm-for solving convex optimization problems. We continue to study sparse approximate solutions to convex optimization problems. It is known that in many engineering applications researchers are interested in an approximate solution of an optimization problem as a linear combination of elements from a given system of elements. There is an increasing interest in building such sparse approximate solutions using different greedy-type algorithms. In this paper we concentrate on greedy algorithms that provide expansions, which means that the approximant at the mth iteration is equal to the sum of the approximant from the previous, (m ? 1)th, iteration and one element from the dictionary with an appropriate coefficient. The problem of greedy expansions of elements of a Banach space is well studied in nonlinear approximation theory. At first glance the setting of a problem of expansion of a given element and the setting of the problem of expansion in an optimization problem are very different. However, it turns out that the same technique can be used for solving both problems. We show how the technique developed in nonlinear approximation theory, in particular, the greedy expansions technique, can be adjusted for finding a sparse solution of an optimization problem given by an expansion with respect to a given dictionary.     

Some remarks on greedy algorithms

Estimates are given for the rate of approximation of a function by means of greedy algorithms. The estimates apply to approximation from an arbitrary dictionary of functions. Three greedy algorithms are discussed: the Pure Greedy Algorithm, an Orthogonal Greedy Algorithm, and a Relaxed Greedy Algorithm.This research was supported by the Office of Naval Research Contract N0014-91-J1343.     

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.     

Greedy algorithm for functions with low mixed smoothness

In this note, we investigate the efficiency of the greedy algorithm for the classes of multivariate periodic functions with low mixed smoothness in L_q with regard to the wavelet-type basis. We find that the order of greedy approximation in the case of low smoothness is different for some range of parameters.     

Besov类上的贪婪算法

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

Maximizing non-monotone submodular set functions subject to different constraints: Combined algorithms

We study the problem of maximizing constrained non-monotone submodular functions and provide approximation algorithms that improve existing algorithms in terms of either the approximation factor or simplicity. Different constraints that we study are exact cardinality and multiple knapsack constraints for which we achieve (0.25−?)-factor algorithms.We also show, as our main contribution, how to use the continuous greedy process for non-monotone functions and, as a result, obtain a 0.13-factor approximation algorithm for maximization over any solvable down-monotone polytope.     

Lorentz Spaces and Embeddings Induced by Almost Greedy Bases in Banach Spaces

The aim of this paper is to undertake a systematic qualitative study of the built-in symmetry of almost greedy bases in Banach spaces. More specifically, by refining the techniques that Wojtaszczyk used in J Approx Theory 107(2), 293–314 2000 for quasi-greedy bases in Hilbert spaces, we show that an almost greedy basis in a Banach space X naturally induces embeddings that allow sandwiching X between two symmetric sequence spaces. Using classical interpolation techniques in combination with duality, we also explore what we label as interpolation of greedy bases. It is then proved that the only almost greedy basis shared by any two \(\ell _{p}\) spaces is equivalent to the standard unit vector basis and that there is no basis which is simultaneously (normalized and) greedy in two different \(L_{p}\) spaces. As a by-product of our work, we obtain a new characterization of greedy bases in Banach spaces in terms of bounded linear operators.