A multivariate ridge function is a function of the form @math , where @math is univariate and @math . We show that the recovery of an unknown ridge function defined on the hypercube @math with Lipschitz-regular profile @math suffers from the curse of dimensionality when the recovery error is measured in the @math -norm, even if we allow randomized algorithms. If a limited number of components of @math is substantially larger than the others, then the curse of dimensionality is not present and the problem is weakly tractable provided the profile @math is sufficiently regular.
There is an obvious generalization of the ridge function model, namely functions of the form [ f(x) = g(Ax), g: ^m , A ^ m d , ] where @math is supposed to be much smaller than the ambient dimension @math . @cite_33 , such functions are called . Following the ideas of @cite_35 , the paper @cite_22 develops an efficient algorithm for the recovery of generalized ridge functions defined on Euclidean balls, provided the function @math fulfills certain integral conditions and the rows of the matrix are compressible. In the case @math , the integral conditions are fulfilled, e.g., if we assume . Instead of compressibility assumptions on the rows of @math , the work @cite_28 assumes that the matrix @math is a low-rank tensor and obtains an algorithms that requires only polynomially many function samples.
@cite_28 @cite_35 @cite_22 @cite_33
2077625299 2012411663 2138611516 1991143958
We present effective algorithms for uniform approximation of multivariate functions satisfying some prescribed inner structure. We extend, in several directions, the analysis of recovery of ridge functions f ( x ) = g ( a , x ) as performed earlier by one of the authors and his coauthors. We consider ridge functions defined on the unit cube - 1 , 1 ] d as well as recovery of ridge functions defined on the unit ball from noisy measurements. We conclude with the study of functions of the type f ( x ) = g ( ? a - x ? l 2 d 2 ) . We consider the problem of learning multi-ridge functions of the form f (x) = g(Ax) from point evaluations of f. We assume that the function f is defined on an l(2)-ball in R-d, g is twice continuously differentiable almost everywhere, and A is an element of R-kxd is a rank k matrix, where k << d. We propose a randomized, polynomial-complexity sampling scheme for estimating such functions. Our theoretical developments leverage recent techniques from low rank matrix recovery, which enables us to derive a polynomial time estimator of the function f along with uniform approximation guarantees. We prove that our scheme can also be applied for learning functions of the form: f(x) = Sigma(k)(i=1) g(i)(a(i)(T)x), provided f satisfies certain smoothness conditions in a neighborhood around the origin. We also characterize the noise robustness of the scheme. Finally, we present numerical examples to illustrate the theoretical bounds in action. (C) 2014 Elsevier Inc. All rights reserved. We study the properties of ridge functions (f(x)=g(a x) ) in high dimensions (d ) from the viewpoint of approximation theory. The function classes considered consist of ridge functions such that the profile (g ) is a member of a univariate Lipschitz class with smoothness ( >0 ) (including infinite smoothness) and the ridge direction (a ) has (p )-norm ( a _p 1 ). First, we investigate entropy numbers in order to quantify the compactness of these ridge function classes in (L_ ). We show that they are essentially as compact as the class of univariate Lipschitz functions. Second, we examine sampling numbers and consider two extreme cases. In the case (p=2 ), sampling ridge functions on the Euclidean unit ball suffers from the curse of dimensionality. Moreover, it is as difficult as sampling general multivariate Lipschitz functions, which is in sharp contrast to the result on entropy numbers. When we additionally assume that all feasible profiles have a first derivative uniformly bounded away from zero at the origin, the complexity of sampling ridge functions reduces drastically to the complexity of sampling univariate Lipschitz functions. In between, the sampling problem’s degree of difficulty varies, depending on the values of ( ) and (p ). Surprisingly, we see almost the entire hierarchy of tractability levels as introduced in the recent monographs by Novak and Woźniakowski. 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.