View abstract

Session III.5 - Information-Based Complexity

Monday, June 19, 17:00 ~ 17:30

On Least Squares Approximation Based on Random or Optimal Data

Mario Ullrich

JKU Linz, Österreich   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

We study the $L_p$-approximation, $2\le p\le\infty$ of functions with the help of (unregularized) least squares methods based on "random" information, like function evaluations, and we want to compare this with the power of arbitrary algorithms based on arbitrary linear information, i.e., the best we can do theoretically.

Here, we survey on results of the past 5 years that eventually lead to a sharp comparison which showed that function evaluations are often enough for optimal results (in a worst-case sense).

Joint work with Matthieu Dolbeault (Sorbonne University, France), David Krieg (JKU Linz, Austria), Kateryna Pozharska (TU Chemnitz) and Tino Ullrich (TU Chemnitz).

View abstract PDF