Random sections of ellipsoids and the power of random information

39 mins 57 secs, 138.93 MB, WebM 640x360, 29.97 fps, 44100 Hz, 474.8 kbits/sec

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/2923596/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Hinrichs, A Monday 18th February 2019 - 11:00 to 11:35


Created:	2019-02-19 12:49
Collection:	Approximation, sampling and compression in data science
Publisher:	Isaac Newton Institute
Copyright:	Hinrichs, A
Language:	eng (English)
Distribution:	World (downloadable)
Explicit content:	No
Aspect Ratio:	16:9
Screencast:	No
Bumper:	UCS Default
Trailer:	UCS Default


Abstract:	We study the circumradius of the intersection of an m-dimensional ellipsoid~E with half axes σ1≥⋯≥σm with random subspaces of codimension n. We find that, under certain assumptions on σ, this random radius Rn=Rn(σ) is of the same order as the minimal such radius σn+1 with high probability. In other situations Rn is close to the maximum~σ1. The random variable Rn naturally corresponds to the worst-case error of the best algorithm based on random information for L2-approximation of functions from a compactly embedded Hilbert space H with unit ball E. In particular, σk is the kth largest singular value of the embedding H↪L2. In this formulation, one can also consider the case m=∞, and we prove that random information behaves very differently depending on whether σ∈ℓ2 or not. For σ∉ℓ2 random information is completely useless. For σ∈ℓ2 the expected radius of random information tends to zero at least at rate o(1/n−−√) as n→∞. 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.

Abstract:

We study the circumradius of the intersection of an m-dimensional ellipsoid~E with half axes σ1≥⋯≥σm with random subspaces of codimension n. We find that, under certain assumptions on σ, this random radius Rn=Rn(σ) is of the same order as the minimal such radius σn+1 with high probability. In other situations Rn is close to the maximum~σ1. The random variable Rn naturally corresponds to the worst-case error of the best algorithm based on random information for L2-approximation of functions from a compactly embedded Hilbert space H with unit ball E.

In particular, σk is the kth largest singular value of the embedding H↪L2. In this formulation, one can also consider the case m=∞, and we prove that random information behaves very differently depending on whether σ∈ℓ2 or not. For σ∉ℓ2 random information is completely useless. For σ∈ℓ2 the expected radius of random information tends to zero at least at rate o(1/n−−√) as n→∞.

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.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.93 Mbits/sec	581.22 MB	View	Download
WebM *	640x360	474.8 kbits/sec	138.93 MB	View	Download
iPod Video	480x270	521.97 kbits/sec	152.73 MB	View	Download
MP3	44100 Hz	249.77 kbits/sec	73.15 MB	Listen	Download
Auto	(Allows browser to choose a format it supports)

Streaming Media Service Upload

Random sections of ellipsoids and the power of random information