skip to content

# Random sections of ellipsoids and the power of random information

Presented by:
Aicke Hinrichs Johannes Kepler Universität
Date:
Monday 18th February 2019 - 11:00 to 11:35
Venue:
INI Seminar Room 1
Abstract:
We study the circumradius of the intersection of an $m$-dimensional ellipsoid~$\mathcal E$ with half axes $\sigma_1\geq\dots\geq \sigma_m$ with random subspaces of codimension $n$. We find that, under certain assumptions on $\sigma$, this random radius $\mathcal{R}_n=\mathcal{R}_n(\sigma)$ is of the same order as the minimal such radius $\sigma_{n+1}$ with high probability. In other situations $\mathcal{R}_n$ is close to the maximum~$\sigma_1$. The random variable $\mathcal{R}_n$ naturally corresponds to the worst-case error of the best algorithm based on random information for $L_2$-approximation of functions from a compactly embedded Hilbert space $H$ with unit ball $\mathcal E$.

In particular, $\sigma_k$ is the $k$th largest singular value of the embedding $H\hookrightarrow L_2$. In this formulation, one can also consider the case $m=\infty$, and we prove that random information behaves very differently depending on whether $\sigma \in \ell_2$ or not. For $\sigma \notin \ell_2$ random information is completely useless. For $\sigma \in \ell_2$ the expected radius of random information tends to zero at least at rate $o(1/\sqrt{n})$ as $n\to\infty$.

In the proofs we use a comparison result for Gaussian processes a la Gordon, exponential estimates for sums of chi-squared random variables, and estimates for the extreme singular values of (structured) Gaussian random matrices.

This is joint work with David Krieg, Erich Novak, Joscha Prochno and Mario Ullrich.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: