The Efficiency Of The Rescaled Pure Greedy Algorithm For M-Term Approximations

Greedy algorithm is one of the important research fields of function approximation theory.The Rescaled Pure Greedy Algorithm is a new greedy approximation algorithm,which is very important in solving convex optimization problems.In this paper,the efficiency of Rescaled Pure Greedy Algorithm for m-term approximation will be studied in depth.Here we analyze the efficiency mainly including three aspects: on the one hand,we study the convergence of greedy algorithms.On the other hand,we estimate the convergence order of greedy algorithms,it is also divided into two cases.One case is estimate the convergence order of greedy algorithms in Banach spaces,the other case is estimate the convergence order of greedy algorithms on some function classes.The last aspect is establish the Lebesgue-type inequalities for greedy algorithms.The thesis consists of seven chapters.The main contents are as follows:Chapter 1 is the introduction,which mainly introduces research background,research motivation,the results of this paper and the significance and innovation of the results.In chapter 2,we study the convergence of the Weak Rescaled Pure Greedy Algorithm in Banach spaces,and obtain the sufficient and necessary conditions for the convergence of the Weak Rescaled Pure Greedy Algorithm.We compare these conditions with the convergence conditions of other greedy algorithms,and conclude that the Weak Rescaled Pure Greedy Algorithm has better properties.In chapter 3,we study the error estimate of the Weak Rescaled Pure Greedy Algorithm in the noisy version,and extend the concept of basic K-functional form Hilbert spaces to Banach spaces.Using this basic K-functional,we obtain the error estimate of the Weak Rescaled Pure Greedy Algorithm,from the error estimate we derive the sufficient conditions of convergence and the order of convergence on some sparse classes for the Weak Rescaled Pure Greedy Algorithm.In chapter 4,in general,under the assumption that the given element f belongs to the class of sparse element,the error bound obtained by the greedy algorithm after m iterations,this error bound depends on the algorithm itself and the class of element,but not depends on a single element in the class of element,is called the prior error bound.In order to improve the prior error bound of Rescaled Pure Greedy Algorithm,we discuss its posterior error bounds by using the information of its first m iterations.In chapter 5,we analyze the efficiency for the class of Weak Biorthogonal Greedy Algorithm,and obtain the error estimate by using the basic K-functional introduced in Banach spaces,and deduce the sufficient conditions of the convergence and the order of convergence on some sparse classes for the class of Weak Biorthogonal Greedy Algorithm.In chapter 6,we define the Approximate Weak Rescaled Pure Greedy Algorithm in Banach Spaces.By using the basic K-functional introduced in Banach space,we prove the error estimate of the Approximate Weak Rescaled Pure Greedy Algorithm,and obtain the sufficient conditions of the convergence,the order of convergence on some function classes and particular interpolation spaces for the Approximate Weak Rescaled Pure Greedy Algorithm.In Chapter 7,we use the order of the optimal m-term approximation error in Hilbert space to estimate the upper bound on the error of the Rescaled Pure Greedy Algorithm,and obtain the additive Lebesgue inequality for the Rescaled Pure Greedy Algorithm with the help of M-coherent dictionaries and λ-quasi-orthogonal dictionaries.