Geodesic
Greedy approximation of characteristic functions
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Function theory and differential equations, Tome 269 (2010), pp. 254-264.

Voir la notice de l'article provenant de la source Math-Net.Ru

We discuss the problem of sparse representation of domains in $\mathbb R^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 $\mathbb R^2$. 
@article{TM_2010_269_a20,
     author = {V. N. Temlyakov},
     title = {Greedy approximation of characteristic functions},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {254--264},
     publisher = {mathdoc},
     volume = {269},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/TM_2010_269_a20/}
}
TY  - JOUR
AU  - V. N. Temlyakov
TI  - Greedy approximation of characteristic functions
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2010
SP  - 254
EP  - 264
VL  - 269
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TM_2010_269_a20/
LA  - en
ID  - TM_2010_269_a20
ER  - 
%0 Journal Article
%A V. N. Temlyakov
%T Greedy approximation of characteristic functions
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2010
%P 254-264
%V 269
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TM_2010_269_a20/
%G en
%F TM_2010_269_a20
V. N. Temlyakov. Greedy approximation of characteristic functions. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Function theory and differential equations, Tome 269 (2010), pp. 254-264. http://geodesic.mathdoc.fr/item/TM_2010_269_a20/

[1] Carl B., “Entropy numbers, $s$-numbers, and eigenvalue problems”, J. Funct. Anal., 41 (1981), 290–306 | DOI | MR | Zbl

[2] Dudley R.M., “Metric entropy of some classes of sets with differentiable boundaries”, J. Approx. Theory, 10 (1974), 227–236 | DOI | MR | Zbl

[3] Donahue M.J., Gurvits L., Darken C., Sontag E., “Rates of convex approximation in non-Hilbert spaces”, Constr. Approx., 13 (1997), 187–220 | DOI | MR | Zbl

[4] DeVore R.A., Temlyakov V.N., “Nonlinear approximation by trigonometric sums”, J. Fourier Anal. and Appl., 2 (1995), 29–48 | DOI | MR | Zbl

[5] DeVore R.A., Temlyakov V.N., “Some remarks on greedy algorithms”, Adv. Comput. Math., 5 (1996), 173–187 | DOI | MR | Zbl

[6] Kashin B.S., “Ob approksimatsionnykh svoistvakh polnykh ortonormirovannykh sistem”, Tr. MIAN, 172, 1985, 187–191 | MR | Zbl

[7] Kashin B.S., Temlyakov V.N., “O nailuchshikh $m$-chlennykh priblizheniyakh i entropii mnozhestv v prostranstve $L^1$”, Mat. zametki, 56:5 (1994), 57–86 | MR | Zbl

[8] Lorentz G.G., “Metric entropy and approximation”, Bull. Amer. Math. Soc., 72 (1966), 903–937 | DOI | MR | Zbl

[9] Lorentz G.G., von Golitschek M., Makovoz Y., Constructive approximation: Advanced problems, Springer, Berlin, 1996 | MR | Zbl

[10] Lindenstrauss J., Tzafriri L., Classical Banach spaces, v. 1, Sequence spaces, Springer, Berlin, 1977 | MR | Zbl

[11] Temlyakov V.N., “Nelineinye poperechniki po Kolmogorovu”, Mat. zametki, 63:6 (1998), 891–902 | DOI | MR | Zbl

[12] Temlyakov V.N., “Weak greedy algorithms”, Adv. Comput. Math., 12 (2000), 213–227 | DOI | MR | Zbl

[13] Temlyakov V.N., “Greedy algorithms in Banach spaces”, Adv. Comput. Math., 14 (2001), 277–292 | DOI | MR | Zbl

[14] Temlyakov V.N., “Relaxation in greedy approximation”, Constr. Approx., 28 (2008), 1–25 | DOI | MR | Zbl

[15] Temlyakov V.N., “Greedy algorithms with regard to multivariate systems with special structure”, Constr. Approx., 16 (2000), 399–425 | DOI | MR | Zbl

[16] Temlyakov V.N., “Universal bases and greedy algorithms for anisotropic function classes”, Constr. Approx., 18 (2002), 529–550 | DOI | MR | Zbl

[17] Temlyakov V.N., “Greedy approximation”, Acta numer., 17 (2008), 235–409 | DOI | MR | Zbl