Entropy and Sampling Numbers of Classes of Ridge Functions

详细信息    查看全文

• 作者：Sebastian Mayer ; Tino Ullrich ; Jan Vybíral
• 关键词：Ridge functions ; Sampling numbers ; Entropy numbers ; Rate of convergence ; Information ; based complexity ; Curse of dimensionality ; 41A10 ; 41A25 ; 41A50 ; 41A63 ; 46E35 ; 65D05 ; 65D15
• 刊名：Constructive Approximation
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：42
• 期：2
• 页码：231-264
• 全文大小：636 KB
• 参考文献：1.Bühlmann, P., van de Geer, S.: Statistics for High-Dimensional Data. Springer, Heidelberg (2011)CrossRef MATH
  2.Buhmann, M.D., Pinkus, A.: Identifying linear combinations of ridge functions. Adv. Appl. Math. 22, 103-18 (1999)MathSciNet CrossRef MATH
  3.Candés, E.J.: Harmonic analysis of neural networks. Appl. Comput. Harmon. Anal. 6, 197-18 (1999)MathSciNet CrossRef MATH
  4.Candés, E.J., Donoho, D.L.: Ridgelets: a key to higher-dimensional intermittency? Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 357, 2495-509 (1999)CrossRef MATH
  5.Carl, B., Stefani, I.: Entropy, Compactness and the Approximation of Operators. Cambridge Tracts in Mathematics, vol. 98. Cambridge University Press, Cambridge (1990)CrossRef
  6.Cohen, A., Daubechies, I., DeVore, R.A., Kerkyacharian, G., Picard, D.: Capturing ridge functions in high dimensions from point queries. Constr. Approx. 35, 225-43 (2012)MathSciNet CrossRef MATH
  7.Creutzig, J., Dereich, S., Müller-Kronbach, T., Ritter, K.: Infinite-dimensional quadrature and approximation of distributions. Found. Comput. Math. 9, 391-29 (2009)MathSciNet CrossRef MATH
  8.Cucker, F., Zhou, D.-X.: Learning theory: an approximation theory viewpoint. Cambridge Monographs on Applied and Computational Mathematics, vol. 24. Cambridge University Press, Cambridge (2007)
  9.DeVore, R.A., Lorentz, G.G.: Constructive Approximation. Springer, Berlin (1993)CrossRef MATH
  10.Edmunds, D.E., Triebel, H.: Function Spaces, Entropy Numbers, Differential Operators. Cambridge Tracts in Mathematics, vol. 120. Cambridge University Press, Cambridge (1996)CrossRef
  11.Flad, H.J., Hackbusch, W., Khoromskij, B.N., Schneider, R.: Concepts of data-sparse tensor-product approximation in many-particle modeling. In: Olshevsky, V., Tyrtyshnikov, E. (eds.) Matrix Methods: Theory, Algorithms and Applications. World Scientific, Singapore (2010)
  12.Fornasier, M., Schnass, K., Vybíral, J.: Learning functions of few arbitrary linear parameters in high dimensions. Found. Comput. Math. 12, 229-62 (2012)MathSciNet CrossRef MATH
  13.Foucart, S., Pajor, A., Rauhut, H., Ullrich, T.: The Gelfand widths of lp-balls for \(0 < p\le 1\) . J. Complexity 26, 629-40 (2010)MathSciNet CrossRef MATH
  14.Friedman, J.H., Stuetzle, W.: Projection pursuit regression. J. Am. Stat. Assoc. 76, 817-23 (1981)MathSciNet CrossRef
  15.Golubev, G.K.: Asymptotically minimax estimation of a regression function in an additive model. Problemy Peredachi Informatsii 28, 101-12 (1992)MathSciNet
  16.Graham, R., Sloane, N.: Lower bounds for constant weight codes. IEEE Trans. Inform. Theory 26, 37-3 (1980)MathSciNet CrossRef MATH
  17.Hastie, T., Tibshirani, R., Friedman, J.: The elements of statistical learning. Springer, New York (2001)CrossRef MATH
  18.Hinrichs, A., Mayer, S.: Entropy numbers of spheres in Banach and quasi-Banach spaces. University of Bonn, preprint
  19.Hinrichs, A., Novak, E., Ullrich, M., Wo?niakowski, H.: The curse of dimensionality for numerical integration of smooth functions II. J. Complex. 30, 117-43 (2014)CrossRef MATH
  20.Hristache, M., Juditsky, A., Spokoiny, V.: Direct estimation of the index coefficient in a single-index model. Ann. Stat. 29, 595-23 (2001)MathSciNet CrossRef MATH
  21.Kühn, T.: A lower estimate for entropy numbers. J. Approx. Theory 110, 120-24 (2001)MathSciNet CrossRef MATH
  22.Logan, B.P., Shepp, L.A.: Optimal reconstruction of a function from its projections. Duke Math. J. 42, 645-59 (1975)MathSciNet CrossRef MATH
  23.Lorentz, G., von Golitschek, M., Makovoz, Y.: Constructive Approximation: Advanced Problems. Volume 304 of Grundlehren der Mathematischen Wissenschaften, Springer, Berlin (1996)
  24.Maiorov, V.: Geometric properties of the ridge manifold. Adv. Comput. Math. 32, 239-53 (2010)MathSciNet CrossRef MATH
  25.Novak, E., Triebel, H.: Function spaces in Lipschitz domains and optimal rates of convergence for sampling. Constr. Approx. 23, 325-50 (2006)MathSciNet CrossRef MATH
  26.Novak, E., Wo?niakowski, H.: Tractability of Multivariate Problems, Volume I: Linear Information. EMS Tracts in Mathematics, vol. 6, Eur. Math. Soc. Publ. House, Zürich (2008)
  27.Novak, E., Wo?niakowski, H.: Approximation of infinitely differentiable multivariate functions is intractable. J. Complex. 25, 398-04 (2009)CrossRef MATH
  28.Novak, E., Wo?niakowski, H.: Tractability of Multivariate Problems, Volume II: Standard Information for Functionals. EMS Tracts in Mathematics, vol. 12, Eur. Math. Soc. Publ. House, Zürich (2010)
  29.Paskov, S., Traub, J.: Faster evaluation of financial derivatives. J. Portf. Manag. 22, 113-20 (1995)CrossRef
  30.Pinkus, A.: Approximating by ridge functions. In: Le Méhauté, A., Rabut, C., Schumaker, L.L. (eds.) Surface Fitting and Multiresolution Methods, pp. 279-92. Vanderbilt University Press, Nashville (1997)
  31.Pinkus, A.: Approximation theory of the MLP model in neural networks. A
• 作者单位：Sebastian Mayer (1)
  Tino Ullrich (1)
  Jan Vybíral (2)
  
  1. Hausdorff-Center for Mathematics, Endenicher Allee 62, 53115, Bonn, Germany
  2. Department of Mathematical Analysis, Charles University, Sokolovska 83, 186 00, Prague 8, Czech Republic
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Numerical Analysis
  Analysis
  
• 出版者：Springer New York
• ISSN：1432-0940

文摘

We study the properties of ridge functions \(f(x)=g(a\cdot x)\) in high dimensions \(d\) from the viewpoint of approximation theory. The function classes considered consist of ridge functions such that the profile \(g\) is a member of a univariate Lipschitz class with smoothness \(\alpha >0\) (including infinite smoothness) and the ridge direction \(a\) has \(p\)-norm \(\Vert a\Vert _p\le 1\). First, we investigate entropy numbers in order to quantify the compactness of these ridge function classes in \(L_{\infty }\). We show that they are essentially as compact as the class of univariate Lipschitz functions. Second, we examine sampling numbers and consider two extreme cases. In the case \(p=2\), sampling ridge functions on the Euclidean unit ball suffers from the curse of dimensionality. Moreover, it is as difficult as sampling general multivariate Lipschitz functions, which is in sharp contrast to the result on entropy numbers. When we additionally assume that all feasible profiles have a first derivative uniformly bounded away from zero at the origin, the complexity of sampling ridge functions reduces drastically to the complexity of sampling univariate Lipschitz functions. In between, the sampling problem’s degree of difficulty varies, depending on the values of \(\alpha \) and \(p\). Surprisingly, we see almost the entire hierarchy of tractability levels as introduced in the recent monographs by Novak and Wo?niakowski. Keywords Ridge functions Sampling numbers Entropy numbers Rate of convergence Information-based complexity Curse of dimensionality