On the worst-case error of least squares algorithms for \(L_2\)-approximation with high probability

DOI10.1016/j.jco.2020.101484OpenAlexW3017325642MaRDI QIDQ2192673

Mario Ullrich

Publication date: 17 August 2020

Published in: Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

random matricesleast squares\(L_2\)-approximation

Mathematics Subject Classification ID

Numerical analysis (65-XX) Computer science (68-XX)

Related Items

A new upper bound for sampling numbers ⋮ A Note on Sampling Recovery of Multivariate Functions in the Uniform Norm ⋮ Weighted random sampling and reconstruction in general multivariate trigonometric polynomial spaces ⋮ Spherical random sampling of localized functions on 𝕊ⁿ⁻¹ ⋮ A sharp upper bound for sampling numbers in \(L_2\) ⋮ Recovery of Sobolev functions restricted to iid sampling ⋮ New lower bounds for the integration of periodic functions ⋮ On the power of standard information for tractability for \(L_{\infty}\) approximation of periodic functions in the worst case setting ⋮ Exponential tractability of \(L_2\)-approximation with function values ⋮ Function values are enough for \(L_2\)-approximation ⋮ Function values are enough for \(L_2\)-approximation. II ⋮ Worst-case recovery guarantees for least squares approximation using random samples ⋮ \(L_2\)-norm sampling discretization and recovery of functions from RKHS with finite trace

Cites Work

• Sums of random Hermitian matrices and an inequality by Rudelson
• Tractability of multivariate problems. Volume III: Standard information for operators
• On singular values of matrices with independent rows
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.