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).