Kolmogorov n-Widths of Function Classes Induced by a Non-Degenerate Differential Operator: A Convex Duality Approach

详细信息    查看全文

• 作者：Patrick L. Combettes ; Dinh Dũng
• 关键词：Asymptotic order ; Kolmogorov n ; widths ; Non ; degenerate differential operator ; Convex duality ; 41A10 ; 41A50 ; 41A63
• 刊名：Set-Valued and Variational Analysis
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：24
• 期：1
• 页码：83-99
• 全文大小：423 KB
• 参考文献：1.Babenko, K.I.: Approximation of periodic functions of many variables by trigonometric polynomials. Soviet Math. Dokl. 1, 513–516 (1960)MathSciNet MATH
  2.Babenko, K.I.: Approximation by trigonometric polynomials in a certain class of periodic functions of several variables. Soviet Math. Dokl. 1, 672–675 (1960)MathSciNet MATH
  3.Baraniuk, R., Davenport, M., DeVore, R., Wakin, M.: A simple proof of the restricted isometry property for random matrices. Constr. Approx. 28, 253–263 (2008)CrossRef MathSciNet MATH
  4.Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)CrossRef MATH
  5.Chernov, A., Dinh Dũng: New explicit-in-dimension estimates for the cardinality of high-dimensional hyperbolic crosses and approximation of functions having mixed smoothness. arXiv:1309.​5170
  6.Dinh Dũng: The number of integral points in some sets and approximation of functions of several variables. Mat. Zametki 36, 479–491 (1984)MathSciNet
  7.Dinh Dũng: Approximation of functions of several variables on a torus by trigonometric polynomials. Math. USSR-Sb 59, 247–267 (1988)CrossRef MathSciNet
  8.Dinh Dũng: Best multivariate approximations by trigonometric polynomials with frequencies from hyperbolic crosses. J. Approx. Theory 91, 205–225 (1997)CrossRef MathSciNet MATH
  9.Dinh Dũng, Ullrich, T.: n-widths and e-dimensions for high-dimensional approximations. Found. Comput. Math. 13, 965–1003 (2013)CrossRef MathSciNet MATH
  10.Donoho, D.L.: Compressed sensing. IEEE Trans. Inform. Theory 52, 1289–1306 (2006)CrossRef MathSciNet MATH
  11.Foucart, S., Pajor, A., Rauhut, H., Ullrich, T.: The Gelfand widths of l p -balls for 0<p=1. J. Complexity 26, 629–640 (2010)CrossRef MathSciNet MATH
  12.Gindikin, S.G.: Energy estimates connected with Newton polyhedron, Trudy Moskov. Mat. Obshch. 31, 189–236 (1974)MathSciNet MATH
  13.Höllig, K.: Diameters of classes of smooth functions. In: Quantitative Approximation, pp. 163–175. Academic, New York (1980)
  14.Kolmogorov, A.N.: Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse. Ann. of Math. 37, 107–110 (1936)CrossRef MathSciNet MATH
  15.Kolmogorov, A.N.: Selected Works, vol. 1, Mathematics and Mechanics, Nauka, Moscow (in Russian) (1985)
  16.Kurková, V., Sanguineti, M.: Comparison of worst case errors in linear and neural network approximation. IEEE Trans. Inform. Theory 48, 262–275 (2002)CrossRef
  17.Kushpel, A., Tozoni, S.A.: Entropy and widths of multiplier operators on two-point homogeneous spaces, Constr. Approx. 35, 137–180 (2012)CrossRef MathSciNet MATH
  18.Liang, J., Parks, T.W.: Kolmogorov n-widths and wavelet representations for signal classes. IEEE Trans. Signal Process. 44, 1693–1703 (1996)CrossRef
  19.Mihailov, V.P.: Behavior at infinity of a certain class of polynomials, Proc. Steklov Inst. Math. 91, 61–82 (1967)
  20.Pinkus, A.: n-Widths in Approximation Theory. Springer, New York (1985)CrossRef MATH
  21.Pinkus, A.: Sparse representations and approximation theory. J. Approx. Theory 163, 388–412 (2011)CrossRef MathSciNet MATH
  22.Rockafellar, R.T.: Convex Analysis, Princeton University Press, Princeton, NJ (1970)
  23.Schmeisser, H.-J., Sickel, W.: Spaces of functions of mixed smoothness and approximation from hyperbolic crosses. J. Approx. Theory 128, 115–150 (2004)CrossRef MathSciNet MATH
  24.Schwartz, L.: Théorie des Distributions, 2nd ed., Hermann & Cie, Paris (1966)
  25.Sickel, W., Ullrich, T.: Tensor products of Sobolev–Besov spaces and applications to approximation from the hyperbolic cross. J. Approx. Theory 161, 748–786 (2009)CrossRef MathSciNet MATH
  26.Temlyakov, V.: Approximation of Periodic Functions, Nova Science Publishers, Inc., New York (1993)
  27.Tikhomirov, V.M.: Diameters of sets in functional spaces and the theory of best approximations. Russ. Math. Survey 15, 75–111 (1960)CrossRef MATH
  28.Tikhomirov, V.M.: Some Problems in Approximation Theory (in Russian), Moscow State University (1985)
  29.Wang, H.: Widths between the anisotropic spaces and the spaces of functions with mixed smoothness. J. Approx. Theory 164, 406–430 (2012)CrossRef MathSciNet MATH
  30.Wojtaszczyk, P.: On greedy algorithm approximating Kolmogorov widths in Banach spaces. J. Math. Anal. Appl. 424, 685–695 (2015)CrossRef MathSciNet MATH
  31.Zhang, L.: Nearly optimal minimax estimator for high-dimensional sparse linear regression. Ann. Stat. 41, 2149–2175 (2013)CrossRef MATH
  
• 作者单位：Patrick L. Combettes (1)
  Dinh Dũng (2)
  
  1. Sorbonne Universités – UPMC Univ. Paris 06, UMR 7598, Laboratoire Jacques-Louis Lions, 75005, Paris, France
  2. Information Technology Institute, Vietnam National University, Hanoi, Vietnam
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Analysis
  Geometry
  
• 出版者：Springer Netherlands
• ISSN：1877-0541

文摘

The problem of computing the asymptotic order of the Kolmogorov n-width of the unit ball of the space of multivariate periodic functions induced by a differential operator associated with a polynomial in the general case when the ball is compactly embedded into L ₂ has been open for a long time. In the present paper, we use convex analytical tools to solve it in the case when the differential operator is non-degenerate. Keywords Asymptotic order Kolmogorov n-widths Non-degenerate differential operator Convex duality