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.001MaRDI QIDQ895989zbMATH OpenOpenAlexFDO

Authors Alexey Chernov, Dinh Dũng

Publication date 11 December 2015

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

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

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)

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.

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

Cites work

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

Cited in

(16)

• Approximation of mixed order Sobolev functions on the \(d\)-torus: asymptotics, preasymptotics, and \(d\)-dependence
• \(s\)-numbers of embeddings of weighted Wiener algebras
• \(N\)-widths and \(\varepsilon \)-dimensions for high-dimensional approximations
• On two asymptotic formulas in the theory of hyperbolic zeta function of lattices
• 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
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Deep ReLU neural networks in high-dimensional approximation
• Tensor power sequences and the approximation of tensor product operators
• Kolmogorov \(n\)-widths of function classes induced by a non-degenerate differential operator: a convex duality approach
• Best \(n\)-term approximation of diagonal operators and application to function spaces with mixed smoothness
• \(\varepsilon\)-dimension in infinite dimensional hyperbolic cross approximation and application to parametric elliptic PDEs
• Dimension-dependent error estimates for sampling recovery on Smolyak grids based on B-spline quasi-interpolation
• Adjusted sparse tensor product spectral Galerkin method for solving pseudodifferential equations on the sphere with random input data
• Infinite-dimensional compressed sensing and function interpolation
• How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings

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)