2019/03/25 by Benjamin Doerr, Doerr, Benjamin, Sebastian Mayer +1
Engineering · Mathematics · Medicine · #FOS: Mathematics #Mathematical Approximation and Integration #Medical Imaging Techniques and Applications #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1903.10223
openalex publication_date 2019/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A multivariate ridge function is a function of the form f(x) =\ng(a scriptscriptstyle T x), where g is univariate and a \∈\n\ℝd. We show that the recovery of an unknown ridge function defined\non the hypercube [-1,1]d with Lipschitz-regular profile g suffers from the\ncurse of dimensionality when the recovery error is measured in the\nL_\∞-norm, even if we allow randomized algorithms. If a limited number of\ncomponents of a is substantially larger than the others, then the curse of\ndimensionality is not present and the problem is weakly tractable provided the\nprofile g is sufficiently regular.\n