FoCM 2014 conference

Workshop B5 - Information Based Complexity

December 15, 18:00 ~ 18:30 - Room B23

## Tractability of approximation of ridge functions

### Department of Mathematical Analysis, Charles University, Prague, Czech Republic   -   vybiral@karlin.mff.cuni.cz

We give an overview of recent results on approximation of ridge functions $f(x)=g(a\cdot x)$. As the class of ridge functions is non-linear, number of interesting questions appear. We present, and analyse, several algorithms for recovery of such functions, study their numerical performance and their optimality. Surprisingly, nearly all sorts of tractability appear when trying to approximate ridge functions in high dimension from a limited number of its function values.

Joint work with Ingrid Daubechies (Duke), Massimo Fornasier (TU Munich), Anton Kolleck (TU Berlin), Sebastian Mayer (Uni Bonn), Karin Schnass (Uni Innsbruck) and Tino Ullrich (Uni Bonn).