Hostname: page-component-cc8bf7c57-hbs24 Total loading time: 0 Render date: 2024-12-11T23:06:54.123Z Has data issue: false hasContentIssue false
  • English
  • Français

Greedy approximation

Published online by Cambridge University Press:  25 April 2008

V. N. Temlyakov
V. N. Temlyakov
Affiliation:
University of South Carolina, Columbia, 29208, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this survey we discuss properties of specific methods of approximation that belong to a family of greedy approximation methods (greedy algorithms). It is now well understood that we need to study nonlinear sparse representations in order to significantly increase our ability to process (compress, denoise, etc.) large data sets. Sparse representations of a function are not only a powerful analytic tool but they are utilized in many application areas such as image/signal processing and numerical computation. The key to finding sparse representations is the concept of m-term approximation of the target function by the elements of a given system of functions (dictionary). The fundamental question is how to construct good methods (algorithms) of approximation. Recent results have established that greedy-type algorithms are suitable methods of nonlinear approximation in both m-term approximation with regard to bases, and m-term approximation with regard to redundant systems. It turns out that there is one fundamental principle that allows us to build good algorithms, both for arbitrary redundant systems and for very simple well-structured bases, such as the Haar basis. This principle is the use of a greedy step in searching for a new element to be added to a given m-term approximant.

Type
Research Article
Information
Acta Numerica , Volume 17 , May 2008 , pp. 235 - 409
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Barron, A. R. (1993), ‘Universal approximation bounds for superposition of n sigmoidal functions’, IEEE Trans. Inform. Theory 39, 930–945.CrossRefGoogle Scholar
Barron, A., Cohen, A., Dahmen, W. and DeVore, R. (2005), Approximation and learning by greedy algorithms. Manuscript.Google Scholar
Baishanski, B. M. (1983), ‘Approximation by polynomials of given length’, Illinois J. Math. 27, 449–458.CrossRefGoogle Scholar
Bary, N. K. (1961), Trigonometric Series, Nauka, Moscow (in Russian). English translation: Pergamon Press, Oxford (1964).Google Scholar
Beck, J. and Chen, W. (1987), Irregularities of Distribution, Cambridge University Press.CrossRefGoogle Scholar
Bednorz, W. (2006), Greedy bases are best for m-term approximation. Manuscript.Google Scholar
Birman, M. S. and Solomyak, M. Z. (1977), ‘Estimates of singular numbers of integral operators’, Uspekhi Mat. Nauk 32, 17–84. English translation in Russian Math. Surveys 32 (1977).Google Scholar
Bourgain, J. (1992), ‘A remark on the behaviour of L p-multipliers and the range of operators acting on L p-spaces’, Israel J. Math. 79, 193–206.Google Scholar
Candèes, E. (2006), Compressive sampling. In Proc. International Congress of Mathematics (Madrid 2006), Vol. 3, pp. 1433–1452.Google Scholar
Candèes, E., Romberg, J. and Tao, T. (2006), ‘Stable signal recovery from incomplete and inaccurate measurements’, Comm. Pure Appl. Math. 59, 1207–1223.CrossRefGoogle Scholar
Candèes, E. and Tao, T. (2005), ‘Decoding by linear programming’, IEEE Trans. Inform. Theory 51, 4203–4215.CrossRefGoogle Scholar
Carl, B. (1981), ‘Entropy numbers, s-numbers, and eigenvalue problems’, J. Funct. Anal. 41, 290–306.CrossRefGoogle Scholar
Chen, S. S., Donoho, D. L. and Saunders, M. A. (2001), ‘Atomic decomposition by basis pursuit’, SIAM Review 43, 129–159.CrossRefGoogle Scholar
Cochran, J. A. (1977), ‘Composite integral operators and nuclearity’, Ark. Mat. 15, 215–222.CrossRefGoogle Scholar
Cohen, A., DeVore, R. A. and Hochmuth, R. (2000), ‘Restricted nonlinear approximation’, Constr. Approx. 16, 85–113.Google Scholar
Cohen, A., Dahmen, W. and DeVore, R. (2007), Compressed sensing and k-term approximation. Manuscript.Google Scholar
Coifman, R. R. and Wickerhauser, M. V. (1992), ‘Entropy-based algorithms for best-basis selection’, IEEE Trans. Inform. Theory 38, 713–718.CrossRefGoogle Scholar
Cordoba, A. and Fernandez, P. (1998), ‘Convergence and divergence of decreasing rearranged Fourier series’, SIAM J. Math. Anal. 29, 1129–1139.Google Scholar
Cucker, F. and Smale, S. (2001), ‘On the mathematical foundations of learning’, Bull. Amer. Math. Soc. 39, 1–49.Google Scholar
Davis, G., Mallat, S. and Avellaneda, M. (1997), ‘Adaptive greedy approximations’, Constr. Approx. 13, 57–98.CrossRefGoogle Scholar
DeVore, R. A. (1998), Nonlinear approximation. In Acta Numerica, Vol. 7, Cambridge University Press, pp. 51–150.Google Scholar
DeVore, R. A. (2006), Optimal computation. In Proc. International Congress of Mathematics (Madrid 2006), Vol. 1, pp. 187–215.Google Scholar
DeVore, R., Jawerth, B. and Popov, V. (1992), ‘Compression of wavelet decompositions’, Amer. J. Math. 114, 737–785.CrossRefGoogle Scholar
DeVore, R., Kerkyacharian, G., Picard, D. and Temlyakov, V. (2004), On mathematical methods of learning. IMI Preprint 10, Department of Mathematics, University of South Carolina.Google Scholar
DeVore, R., Kerkyacharian, G., Picard, D. and Temlyakov, V. (2006), ‘Mathematical methods for supervised learning’, Found. Comput. Math. 6, 3–58.CrossRefGoogle Scholar
DeVore, R. A., Konyagin, S. V. and Temlyakov, V. N. (1998), ‘Hyperbolic wavelet approximation’, Constr. Approx. 14, 1–26.Google Scholar
DeVore, R. A. and Lorenz, G. G. (1993), Constructive Approximation, Springer, Berlin.CrossRefGoogle Scholar
DeVore, R., Petrova, G. and Temlyakov, V. N. (2003), ‘Best basis selection for approximation in Lp’, Found. Comput. Math. 3, 161–185.Google Scholar
DeVore, R. A. and Popov, V. A. (1988), Interpolation spaces and non-linear approximation. In Function Spaces and Approximation, Vol. 1302 of Lecture Notes in Mathematics, Springer, pp. 191–205.CrossRefGoogle Scholar
DeVore, R. A. and Temlyakov, V. N. (1995), ‘Nonlinear approximation by trigonometric sums’, J. Fourier Anal. Appl. 2, 29–48.Google Scholar
DeVore, R. A. and Temlyakov, V. N. (1996), ‘Some remarks on greedy algorithms’, Adv. Comput. Math. 5, 173–187.CrossRefGoogle Scholar
DeVore, R. A. and Temlyakov, V. N. (1997), ‘Nonlinear approximation in finite dimensional spaces’, J. Complexity 13, 489–508.CrossRefGoogle Scholar
Dilworth, S. J., Kalton, N. J. and Kutzarova, D. (2003), ‘On the existence of almost greedy bases in Banach spaces’, Studia Math. 158, 67–101.CrossRefGoogle Scholar
Dilworth, S. J., Kalton, N. J., Kutzarova, D. and Temlyakov, V. N. (2003), ‘The thresholding greedy algorithm, greedy bases, and duality’, Constr. Approx. 19, 575–597.Google Scholar
Dilworth, S., Kutzarova, D. and Temlyakov, V. (2002), ‘Convergence of some greedy algorithms in Banach spaces’, J. Fourier Anal. Appl. 8, 489–505.CrossRefGoogle Scholar
Dilworth, S. J., Kutzarova, D. and Wojtaszczyk, P. (2002), ‘On approximate l 1 systems in Banach spaces’, J. Approx. Theory 114, 214–241.Google Scholar
Donahue, M., Gurvits, L., Darken, C. and Sontag, E. (1997), ‘Rate of convex approximation in non-Hilbert spaces’, Constr. Approx. 13, 187–220.CrossRefGoogle Scholar
Donoho, D. L. (1993), ‘Unconditional bases are optimal bases for data compression and for statistical estimation’, Appl. Comput. Harmon. Anal. 1, 100–115.Google Scholar
Donoho, D. L. (1997), ‘CART and best-ortho-basis: A connection’, Ann. Statist. 25, 1870–1911.CrossRefGoogle Scholar
Donoho, D. L. (2001), ‘Sparse components of images and optimal atomic decompositions’, Constr. Approx. 17, 353–382.CrossRefGoogle Scholar
Donoho, D. (2006), ‘Compressed sensing’, IEEE Trans. Inform. Theory 52, 1289–1306.Google Scholar
Donoho, D., Elad, M. and Temlyakov, V. N. (2006), ‘Stable recovery of sparse overcomplete representations in the presence of noise’, IEEE Trans. Inform. Theory 52, 6–18.Google Scholar
Donoho, D., Elad, M. and Temlyakov, V. N. (2007), ‘On the Lebesgue type inequalities for greedy approximation’, J. Approx. Theory 147, 185–195.CrossRefGoogle Scholar
Donoho, D. and Johnstone, I. (1994), ‘Ideal spatial adaptation via wavelet shrink age’, Biometrica 81, 425–455.CrossRefGoogle Scholar
Dubinin, V. V. (1997), Greedy algorithms and applications. PhD Thesis, University of South Carolina.Google Scholar
Fefferman, C. and Stein, E. (1972), ‘Hp spaces of several variables’, Acta Math. 129, 137–193.CrossRefGoogle Scholar
Figiel, T., Johnson, W. B. and Schechtman, G. (1988), ‘Factorization of natural embeddings of into Lr I’, Studia Math. 89, 79–103.CrossRefGoogle Scholar
Frazier, M. and Jawerth, B. (1990), ‘A discrete transform and decomposition of distribution spaces’, J. Funct. Anal. 93, 34–170.CrossRefGoogle Scholar
Fredholm, I. (1903), ‘Sur une classe d'éequations fonctionelles’, Acta Math. 27, 365–390.CrossRefGoogle Scholar
Friedman, J. H. and Stuetzle, W. (1981), ‘Projection pursuit regression’, J. Amer. Statist. Assoc. 76, 817–823.Google Scholar
Galatenko, V. V. and Livshitz, E. D. (2003), ‘On convergence of approximate weak greedy algorithms’, East J. Approx. 9, 43–49.Google Scholar
Galatenko, V. V. and Livshitz, E. D. (2005), ‘Generalized approximate weak greedy algorithms’, Math. Notes 78, 170–184.CrossRefGoogle Scholar
Ganichev, M. and Kalton, N. J. (2003), ‘Convergence of the weak dual greedy algorithm in Lp-spaces’, J. Approx. Theory 124, 89–95.CrossRefGoogle Scholar
Garnaev, A. and Gluskin, E. (1984), ‘The widths of a Euclidean ball’, Dokl. Akad. Nauk USSR 277, 1048–1052. English translation in Soviet Math. Dokl. 30, 200–204.Google Scholar
Gilbert, A. C., Muthukrishnan, S. and Strauss, M. J. (2003), Approximation of functions over redundant dictionaries using coherence. In Proc. 14th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 243–252.Google Scholar
Gogyan, S. (2005), ‘Greedy algorithm with regard to Haar subsystems’, East J. Approx. 11, 221–236.Google Scholar
Gogyan, S. (2006), On convergence of weak thresholding greedy algorithm in L 1(0, 1). Manuscript.Google Scholar
Gribonval, R. and Nielsen, M. (2001 a), ‘Approximate weak greedy algorithms’, Adv. Comput. Math. 14, 361–368.CrossRefGoogle Scholar
Gribonval, R. and Nielsen, M. (2001 b), ‘Some remarks on non-linear approximation with Schauder bases’, East J. Approx. 7, 267–285.Google Scholar
Habala, P., Háajek, P. and Zizler, V. (1996), Introduction to Banach Spaces, Vol. I, Matfyzpress, Univerzity Karlovy.Google Scholar
Heinrich, S., Novak, E., Wasilkowski, G. and Wozniakowski, H. (2001), ‘The inverse of the star-discrepancy depends linearly on the dimension’, Acta Arith. 96, 279–302.CrossRefGoogle Scholar
Hille, E. and Tamarkin, J. D. (1931), ‘On the characteristic values of linear integral equations’, Acta Math. 57, 1–76.CrossRefGoogle Scholar
Huber, P. J. (1985), ‘Projection pursuit’, Ann. Statist. 13, 435–475.Google Scholar
Jones, L. (1987), ‘On a conjecture of Huber concerning the convergence of projection pursuit regression’, Ann. Statist. 15, 880–882.Google Scholar
Jones, L. (1992), ‘A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training’, Ann. Statist. 20, 608–613.CrossRefGoogle Scholar
Kalton, N. J., Beck, N. T. and Roberts, J. W. (1984), An F-Space Sampler, Vol. 5 of London Math. Soc. Lecture Notes, Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Kamont, A. and Temlyakov, V. N. (2004), ‘Greedy approximation and the multivariate Haar system’, Studia Math. 161, 199–223.CrossRefGoogle Scholar
Kashin, B. S. (1977), ‘Widths of certain finite-dimensional sets and classes of smooth functions’, Izv. Akad. Nauk SSSR, Ser. Mat. 41, 334–351. English translation in Math. USSR IZV. 11.Google Scholar
Kashin, B. S. (1985), ‘On approximation properties of complete orthonormal systems’, Tr. Mat. Inst. Steklova 172, 187–191. English translation in Proc. Steklov Inst. Math. 3, 207–211.Google Scholar
Kashin, B. S. and Temlyakov, V. N. (2007), A remark on compressed sensing. Manuscript.CrossRefGoogle Scholar
Kerkyacharian, G. and Picard, D. (2004), ‘Entropy, universal coding, approximation, and bases properties’, Constr. Approx. 20, 1–37.CrossRefGoogle Scholar
Kerkyacharian, G., Picard, D. and Temlyakov, V. N. (2006), ‘Some inequalities for the tensor product of greedy bases and weight-greedy bases’, East J. Approx. 12, 103–118.Google Scholar
Konyagin, S. V. and Skopina, M. A. (2001), ‘Comparison of the L 1-norms of total and truncated exponential sums’, Mat. Zametki 69, 699–707.Google Scholar
Konyagin, S. V. and Temlyakov, V. N. (1999 a), ‘A remark on greedy approximation in Banach spaces’, East J. Approx. 5, 1–15.Google Scholar
Konyagin, S. V. and Temlyakov, V. N. (1999 b), ‘Rate of convergence of pure greedy algorithms’, East J. Approx. 5, 493–499.Google Scholar
Konyagin, S. V. and Temlyakov, V. N. (2002), ‘Greedy approximation with regard to bases and general minimal systems’, Serdica Math. J. 28, 305–328.Google Scholar
Konyagin, S. V. and Temlyakov, V. N. (2003 a), ‘Convergence of greedy approximation I: General systems’, Studia Math. 159, 143–160.Google Scholar
Konyagin, S. V. and Temlyakov, V. N. (2003 b), ‘Convergence of greedy approximation II: The trigonometric system’, Studia Math. 159, 161–184.Google Scholar
Konyagin, S. V. and Temlyakov, V. N. (2004), Some error estimates in learning theory. In Approximation Theory: A Volume Dedicated to Borislav Bojanov, Marin Drinov Academy Publishing House, Sofia, pp. 126–144.Google Scholar
Konyagin, S. V. and Temlyakov, V. N. (2005), ‘Convergence of greedy approximation for the trigonometric system’, Anal. Math. 31, 85–115.Google Scholar
Konyagin, S. V. and Temlyakov, V. N. (2007), ‘The entropy in learning theory: Error estimates’, Constr. Approx. 25, 1–27.CrossRefGoogle Scholar
Körner, T. W. (1996), ‘Divergence of decreasing rearranged Fourier series’, Ann. of Math. 144, 167–180.CrossRefGoogle Scholar
Körner, T. W. (1999), ‘Decreasing rearranged Fourier series’, J. Fourier Anal. Appl. 5, 1–19.CrossRefGoogle Scholar
Lebesgue, H. (1909), ‘Sur les intéegrales singulièeres’, Ann. Fac. Sci. Univ. Toulouse (3) 1, 25–117.Google Scholar
Lee, W. S., Bartlett, P. L. and Williamson, R. C. (1996), ‘Efficient agnostic learning of neural networks with bounded fan-in’, IEEE Trans. Inform. Theory 42, 2118–2132.Google Scholar
Leviatan, D. and Temlyakov, V. N. (2005), ‘Simultaneous greedy approximation in Banach spaces’, J. Complexity 21, 275–293.CrossRefGoogle Scholar
Leviatan, D. and Temlyakov, V. N. (2006), ‘Simultaneous approximation by greedy algorithms’, Adv. Comput. Math. 25, 73–90.Google Scholar
Lindenstrauss, J. and Tzafriri, L. (1977), Classical Banach Spaces, Vol. I, Springer, Berlin.CrossRefGoogle Scholar
Livshitz, E. D. (2003), ‘Convergence of greedy algorithms in Banach spaces’, Math. Notes 73, 342–368.CrossRefGoogle Scholar
Livshitz, E. D. (2006), ‘On the recursive greedy algorithm’, Izv. RAN. Ser. Mat. 70, 95–116.Google Scholar
Livshitz, E. D. (2007 a), ‘Optimality of the greedy algorithm for some function classes’, Mat. Sb. 198, 95–114.Google Scholar
Livshitz, E. D. (2007 b), On lower estimates of rate of convergence of greedy algorithms. Manuscript.Google Scholar
Livshitz, E. D. and Temlyakov, V. N. (2001), ‘On the convergence of weak greedy algorithms’, Tr. Mat. Inst. Steklova 232, 236–247.Google Scholar
Livshitz, E. D. and Temlyakov, V. N. (2003), ‘Two lower estimates in greedy approximation’, Constr. Approx. 19, 509–523.CrossRefGoogle Scholar
Lutoborski, A. and Temlyakov, V. N. (2003), ‘Vector greedy algorithms’, J. Complexity 19, 458–473.Google Scholar
Maiorov, V. E., Oskolkov, K. I. and Temlyakov, V. N. (2002), Gridge approximations and Radon compass. In Approximation Theory: A Volume Dedicated to Blagovest Sendov, DARBA, Sofia, pp. 284–309.Google Scholar
Mallat, S. and Zhang, Z. (1993), ‘Matching pursuit in a time-frequency dictionary’, IEEE Trans. Signal Proc. 41, 3397–3415.CrossRefGoogle Scholar
Needell, D. and Vershynin, R. (2007), Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit. Manuscript.CrossRefGoogle Scholar
Niederreiter, H., Tichy, R. F. and Turnwald, G. (1990), ‘An inequality for differences of distribution functions’, Arch. Math. 54, 166–172.CrossRefGoogle Scholar
Nielsen, M. (2006), Trigonometric quasi-greedy bases for L p(𝕋;w). Manuscript.Google Scholar
Nikol'skii, S. N. (1975), Approximation of Functions of Several Variables and Embedding Theorems, Springer.CrossRefGoogle Scholar
Oswald, P. (2001), ‘Greedy algorithms and best m-term approximation with respect to biorthogonal systems’, J. Fourier Anal. Appl. 7, 325–341.CrossRefGoogle Scholar
Petrushev, P. (1988), Direct and converse theorems for spline and rational approximation and Besov spaces. In Function Spaces and Applications, Vol. 1302 of Lecture Notes in Mathematics, pp. 363–377.CrossRefGoogle Scholar
Poggio, T. and Smale, S. (2003), ‘The mathematics of learning: Dealing with data’, Notices Amer. Math. Soc., 50, 537–544.Google Scholar
Schmidt, E. (1906), ‘Zur Theorie der linearen und nichtlinearen Integralgleichungen I’, Math. Annalen 63, 433–476.CrossRefGoogle Scholar
Sil'nichenko, A. V. (2004), ‘Rate of convergence of greedy algorithms’, Mat. Zametki 76, 628–632.Google Scholar
Smithies, F. (1937), ‘The eigen-values and singular values of integral equations’, Proc. London Math. Soc. (2) 43, 255–279.Google Scholar
Stromberg, T. and Heath, R. Jr. (2003), ‘Grassmannian frames with applications to coding and communications’, Appl. Comput. Harm. Anal. 14, 257–275.Google Scholar
Temlyakov, V. N. (1988), ‘Approximation by elements of a finite dimensional subspace of functions from various Sobolev or Nikol'skii spaces’, Matem. Zametki 43, 770–786. English translation in Math. Notes 43, 444–454.Google Scholar
Temlyakov, V. N. (1989 a), ‘Approximation of functions with bounded mixed derivative’, Proc. Steklov Inst. 1, 1–122.Google Scholar
Temlyakov, V. N. (1989 b) ‘Estimates of the best bilinear approximations of functions of two variables and some of their applications’, Math. USSR Sb. 62, 95–109.Google Scholar
Temlyakov, V. N. (1990), ‘Bilinear approximation and applications’, Proc. Steklov Inst. Math. 3, 221–248.Google Scholar
Temlyakov, V. N. (1992 a), ‘On estimates of approximation numbers and best bilinear approximation’, Constr. Approx. 8, 23–33.CrossRefGoogle Scholar
Temlyakov, V. N. (1992 b), ‘Estimates of best bilinear approximations of functions and approximation numbers of integral operators’, Math. Notes 51, 510–517.CrossRefGoogle Scholar
Temlyakov, V. N. (1993 b), ‘Bilinear approximation and related questions’, Proc. Steklov Inst. Math. 4, 245–265.Google Scholar
Temlyakov, V. N. (1998 a), ‘The best m-term approximation and greedy algorithms’, Adv. Comput. Math. 8, 249–265.Google Scholar
Temlyakov, V. N. (1998 b), ‘Nonlinear m-term approximation with regard to the multivariate Haar system’, East J. Approx. 4, 87–106.Google Scholar
Temlyakov, V. N. (1998 c), ‘Greedy algorithm and m-term trigonometric approximation’, Constr. Approx. 14, 569–587.Google Scholar
Temlyakov, V. N. (1999), ‘Greedy algorithms and m-term approximation with regard to redundant dictionaries’, J. Approx. Theory 98, 117–145.CrossRefGoogle Scholar
Temlyakov, V. N. (2000 a), ‘Greedy algorithms with regard to multivariate systems with special structure’, Constr. Approx. 16, 399–425.CrossRefGoogle Scholar
Temlyakov, V. N. (2000 b), ‘Weak greedy algorithms’, Adv. Comput. Math. 12, 213–227.CrossRefGoogle Scholar
Temlyakov, V. N. (2001 a), Lecture notes on approximation theory, Chapter I, University of South Carolina, pp. 1–20.Google Scholar
Temlyakov, V. N. (2001 b), ‘Greedy algorithms in Banach spaces’, Adv. Comput. Math. 14, 277–292.Google Scholar
Temlyakov, V. N. (2002 a), ‘Universal bases and greedy algorithms for anisotropic function classes’, Constr. Approx. 18, 529–550.CrossRefGoogle Scholar
Temlyakov, V. N. (2002 b), ‘A criterion for convergence of weak greedy algorithms’, Adv. Comput. Math. 17, 269–280.Google Scholar
Temlyakov, V. N. (2002 c), Nonlinear approximation with regard to bases. In Approximation Theory X, Vanderbilt University Press, Nashville, TN, pp. 373–402.Google Scholar
Temlyakov, V. N. (2003 a), ‘Nonlinear methods of approximation’, Found. Comput. Math. 3, 33–107.CrossRefGoogle Scholar
Temlyakov, V. N. (2003 b), ‘Cubature formulas, discrepancy, and nonlinear approximation’, J. Complexity 19, 352–391.CrossRefGoogle Scholar
Temlyakov, V. N. (2004), ‘A remark on simultaneous greedy approximation’, East J. Approx. 10, 17–25.Google Scholar
Temlyakov, V. N. (2005 a), ‘Greedy type algorithms in Banach spaces and applications’, Constr. Approx. 21, 257–292.CrossRefGoogle Scholar
Temlyakov, V. N. (2005 b), ‘Greedy algorithms with restricted depth search’, Proc. Steklov Inst. Math. 248, 255–267.Google Scholar
Temlyakov, V. N. (2005 c), Approximation in learning theory. IMI Preprint 05, Department of Mathematics, University of South Carolina.Google Scholar
Temlyakov, V. N. (2005 d), On universal estimators in learning theory. IMI Preprint 17, Department of Mathematics, University of South Carolina.Google Scholar
Temlyakov, V. N. (2006 a), Greedy approximations. In Foundations of Computational Mathematics: Santander 2005, Vol. 331 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 371–394.CrossRefGoogle Scholar
Temlyakov, V. N. (2006 b), Greedy approximations with regard to bases. In Proc. International Congress of Mathematics (Madrid 2006), Vol. 2, pp. 1479–1504.Google Scholar
Temlyakov, V. N. (2006 c), Relaxation in greedy approximation. IMI Preprint 03, Department of Mathematics, University of South Carolina.Google Scholar
Temlyakov, V. N. (2006 d), ‘Optimal estimators in learning theory’, Approximation and Probability, Banach Center Publications, 72, 341–366.CrossRefGoogle Scholar
Temlyakov, V. N. (2007 a), ‘Greedy expansions in Banach spaces’, Adv. Comput. Math. 26, 431–449.CrossRefGoogle Scholar
Temlyakov, V. N. (2007 b), ‘Greedy algorithms with prescribed coefficients’, J. Fourier Anal. Appl. 13, 71–86.Google Scholar
Traub, J. F., Wasilkowski, G. W. and Wozniakowski, H. (1988), Information-Based Complexity, Academic Press, New York.Google Scholar
Tropp, J. A. (2004), ‘Greed is good: Algorithmic results for sparse approximation’, IEEE Trans. Inform. Theory 50, 2231–2242.CrossRefGoogle Scholar
Tropp, J. A. and Gilbert, A. C. (2005), Signal recovery from partial information via orthogonal matching pursuit. Preprint, University of Michigan.Google Scholar
Wojtaszczyk, P. (1997), ‘On unconditional polynomial bases in L p and Bergman spaces’, Constr. Approx. 13, 1–15.Google Scholar
Wojtaszczyk, P. (2000), ‘Greedy algorithms for general systems’, J. Approx. Theory 107, 293–314.CrossRefGoogle Scholar
Wojtaszczyk, P. (2002 a), Greedy type bases in Banach spaces. In Constructive Function Theory, DARBA, Sofia, pp. 1–20.Google Scholar
Wojtaszczyk, P. (2002 b), ‘Existence of best m-term approximation’, Functiones et Approximatio XXX, 127–133.Google Scholar
Wojtaszczyk, P. (2006), ‘Greediness of the Haar system in rearrangement invariant spaces’, Banach Center Publications 72, 385–395.CrossRefGoogle Scholar
Weyl, H. (1911), ‘Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen’, Math. Ann. 71, 441–479.CrossRefGoogle Scholar
Zygmund, A. (1959), Trigonometric Series, Cambridge University Press.Google Scholar