Learning Functions of Few Arbitrary Linear Parameters in High Dimensions

Details Learning Functions of Few Arbitrary Linear Parameters in High Dimensions Learning Functions of Few Arbitrary Linear Parameters in High Dimensions

2010-08-18

arxiv.org/abs/1008.3043v2

Mathematics

Numerical Analysis

31 pages, this version was accepted to Foundations of Computational Mathematics, the final publication will be available on

Scientific paper

Let us assume that $f$ is a continuous function defined on the unit ball of $\mathbb R^d$, of the form $f(x) = g (A x)$, where $A$ is a $k \times d$ matrix and $g$ is a function of $k$ variables for $k \ll d$. We are given a budget $m \in \mathbb N$ 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 {\it arbitrary} choice of the matrix $A$, we present in this paper 1. a sampling choice of the points $\{x_i\}$ drawn at random for each function approximation; 2. 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 choice of the sampling points will be according to suitable random distributions and our results hold with overwhelming probability. Our approach uses tools taken from the {\it compressed sensing} framework, recent Chernoff bounds for sums of positive-semidefinite matrices, and classical stability bounds for invariant subspaces of singular value decompositions.

Affiliated with

Also associated with

No associations

Rating

Learning Functions of Few Arbitrary Linear Parameters in High Dimensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Learning Functions of Few Arbitrary Linear Parameters in High Dimensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning Functions of Few Arbitrary Linear Parameters in High Dimensions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-504320