Capturing Ridge Functions in High Dimensions from Point Queries
Capturing Ridge Functions in High Dimensions from Point Queries
复制标题
从点查询中捕获高维岭函数
DOI：
10.1007/s00365-011-9147-6
复制
发表时间：
2011
影响因子：
2.7
通讯作者：
D. Picard
中科院分区：
文献类型：
--
作者：
A. Cohen;I. Daubechies;R. DeVore;G. Kerkyacharian;D. Picard
构造多变量函数的良好近似值受到“维度诅咒”的困扰。也就是说，在一般情况下，利用线性空间或维数为N的非线性流形，可以以最多O（N−s/N）的精度捕获平滑度为s阶的函数。如果N很大而s很小，则必须选择非常大的N才能获得良好的精度。N的大值常常妨碍合理的数值处理。另一方面，人们普遍认为，现实世界中的高维问题具有更适合于数值恢复的解和函数。这导致了这些函数的模型的引入，这些模型不仅依赖于平滑性，而且还涉及某种形式的变量缩减。在这些模型中，假设函数依赖于N个变量，但只有少数变量是显著的。这个原理的另一种变体是函数存在于低维流形上。由于主导变量（分别是流形）是未知的，这就导致了如何组织点查询来捕获这些函数的新问题。本文研究了当a∈f(x)=g（a·x）且g∈C[0,1]均未知时，在何处查询脊函数f(x)=g（a·x）的值。在假设g∈Cs[0,1]的情况下，我们利用这些点查询来估计f的近似值。我们还研究了a的稀疏性或可压缩性在这类查询问题中的作用。
Constructing a good approximation to a function of many variables suffers from the “curse of dimensionality”. Namely, functions on ℝN with smoothness of order s can in general be captured with accuracy at most O(n−s/N) using linear spaces or nonlinear manifolds of dimension n. If N is large and s is not, then n has to be chosen inordinately large for good accuracy. The large value of N often precludes reasonable numerical procedures. On the other hand, there is the common belief that real world problems in high dimensions have as their solution, functions which are more amenable to numerical recovery. This has led to the introduction of models for these functions that do not depend on smoothness alone but also involve some form of variable reduction. In these models it is assumed that, although the function depends on N variables, only a small number of them are significant. Another variant of this principle is that the function lives on a low dimensional manifold. Since the dominant variables (respectively the manifold) are unknown, this leads to new problems of how to organize point queries to capture such functions. The present paper studies where to query the values of a ridge function f(x)=g(a⋅x) when both a∈ℝN and g∈C[0,1] are unknown. We establish estimates on how well f can be approximated using these point queries under the assumptions that g∈Cs[0,1]. We also study the role of sparsity or compressibility of a in such query problems.