New explicit-in-dimension estimates for the cardinality of high-dimensional hyperbolic crosses and approximation of functions having mixed smoothness

DOI10.1016/J.JCO.2015.09.001zbMATH Open1330.65038arXiv1309.5170OpenAlexW1632572948MaRDI QIDQ895989FDOQ895989

Authors: Alexey Chernov, Dinh Dũng 

Publication date: 11 December 2015

Published in: Journal of Complexity (Search for Journal in Brave)

Abstract: We are aiming at sharp and explicit-in-dimension estimations of the cardinality of $s$-dimensional hyperbolic crosses where $s$ may be large, and applications in high-dimensional approximations of functions having mixed smoothness. In particular, we provide new tight and explicit-in-dimension upper and lower bounds for the cardinality of hyperbolic crosses. We apply them to obtain explicit upper and lower bounds for Kolmogorov $N$-widths and $varepsilon$-dimensions of a modified Korobov class parametrized by positive $a$ of $s$-variate periodic functions having mixed smoothness $r$, as a function of three variables $N,s,a$ and $varepsilon,s,a$, respectively, when $N,s$ may be large, $varepsilon$ may be small and $a$ may range from 0 to infinity. Based on these results we describe a complete classification of tractability for the problem of $varepsilon$-dimensions of the modified Korobov class. In particular, we prove the introduced exponential tractability of this problem for $a>1$. All of these methods and results are also extended to high-dimensional approximations of non-periodic functions by Jacobi polynomials with powers in hyperbolic crosses.

Full work available at URL: https://arxiv.org/abs/1309.5170

Recommendations

• Hyperbolic cross approximation in infinite dimensions
• \(N\)-widths and \(\varepsilon \)-dimensions for high-dimensional approximations
• Hyperbolic cross approximation. Lecture notes given at the courses on constructive approximation and harmonic analysis, Barcelona, Spain, May 30 -- June 3, 2016
• Spaces of functions of mixed smoothness and approximation from hyperbolic crosses
• Constructive sparse trigonometric approximation and other problems for functions with mixed smoothness

zbMATH Keywords

approximation of functionstractabilityhyperbolic crosshigh-dimensional approximation\(\varepsilon\)-dimensions\(N\)-widthsexponential tractabilitynon-periodic function

Mathematics Subject Classification ID

Algorithms for approximation of functions (65D15) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

Cites Work

• Theory of Reproducing Kernels
• Title not available (Why is that?)
• Tensor products of Sobolev-Besov spaces and applications to approximation from the hyperbolic cross
• Number of lattice points in the hyperbolic cross
• Spline interpolation on sparse grids
• Approximation of mixed order Sobolev functions on the \(d\)-torus: asymptotics, preasymptotics, and \(d\)-dependence
• Number of integral points in a certain set and the approximation of functions of several variables
• \(N\)-widths and \(\varepsilon \)-dimensions for high-dimensional approximations
• Über die beste Annäherung von Funktionen einer gegebenen Funktionenklasse
• DIAMETERS OF SETS IN FUNCTION SPACES AND THE THEORY OF BEST APPROXIMATIONS
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• B-spline quasi-interpolant representations and sampling recovery of functions with mixed smoothness
• Regularity and approximability of electronic wave functions
• Sparse finite elements for elliptic problems with stochastic loading
• Multivariate approximation by translates of the Korobov function on Smolyak grids
• Approximation on simplices with respect to weighted Sobolev norms
• Encyclopedia of quantitative finance. 4 Volumes.
• Sparse finite elements for stochastic elliptic problems --- higher order moments
• Title not available (Why is that?)
• Hyperbolic wavelet approximation
• Sparse polynomial approximation in positive order Sobolev spaces with bounded mixed derivatives and applications to elliptic problems with random loading
• Sparse \(p\)-version BEM for first kind boundary integral equations with random loading
• Data mining with sparse grids
• Title not available (Why is that?)
• Title not available (Why is that?)
• First-order \(k\)-th moment finite element analysis of nonlinear operator equations with stochastic data
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distribution of lattice points on hyperbolic surfaces

Cited In (14)

• Kolmogorov \(n\)-widths of function classes induced by a non-degenerate differential operator: a convex duality approach
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Dimension-dependent error estimates for sampling recovery on Smolyak grids based on B-spline quasi-interpolation
• How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings
• Infinite-dimensional compressed sensing and function interpolation
• О двух асимптотических формулах в теории гиперболической дзета-функции решёток
• Sampling on energy-norm based sparse grids for the optimal recovery of Sobolev type functions in \(H^\gamma\)
• Sharp estimates for approximation numbers of non-periodic Sobolev embeddings
• Deep ReLU neural networks in high-dimensional approximation
• \(s\)-numbers of embeddings of weighted Wiener algebras
• Tensor power sequences and the approximation of tensor product operators
• Best \(n\)-term approximation of diagonal operators and application to function spaces with mixed smoothness
• Adjusted sparse tensor product spectral Galerkin method for solving pseudodifferential equations on the sphere with random input data
• Approximation of mixed order Sobolev functions on the \(d\)-torus: asymptotics, preasymptotics, and \(d\)-dependence

This page was built for publication: New explicit-in-dimension estimates for the cardinality of high-dimensional hyperbolic crosses and approximation of functions having mixed smoothness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q895989)