TY - JOUR
T1 - Learning Functions of Few Arbitrary Linear Parameters in High Dimensions
AU - Fornasier, Massimo
AU - Schnass, Karin
AU - Vybiral, Jan
N1 - Funding Information:
Massimo Fornasier would like to thank Ronald A. DeVore for his kind and warm hospitality at Texas A&M University and for the very exciting daily joint discussions which later inspired part of this work. We acknowledge the financial support provided by the START-award “Sparse Approximation and Optimization in High Dimensions” of the Fonds zur Förderung der wissenschaftlichen Forschung (FWF, Austrian Science Foundation). We would also like to thank the anonymous referees for their very valuable comments and remarks.
PY - 2012/4
Y1 - 2012/4
N2 - 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(xi), 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 1. a sampling choice of the points {xi} 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 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.
AB - 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(xi), 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 1. a sampling choice of the points {xi} 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 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.
KW - Chernoff bounds for sums of positive semidefinite matrices
KW - Compressed sensing
KW - High-dimensional function approximation
KW - Stability bounds for invariant subspaces of singular value decompositions
UR - http://www.scopus.com/inward/record.url?scp=84858753339&partnerID=8YFLogxK
U2 - 10.1007/s10208-012-9115-y
DO - 10.1007/s10208-012-9115-y
M3 - Article
AN - SCOPUS:84858753339
SN - 1615-3375
VL - 12
SP - 229
EP - 262
JO - Foundations of Computational Mathematics
JF - Foundations of Computational Mathematics
IS - 2
ER -