Capturing Ridge Functions in High Dimensions from Point Queries |
| |
Authors: | Albert?Cohen Ingrid?Daubechies Email author" target="_blank">Ronald?DeVoreEmail author Gerard?Kerkyacharian Dominique?Picard |
| |
Institution: | 1.Laboratoire Jacques-Louis Lions,Université Pierre et Marie Curie,Paris,France;2.Department of Mathematics,Princeton University,Princeton,USA;3.Department of Mathematics,Texas A&M University,College Station,USA;4.Laboratoire PMA,Université Paris Diderot,Paris,France |
| |
Abstract: | 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∈C0,1] are unknown. We establish estimates on how well f can be approximated using these point queries under the assumptions that g∈C
s
0,1]. We also study the role of sparsity or compressibility of a in such query problems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|