WDI2 - Approximation Theory and Applications
We are happy to announce that the next edition of the Workshop Donau-Isar-Inn will be hosted by the University of Innsbruck Friday, 28th of June 2024.
The workshop will take place from 14:00 to 17:15 at the Campus Technik, lecture theatre HSB6 in the civil engineering building (Technikerstr. 13), followed by a dinner in the city centre. The talk schedule as well as the abstracts can be found below.
To register for the workshop please send an email to Morris-Luca Kühmeier until Friday 21st of June 2024.
indicating whether you will join for dinner and/or bring a poster.
We are looking forward to seeing you in Innsbruck!
Schedule
14:00 | Welcome |
14:05 | Diana Carbajal - University of Vienna Random periodic sampling patterns for shift-invariant spaces |
14:45 | David Krieg - University of Passau Optimal recovery in the uniform norm |
15:25 | Coffee and cookie break |
16:00 | Posters!! with more coffee and cookies. |
16:35 | Antoine Maillard - ETH Zurich Fitting ellipsoids to random points |
17:15 | Commute to Restaurant Stiftskeller |
18:00 | Dinner |
Poster session
We will have a dedicated poster session after an ample cookie and coffee break, so we invite everybody to bring a poster.
Random periodic sampling patterns for shift-invariant spaces
Diana Carbajal - University of Vienna
The sampling problem involves finding conditions under which a signal can be reconstructed from its samples taken on a discrete subset of its domain. The most classical assumption about the sampled signal is that it belongs to a Paley-Wiener space (the space of signals whose Fourier transform is supported on a given compact set). In multidimensional settings, finding a stable sampling set for this type of signal remains a very challenging task.
One prolific line of research considers the Paley-Wiener spaces whose spectrum has the property of multi-tiling the space along lattice translations. These signals admit a stable sampling set in the form of a finite union of translations of a lattice –a periodic non-uniform set– that meets Landau’s density benchmark. However, in practice, explicitly constructing such sets requires a substantial level of effort. Namely, the practitioner would need to choose the translation points so as to avoid a certain algebraic variety of exceptional sets. Moreover, no simple a priori stability bounds are provided.
In this presentation, we discuss a probabilistic approach to this problem, while extending it to a broader signal model of shift-invariant spaces that includes the case of Paley-Wiener spaces with a multi-tiling spectrum. We show that by slightly exceeding Landau’s density benchmark, it is possible to obtain periodic non-uniform sampling sets with overwhelming probability. The random sampling strategy not only provides a simple alternative with respect to the deterministic results but is also accompanied with explicit and possibly very favorable stability margins.
This is a joint work with Jorge Antezana (Autonomous University of Madrid) and José Luis Romero (University of Vienna).
Optimal recovery in the uniform norm
David Krieg - University of PassauWe consider the problem of approximating an unknown bounded function f : D → ℂ based on a finite number of function values. Here, D is an arbitrary set and the error is measured in the uniform norm on D.
We show that for any n-dimensional space Vn of bounded functions, the knowledge of 2n function values suffices to compute an approximation of f within Vn whose error exceeds the error of best approximation of f within Vn by a factor of at most O(n½). Previously, it was known that n function values can give the optimal approximation up to a factor O(n) and 9n function values can give the optimal approximation up to a factor O(1). Our result counterbalances the oversampling and the error.
The approximation can be obtained by a plain least-squares algorithm with carefully chosen nodes. The proof is based on properties of an extremal probability measure μ related to Vn and statements on the discretization of the L2(μ)-norm on Vn. The result is sharp in the sense that the excessive factor O(n½) cannot be replaced by a smaller order term with any recovery method that uses at most O(n) function values.
This is joint work with Kateryna Pozharska, Mario Ullrich, and Tino Ullrich.
Fitting ellipsoids to random points
Antoine Maillard - ETH ZürichWe consider the problem of exactly fitting an ellipsoid (centered at 0) to n standard Gaussian random vectors in dimension d, for very large n and d. This problem has connections to questions in statistical learning and theoretical computer science, and is conjectured to undergo a sharp transition: with high probability, it has a solution if n < d2/4, while it is not satisfiable if n > d2/4. In this talk we will discuss the origin of this conjecture, and highlight some recent progress, in three different directions:
- A proof that the problem is feasible for n < d2/C, for some (large) constant C, significantly improving over previously-known bounds.
- A non-rigorous characterization of the conjecture, as well as significant generalizations, using analytical methods of statistical physics.
- A rigorous proof of a satisfiability transition exactly at n = d2/4 in a slightly relaxed version of the problem, the first rigorous result characterizing the expected phase transition in ellipsoid fitting. The proof is inspired by the non-rigorous characterization discussed above.
This talk is based on the three manuscripts: arXiv:2307.01181, arXiv:2310.01169, arXiv:2310.05787, which are joint works with Afonso Bandeira (ETH Zürich), Tim Kunisky (Yale University), Shahar Mendelson (Australian National University) and Elliot Paquette (McGill University).
Registration
To register for the workshop send an email to Morris-Luca Kühmeier until Friday 21st of June 2024.
Please indicate whether you will bring a poster and/or join for dinner.
Location and Directions
The workshop will take place from 14:00 to 17:15 at the Campus Technik in lecture theatre HSB6 in the civil engineering building (Bauingenieurgebäude), Technikerstr. 13.
To get to Campus Technik from Innsbruck main station, take Tram 5 (direction Technik West) or Bus K (direction Kranebitten) and get out at the stop Technik (Technikerstraße).
Organisation
- Morris-Luca Kühmeier
- Sandra Naschberger
- Karin Schnass