Random sections of ellipsoids and the power of random information

DOI10.1090/TRAN/8502MaRDI QIDQ5047902zbMATH OpenOpenAlexFDO

Authors Aicke Hinrichs, David Krieg, Erich Novak, Joscha Prochno, Mario Ullrich

Publication date 17 November 2022

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.06639

zbMATH Keywords

\(L_2\) approximationcomparison principles for Gaussian processesGaussian random matrixhigh dimensional convexityleast squaresrandom informationrandom intersection

Mathematics Subject Classification ID

Random convex sets and integral geometry (aspects of convex geometry) (52A22) Asymptotic theory of convex bodies (52A23) Random matrices (probabilistic aspects) (60B20) Geometric probability and stochastic geometry (60D05) Gaussian processes (60G15) Algorithms for approximation of functions (65D15) Complexity and performance of numerical algorithms (65Y20)

Abstract: We study the circumradius of the intersection of an $m$-dimensional ellipsoid $mathcalE$ with semi-axes $sigm{a}_{1}geqdotsgeqsigm{a}_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 $sigm{a}_{n+1}$ with high probability. In other situations $mathcal{R}_n$ is close to the maximum $sigm{a}_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 $mathcalE$. In particular, $sigm{a}_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 $sigmainel{l}_2$ or not. For $sigmaotinel{l}_2$ random information is completely useless, i.e., $mathbbE[mathcal{R}_n]=sigm{a}_1$. For $sigmainel{l}_2$ the expected radius of random information tends to zero at least at rate $o(1/sqrtn)$ as $noinfty$. In the important case $$, where $alpha>0$ and $$, we obtain that ${\displaystyle }$ mathbb E [mathcal{R}_n(sigma)] asymp �egin{cases} sigma_1 & : alpha<1/2 , ext{ or }, �etaleqalpha=1/2 \ sigma_n , sqrt{ln(n+1)} & : �eta>alpha=1/2 \ sigma_{n+1} & : alpha>1/2. end{cases} ${\displaystyle }$ 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. The upper bound is constructive. It is proven for the worst case error of a least squares estimator.

Recommendations

• Information geometry. Near randomness and near independence
• scientific article; zbMATH DE number 436493
• scientific article; zbMATH DE number 2154144
• The randomized information complexity of elliptic PDE
• 4. On the power of random information
• On asymptotic behavior of entropy of ellipsoids in a Hamming space
• Random sections of spherical convex bodies
• Entropy of an ellipsoid in a Hamming space
• Hitting probabilities for random ellipses and ellipsoids

Cites work

• 4. On the power of random information
• Adaptive estimation of a quadratic functional by model selection.
• Asymptotic formulas for the diameter of sections of symmetric convex bodies
• Asymptotic geometric analysis. I
• Condition numbers of random matrices
• Diameters of sections and coverings of convex bodies
• Eigenvalues and Condition Numbers of Random Matrices
• Function values are enough for \(L_2\)-approximation
• Function values are enough for \(L_2\)-approximation. II
• scientific article; zbMATH DE number 1574604 (Why is no real title available?)
• scientific article; zbMATH DE number 1001426 (Why is no real title available?)
• scientific article; zbMATH DE number 3931824 (Why is no real title available?)
• scientific article; zbMATH DE number 3931747 (Why is no real title available?)
• scientific article; zbMATH DE number 3944537 (Why is no real title available?)
• scientific article; zbMATH DE number 4061904 (Why is no real title available?)
• scientific article; zbMATH DE number 44592 (Why is no real title available?)
• scientific article; zbMATH DE number 193625 (Why is no real title available?)
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Invertibility of random matrices: norm of the inverse
• Linear information versus function evaluations for L₂-approximation
• Linear vs. nonlinear algorithms for linear problems
• Local operator theory, random matrices and Banach spaces.
• Mean width and diameter of proportional sections of a symmetric convex body
• On the expectation of operator norms of random matrices
• On the mean-width of isotropic convex bodies and their associated \(L_{p}\)-centroid bodies
• On the power of standard information for multivariate approximation in the worst case setting
• On the power of standard information for weighted approximation
• On the spectral norm of Gaussian random matrices
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Smallest singular value of a random rectangular matrix
• Smallest singular value of random matrices and geometry of random polytopes
• Smallest singular value of random matrices with independent columns
• Some estimates of norms of random matrices
• Subspaces of Small Codimension of Finite-Dimensional Banach Spaces
• Support Vector Machines
• The concentration of measure phenomenon
• The dimension-free structure of nonhomogeneous random matrices
• The Littlewood-Offord problem and invertibility of random matrices
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Tractability of multivariate problems. Volume III: Standard information for operators

Cited in

(15)

• Spectral flatness and the volume of intersections of \(p\)-ellipsoids
• Best and random approximation of a convex body by a polytope
• Lower bounds for integration and recovery in L₂
• Weighted \(p\)-radial distributions on Euclidean and matrix \(p\)-balls with applications to large deviations
• A sharp upper bound for sampling numbers in \(L_2\)
• Exponential tractability of \(L_2\)-approximation with function values
• Recovery of Sobolev functions restricted to iid sampling
• Large deviations for uniform projections of $p$-radial distributions on $\ell_p^n$-balls
• Optimal recovery and volume estimates
• Random sections of _p-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators
• Norms of structured random matrices
• On the power of standard information for tractability for \(L_{\infty}\) approximation of periodic functions in the worst case setting
• Large deviations for random matrices in the orthogonal group and Stiefel manifold with applications to random projections of product distributions
• Optimal algorithms for numerical integration: recent results and open problems
• Approximation of functions: optimal sampling and complexity

This page was built for publication: Random sections of ellipsoids and the power of random information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5047902)