University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Random sections of ellipsoids and the power of random information

Random sections of ellipsoids and the power of random information



ASCW01 - Challenges in optimal recovery and hyperbolic cross approximation

We study the circumradius of the intersection of an $m$-dimensional ellipsoid$mathcal E$ with half axes $sigma_1geqdotsgeq 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 $Hhookrightarrow 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 otin 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 oinfty$.

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.


Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

