Greedy expansions in convex optimization
From MaRDI portal
Publication:483395
DOI10.1134/S0081543814010180zbMATH Open1306.49052arXiv1206.0393MaRDI QIDQ483395FDOQ483395
Authors: V. N. Temlyakov 
Publication date: 17 December 2014
Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)
Abstract: This paper is a follow up to the previous author's 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 three the most popular in nonlinear approximation in Banach spaces greedy algorithms -- 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 th iteration is equal to the sum of the approximant from the previous iteration (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 a 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.
Full work available at URL: https://arxiv.org/abs/1206.0393
Recommendations
Cites Work
- Introductory lectures on convex optimization. A basic course.
- Title not available (Why is that?)
- Weak greedy algorithms
- Greedy approximation
- Greedy approximation
- Greedy algorithms and \(M\)-term approximation with regard to redundant dictionaries
- Greedy-type approximation in Banach spaces and applications
- The convex geometry of linear inverse problems
- Trading accuracy for sparsity in optimization problems with sparsity constraints
- Sequential greedy approximation for certain convex optimization problems
- Greedy expansions in convex optimization
- Convex analysis and nonlinear optimization. Theory and examples.
- Greedy approximation in convex optimization
Cited In (11)
- Greedy approximation in convex optimization
- Convex optimization on Banach spaces
- Greedy expansions in convex optimization
- Greedy Families for Linear Objective Functions
- From greedy to lazy expansions and their driving dynamics
- Biorthogonal greedy algorithms in convex optimization
- Convergence and rate of convergence of some greedy algorithms in convex optimization
- Greedy strategies for convex optimization
- Duality gap estimates for weak Chebyshev greedy algorithms in Banach spaces
- Dictionary descent in optimization
- Rescaled pure greedy algorithm for convex optimization
This page was built for publication: Greedy expansions in convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q483395)
