publication . Article . Preprint . 2015

Dictionary descent in optimization

Temlyakov, Vladimir;
Open Access
  • Published: 04 Nov 2015 Journal: Analysis Mathematica, volume 42, pages 69-89 (issn: 0133-3852, eissn: 1588-273X, Copyright policy)
  • Publisher: Springer Science and Business Media LLC
Abstract
The problem of convex optimization is studied. Usually in convex optimization the minimization is over a d-dimensional domain. Very often the convergence rate of an optimization algorithm depends on the dimension d. The algorithms studied in this paper utilize dictionaries instead of a canonical basis used in the coordinate descent algorithms. We show how this approach allows us to reduce dimensionality of the problem. Also, we investigate which properties of a dictionary are beneficial for the convergence rate of typical greedy-type algorithms.
Subjects
free text keywords: General Mathematics, Standard basis, Coordinate descent, Rate of convergence, Banach space, Optimization algorithm, Convex optimization, Mathematics, Curse of dimensionality, Topology, Minification, Mathematical optimization, Statistics - Machine Learning, Mathematics - Numerical Analysis
Related Organizations
Funded by
NSF| Greedy Approximation in Banach Spaces and Compressed Sensing
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1160841
  • Funding stream: Directorate for Mathematical & Physical Sciences | Division of Mathematical Sciences
19 references, page 1 of 2

[1] J.M. Borwein and A.S. Lewis, Convex Analysis and Nonlinear Optimization. Theory and Examples, Canadian Mathematical Society, Springer, 2006.

[2] R.A. DeVore, Deterministic Constructions of Compressed Sensing Matrices J. Complexity, 23 (2007), 918-925.

[3] R.A. DeVore and V.N. Temlyakov, Convex optimization on Banach spaces, Foundations of Computational Mathematics, Published online: February 14, 2015, 1-26 (arXiv:1401.0334v1, 1 Jan 2014). [OpenAIRE]

[4] I. Dumer, Covering spheres with spheres, Discrete Comput. Geom. 38 (2007), 665-679. [OpenAIRE]

[5] M.A.T. Figueiredo, R.D. Nowak, and S.J. Wright, Gradient projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems, IEEE, Selected Topics in Signal Processing, 1 (2007), 586-597.

[6] A.C. Gilbert, S. Muthukrishnan and M.J. Strauss, Approximation of functions over redundant dictionaries using coherence, The 14th Annual ACM-SIAM Symposium on Discrete Algorithms (2003).

[7] B.S. Kashin, On widths of octahedrons, Uspekhi Matem. Nauk, 30 (1975), 251-252.

[8] J.L. Nelson and V.N. Temlyakov, On the size of incoherent systems, J. Approximation Theory, 163 (2011), 1238-1245. [OpenAIRE]

[9] Yu. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Kluwer Academic Publishers, Boston, 2004.

[10] C.A. Rogers, Covering a sphere with spheres, Mathematika 10 (1963), 157-164.

[11] V.N. Temlyakov, Greedy algorithms in Banach spaces, Adv. Comput. Math., 14 (2001), 277-292.

[12] V.N. Temlyakov, Greedy approximation, Cambridge University Press, 2011.

[13] V.N. Temlyakov, Greedy approximation in convex optimization, Constructive Approximation, 41 (2015), 269-296 (arXiv: 1206.0392v1 [stat.ML] 2 Jun 2012). [OpenAIRE]

[14] V.N. Temlyakov, Greedy expansions in convex optimization, Proceedings of the Steklov Institute of Mathematics, 284 (2014), 244-262 (arXiv: 1206.0393v1 [stat.ML] 2 Jun 2012).

[15] V.N. Temlyakov, Chebyshev Greedy Algorithm in convex optimization, IMI Preprint, 2013:08, 1-11; arXiv:1312.1244v1, 4 Dec 2013. [OpenAIRE]

19 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Article . Preprint . 2015

Dictionary descent in optimization

Temlyakov, Vladimir;