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.