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.     

Generalized Approximate Weak Greedy Algorithms

We study generalized approximate weak greedy algorithms. The main difference of these algorithms from approximate weak greedy algorithms proposed by R. Gribonval and M. Nielsen consists in that errors in the calculation of the coefficients can be prescribed in terms of not only their relative values, but also their absolute values. We present conditions on the parameters of generalized approximate weak greedy algorithms which are sufficient for the expansions resulting from the use of this algorithm to converge to the expanded element. It is shown that these conditions cannot be essentially weakened. We also study some questions of the convergence of generalized approximate weak greedy expansions with respect to orthonormal systems.__________Translated from Matematicheskie Zametki, vol. 78, no. 2, 2005, pp. 186–201.Original Russian Text Copyright © 2005 by V. V. Galatenko, E. D. Livshits.     

Greedy expansions in Banach spaces

We study convergence and rate of convergence of expansions of elements in a Banach space X into series with regard to a given dictionary . For convenience we assume that is symmetric: implies . The primary goal of this paper is to study representations of an element f∈X by a series

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.     

Relaxation in Greedy Approximation

We study greedy algorithms in a Banach space from the point of view of convergence and rate of convergence. There are two well-studied approximation methods: the Weak Chebyshev Greedy Algorithm (WCGA) and the Weak Relaxed Greedy Algorithm (WRGA). The WRGA is simpler than the WCGA in the sense of computational complexity. However, the WRGA has limited applicability. It converges only for elements of the closure of the convex hull of a dictionary. In this paper we study algorithms that combine good features of both algorithms, the WRGA and the WCGA. In the construction of such algorithms we use different forms of relaxation. First results on such algorithms have been obtained in a Hilbert space by A. Barron, A. Cohen, W. Dahmen, and R. DeVore. Their paper was a motivation for the research reported here.     

Weak Convergence of Greedy Algorithms in Banach Spaces

We study the convergence of certain greedy algorithms in Banach spaces. We introduce the WN property for Banach spaces and prove that the algorithms converge in the weak topology for general dictionaries in uniformly smooth Banach spaces with the WN property. We show that reflexive spaces with the uniform Opial property have the WN property. We show that our results do not extend to algorithms which employ a ‘dictionary dual’ greedy step.     

Convergence of Greedy Algorithms in Banach Spaces

We study the convergence of greedy algorithms in Banach spaces. We construct an example of a smooth Banach space, where the X-greedy algorithm converges not for all dictionaries and initial vectors. We also study the R-greedy algorithm, which, along with the X-greedy algorithm, is a generalization of the simple greedy algorithm in Hilbert space. We prove its convergence for a certain class of Banach spaces. In particular, this class contains, the spaces ^p,p 2.     

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相似文献   

Strong convergence of projection algorithms for a family of relatively quasi-nonexpansive mappings and an equilibrium problem in Banach spaces

In this article, we introduce two kinds of new hybrid projection algorithms for finding a common element of the set of solutions of an equilibrium problem and the set of common fixed points of an infinitely countable family of relatively quasi-nonexpansive mappings in a Banach space. Our main results improve and extend the result obtained by Martinez-Yanes and Xu [Strong convergence of the CQ method for fixed point iteration processes, Nonlinear Anal. 64 (2006), pp. 2400–2411] and the corresponding results.     

Greedy algorithms and bestm-term approximation with respect to biorthogonal systems

The article extends upon previous work by Temlyakov, Konyagin, and Wojtaszczyk on comparing the error of certain greedy algorithms with that of best m-term approximation with respect to a general biorthogonal system in a Banach space X. We consider both necessary and sufficient conditions which cover most of the special cases previously considered. Some new results concerning the Haar system in L₁, L_∞, and BMO are also included.     

Hybrid Proximal-Type and Hybrid Shrinking Projection Algorithms for Equilibrium Problems,Maximal Monotone Operators,and Relatively Nonexpansive Mappings

In this article, we introduce two hybrid proximal-type algorithms and two hybrid shrinking projection algorithms by using the hybrid proximal-type method and the hybrid shrinking projection method, respectively, for finding a common element of the set of solutions of an equilibrium problem, the set of fixed points of a relatively nonexpansive mapping, and the set of solutions to the equation 0 ∈ Tx for a maximal monotone operator T defined on a uniformly smooth and uniformly convex Banach space. The strong convergence of the sequences generated by the proposed algorithms is established. Our results improve and generalize several known results in the literature.     

On some characterizations of greedy-type bases

In 1999, S. V. Konyagin and V. N. Temlyakov introduced the so-called Thresholding Greedy Algorithm. Since then, there have been many interesting and useful characterizations of greedy-type bases in Banach spaces. In this article, we study and extend several characterizations of greedy and almost greedy bases in the literature. Along the way, we give various examples to complement our main results. Furthermore, we propose a new version of the so-called Weak Thresholding Greedy Algorithm (WTGA) and show that the convergence of this new algorithm is equivalent to the convergence of the WTGA.     

On a proximal point method for convex optimization in banach spaces

We analyze the behavior of a parallel proximal point method for solving convex optimization problems in reflexive Banach spaces. Similar algorithms were known to converge under the implicit assumption that the norm of the space is Hilbertian. We extend the area of applicability of the proximal point method to solving convex optimization problems in Banach spaces on which totally convex functions can be found. This includes the class of all smooth uniformly convex Banach spaces. Also, our convergence results leave more flexibility for the choice of the penalty function involved in the algorithm and, in this way, allow simplification of the computational procedure.     

Strong convergence theorems for two countable families of weak relatively nonexpansive mappings and applications

The purpose of this article is to prove strong convergence theorems for common fixed points of two countable families of weak relatively nonexpansive mappings in Banach spaces. In order to get the strong convergence theorems, the monotone hybrid algorithms are presented and are used to approximate the common fixed points. Using this result, we also discuss the problem of strong convergence concerning the maximal monotone operators in a Banach space. The results of this article modify and improve the results of Matsushita and Takahashi [S. Matsushita, W. Takahashi, A strong convergence theorem for relatively nonexpansive mappings in a Banach space, J. Approx. Theory 134 (2005) 257-266] and the results of Plubtieng and Ungchittrakool [S. Plubtieng, K. Ungchittrakool, Strong convergence theorems for a common fixed point of two relatively nonexpansive mappings in a Banach space, J. Approx. Theory 149 (2007) 103-115] and the results of Su et al. [Y. Su, Z. Wang and H. Xu, Strong convergence theorems for a common fixed point of two hemi-relatively nonexpansive mappings, Nonlinear Anal. 71 (2009) 5616-5628], and many others.     

Ball Convergence for Higher Order Methods Under Weak Conditions

We present a local convergence analysis for higher order methods in order to approximate a locally unique solution of an equation in a Banach space setting. In earlier studies, Taylor expansions and hypotheses on higher order Fréchet-derivatives are used. We expand the applicability of these methods using only hypotheses on the first Fréchet derivative. Moreover, we obtain a radius of convergence and computable error bounds using Lipschitz constants not given before. Numerical examples are also presented in this study.     

Greedy Algorithms for High-Dimensional Eigenvalue Problems

In this article, we present two new greedy algorithms for the computation of the lowest eigenvalue (and an associated eigenvector) of a high-dimensional eigenvalue problem and prove some convergence results for these algorithms and their orthogonalized versions. The performance of our algorithms is illustrated on numerical test cases (including the computation of the buckling modes of a microstructured plate) and compared with that of another greedy algorithm for eigenvalue problems introduced by Ammar and Chinesta.     

Schwarz methods for inequalities with contraction operators

We prove the convergence of some multiplicative and additive Schwarz methods for inequalities which contain contraction operators. The problem is stated in a reflexive Banach space and it generalizes the well-known fixed-point problem in the Hilbert spaces. Error estimation theorems are given for three multiplicative algorithms and two additive algorithms. We show that these algorithms are in fact Schwarz methods if the subspaces are associated with a decomposition of the domain. Also, for the one- and two-level methods in the finite element spaces, we write the convergence rates as functions of the overlapping and mesh parameters. They are similar with the convergence rates of these methods for linear problems. Besides the direct use of the five algorithms for the inequalities with contraction operators, we can use the above results to obtain the convergence rate of the Schwarz method for other types of inequalities or nonlinear equations. In this way, we prove the convergence and estimate the error of the one- and two-level Schwarz methods for some inequalities in Hilbert spaces which are not of the variational type, and also, for the Navier–Stokes problem. Finally, we give conditions of existence and uniqueness of the solution for all problems we consider. We point out that these conditions and the convergence conditions of the proposed algorithms are of the same type.     

Iterative algorithms for solving variational inequalities and fixed point problems for asymptotically nonexpansive mappings in Banach spaces

The purpose of this paper is to study some iterative algorithms for finding a common element of the set of solutions of systems of variational inequalities for inverse-strongly accretive mappings and the set of fixed points of an asymptotically nonexpansive mapping in uniformly convex and 2-uniformly smooth Banach space or uniformly convex and q-uniformly smooth Banach space. Strong convergence theorems are obtained under suitable conditions. We also give some numerical examples to support our main results. The results obtained in this paper improve and extend the recent ones announced by many others in the literature.     

Series expansions of analytic functions

Many of the classical polynomial expansions of analytic functions share a common property: the space of “expandable” functions is a Banach space isometrically isomorphic to the space of complex sequences with limit 0. Under the isometries, these polynomial expansions all correspond to essentially the same biorthogonal expansion in this sequence space. Sufficient conditions for such an isometry to exist are obtained, and convergence properties of the expansions are studied. The results obtained also apply to expansions other than polynomial expansions.     

简化原理在Hilbert空间与可分Banach空间的一些应用

本文研究了简化原理在Hilbert空间与可分Banach空间中的一些应用,利用简化原理和独立随机元收敛准则获得了中分Banach空间随机级数的收缩原理和B-值随机Dirichlet级数简单收敛横坐标及一般随机整函数的增长性和值分布,将许多以Rademacher序列为系数的随机Tayor级数和随机Dirichlet级数的相关结果,推广到一般的具有独立对称分布系数的随机级数上去。