Kühn, Thomas; Sickel, Winfried; Ullrich, Tino Approximation numbers of Sobolev embeddings-sharp constants and tractability. (English) Zbl 1334.47028 J. Complexity 30, No. 2, 95-116 (2014). Authors’ abstract: We investigate optimal linear approximations (approximation numbers) in the context of periodic Sobolev spaces \(H^s(T^d)\) of fractional smoothness \(s>0\) for various equivalent norms including the classical one. The error is always measured in \(L_2(T^d)\). Particular emphasis is given to the dependence of all constants on the dimension \(d\). We capture the exact decay rate in \(n\) and the exact decay order of the constants with respect to \(d\), which is in fact polynomial. As a consequence we observe that none of our considered approximation problems suffers from the curse of dimensionality. Surprisingly, the square integrability of all weak derivatives up to order three (classical Sobolev norm) guarantees weak tractability of the associated multivariate approximation problem. Reviewer: Joe Howard (Portales) Cited in 1 ReviewCited in 27 Documents MSC: 47B06 Riesz operators; eigenvalue distributions; approximation numbers, \(s\)-numbers, Kolmogorov numbers, entropy numbers, etc. of operators Keywords:approximation numbers; Sobolev embeddings; sharp constants; weak tractability; curse of dimensionality PDFBibTeX XMLCite \textit{T. Kühn} et al., J. Complexity 30, No. 2, 95--116 (2014; Zbl 1334.47028) Full Text: DOI References: [1] Bose, R. C.; Manvel, B., Introduction to Combinatorial Theory (1984), Wiley: Wiley New York · Zbl 0636.05001 [2] Creutzig, J.; Wojtaszczyk, P., Linear vs. nonlinear algorithms for linear problems, J. Complexity, 20, 807-820 (2004) · Zbl 1086.41017 [3] Dũng, D.; Ullrich, T., \(N\)-widths and \(\varepsilon \)-dimensions for high-dimensional approximations, Found. Comput. Math (2013), (in press) · Zbl 1284.42001 [4] Gradshteyn, I. S.; Ryzhik, I. M., Tables of Integrals, Series and Products (2007), Academic Press · Zbl 1208.65001 [5] Kolmogorov, A. N., Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse, Ann. of Math. (2), 37, 107-110 (1936) · Zbl 0013.34903 [6] König, H., Eigenvalue Distribution of Compact Operators (1986), Birkhäuser: Birkhäuser Basel · Zbl 0618.47013 [8] Mitrinović, D. S., (Analytic Inequalities. Analytic Inequalities, Grundlehren, Bd. 165 (1970), Springer: Springer Berlin) · Zbl 0199.38101 [9] Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems. Volume I: Linear Information (2008), EMS: EMS Zürich) · Zbl 1156.65001 [10] Novak, E.; Woźniakowski, H., Approximation of infinitely differentiable multivariate functions is intractable, J. Complexity, 25, 398-404 (2009) · Zbl 1180.41031 [11] Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems. Volume II: Standard Information for Functionals (2010), EMS: EMS Zürich) · Zbl 1241.65025 [12] Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems. Volume III: Standard Information for Operators (2012), EMS: EMS Zürich) · Zbl 1359.65003 [13] Pietsch, A., History of Banach Spaces and Linear Operators (2007), Birkhäuser: Birkhäuser Basel · Zbl 1121.46002 [14] Pinkus, A., \(N\)-Widths in Approximation Theory (1985), Springer: Springer Berlin · Zbl 0551.41001 [15] Pólya, G.; Szegö, G., (Aufgaben und Lehrsätze aus der Analysis. Aufgaben und Lehrsätze aus der Analysis, Grundlehren, Bd. 19 (1954), Springer: Springer Berlin) · Zbl 0055.27802 [16] Temlyakov, V. N., Approximation of Periodic Functions (1993), Nova Science: Nova Science New York · Zbl 0899.41001 [17] Tikhomirov, V. M., (Approximation Theory. Approximation Theory, Encyclopaedia of Math. Sciences, Analysis II, vol. 14 (1990), Springer: Springer Berlin) · Zbl 0728.41016 [18] Traub, J. F.; Wasilkowski, G. W.; Woźniakowski, H., Information-Based Complexity (1988), Academic Press: Academic Press New York · Zbl 0654.94004 [19] Vybíral, J., Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions, J. Complexity, 30, 2, 48-55 (2014) · Zbl 1308.46034 [20] Wang, X., Volumes of generalized unit balls, Math. Mag., 78, 5, 390-395 (2005) · Zbl 1085.51024 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.