Tractability of the approximation of high-dimensional rank one tensors

DOI10.1007/S00365-015-9282-6zbMATH Open1335.65106arXiv1402.5011OpenAlexW2012733921MaRDI QIDQ5962914FDOQ5962914

Daniel Rudolf, Erich Novak

Publication date: 25 February 2016

Published in: Constructive Approximation (Search for Journal in Brave)

Abstract: We study the approximation of high-dimensional rank one tensors using point evaluations and consider deterministic as well as randomized algorithms. We prove that for certain parameters (smoothness and norm of the $r$th derivative) this problem is intractable while for other parameters the problem is tractable and the complexity is only polynomial in the dimension for every fixed $varepsilon>0$. For randomized algorithms we completely characterize the set of parameters that lead to easy or difficult problems, respectively. In the "difficult" case we modify the class to obtain a tractable problem: The problem gets tractable with a polynomial (in the dimension) complexity if the support of the function is not too small.

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

zbMATH Keywords

dispersioncurse of dimensionalitytractabilityhigh-dimensional approximationrank one tensors

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Complexity and performance of numerical algorithms (65Y20) Multidimensional problems (41A63) Vector and tensor algebra, theory of invariants (15A72) Rate of convergence, degree of approximation (41A25)

Cites Work

• Learnability and the Vapnik-Chervonenkis dimension
• Deterministic and stochastic error bounds in numerical analysis
• Tractability of multivariate problems. Volume III: Standard information for operators
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Entropy and sampling numbers of classes of ridge functions
• Approximation of infinitely differentiable multivariate functions is intractable
• The curse of dimensionality for numerical integration of smooth functions
• On the largest empty axis-parallel box amidst \(n\) points
• On the power of adaption
• Quasi-Monte-Carlo methods and the dispersion of point sequences
• Approximation of high-dimensional rank one tensors

Cited In (16)

• The minimal \(k\)-dispersion of point sets in high dimensions
• Expected dispersion of uniformly distributed points
• The recovery of ridge functions on the hypercube suffers from the curse of dimensionality
• Minimal dispersion of large volume boxes in the cube
• Transformed rank-1 lattices for high-dimensional approximation
• A note on minimal dispersion of point sets in the unit cube
• An upper bound on the minimal dispersion
• Deterministic constructions of high-dimensional sets with small dispersion
• On the size of the largest empty box amidst a point set
• \(O(d \log N)\)-quantics approximation of \(N\)-\(d\) tensors in high-dimensional numerical modeling
• Approximation of high-dimensional rank one tensors
• Recovery algorithms for high-dimensional rank one tensors
• On the dispersion of sparse grids
• On optimal approximation in periodic Besov spaces
• An Upper Bound of the Minimal Dispersion via Delta Covers
• Tractability of sampling recovery on unweighted function classes

This page was built for publication: Tractability of the approximation of high-dimensional rank one tensors

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