Certified Randomized Methods for High-Dimensional Approximation: Non-asymptotic bounds for the PCA/POD error and near-optimal sampling strategies

Thumbnail

Event details

Date 25.11.2026
Hour 16:15
Speaker Kathrin Smetana (EPFL)
Location
CM 1 517
Category Conferences - Seminars
Event Language English

In this talk, I will present randomized methods that provide a certified approximation of the solutions of parametric partial differential equations (PDEs) with high-dimensional parameter sets. To that end, we will exploit data-dependent sampling strategies and concentration phenomena to discover and leverage low-dimensional structure.
First, I will present non-asymptotic error bounds for Principal Component Analysis (PCA) or Proper Orthogonal Decomposition (POD) under the assumption that the norm of the solution is bounded for almost all parameter values. The resulting bounds are independent of the dimension of the parameter space and remain valid in infinite-dimensional settings. Under suitable spectral-gap conditions, we show that our bounds are asymptotically optimal up to constants.
While the PCA/POD result holds for general sampling distributions, the quality of the randomized approximation can be significantly improved by exploiting problem-dependent sampling. We therefore turn to provably near-optimal sampling strategies. Sampling from Christoffel-type measures provides a near-optimal strategy for identifying large function values from finitely many samples. Building on this idea, we design a randomized greedy algorithm that guarantees, with high probability, the desired approximation accuracy for almost every parameter value in the parameter set. We show that, with high probability, the resulting randomized greedy algorithm achieves quasi-optimal convergence rates. If we had already found a space that approximates the set of all solutions well, volume sampling based on that space would yield a quasi-best approximation in expectation with the number of samples on the order of the dimension of the reduced space. However, in this case, we would no longer need to sample, as we would already have a good approximation space. We therefore propose constructing a surrogate sampling distribution, for instance, from the data functions of the PDE, and analyze how this affects the approximation error.

Practical information

  • General public
  • Free

Organizer

  • Fabio Nobile

Contact

  • Fabio Nobile

Tags

Mathicse seminar

Event broadcasted in

Share