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
2012411663 1983767920 1644425553
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. This paper is about an inverse problem. We assume we are given a functionf(x) which is some sum of ridge functions of the form ?mi=1gi(ai·x) and we just know an upper bound onm. We seek to identify the functionsgiand also to identify the directionsaifrom such limited information. Several ways to solve this nonlinear problem are discussed in this work. Let us assume that f is a continuous function defined on the unit ball of ℝ d , of the form f(x)=g(Ax), where A is a k×d matrix and g is a function of k variables for k≪d. We are given a budget m∈ℕ of possible point evaluations f(x i ), i=1,…,m, of f, which we are allowed to query in order to construct a uniform approximating function. Under certain smoothness and variation assumptions on the function g, and an arbitrary choice of the matrix A, we present in this paper a sampling choice of the points xi drawn at random for each function approximation; algorithms (Algorithm 1 and Algorithm 2) for computing the approximating function, whose complexity is at most polynomial in the dimension d and in the number m of points. Due to the arbitrariness of A, the sampling points will be chosen according to suitable random distributions, and our results hold with overwhelming probability. Our approach uses tools taken from the compressed sensing framework, recent Chernoff bounds for sums of positive semidefinite matrices, and classical stability bounds for invariant subspaces of singular value decompositions.