Function values are enough for \(L_2\)-approximation. II

DOI10.1016/j.jco.2021.101569zbMath1475.41006OpenAlexW3155724638MaRDI QIDQ1979425

David Krieg, Mario Ullrich

Publication date: 2 September 2021

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

Full work available at URL: https://doi.org/10.1016/j.jco.2021.101569

zbMATH Keywords

rate of convergencerandom matricesleast squaresinformation-based complexityKadison-Singer\(L_2\)-approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random matrices (probabilistic aspects) (60B20) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Multidimensional problems (41A63) Rate of convergence, degree of approximation (41A25)

Related Items (19)

Approximation of functions with small mixed smoothness in the uniform norm ⋮ On the power of standard information for tractability for \(L_2\)-approximation in the average case setting ⋮ Random sections of ellipsoids and the power of random information ⋮ Sampling discretization and related problems ⋮ A new upper bound for sampling numbers ⋮ Lower bounds for integration and recovery in \(L_2\) ⋮ A Note on Sampling Recovery of Multivariate Functions in the Uniform Norm ⋮ Weighted random sampling and reconstruction in general multivariate trigonometric polynomial spaces ⋮ Constructive subsampling of finite frames with applications in optimal function recovery ⋮ Spherical random sampling of localized functions on 𝕊ⁿ⁻¹ ⋮ A sharp upper bound for sampling numbers in \(L_2\) ⋮ Sampling numbers of smoothness classes via \(\ell^1\)-minimization ⋮ Recovery of Sobolev functions restricted to iid sampling ⋮ On the reconstruction of functions from values at subsampled quadrature points ⋮ 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 ⋮ Optimal pointwise sampling for \(L^2\) approximation ⋮ \(L_2\)-norm sampling discretization and recovery of functions from RKHS with finite trace

Cites Work

• Unnamed Item
• Unnamed Item
• On the stability and accuracy of least squares approximations
• 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
• Linear information versus function evaluations for \(L_2\)-approximation
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• The Kadison-Singer problem in discrepancy theory.
• Tensor power sequences and the approximation of tensor product operators
• Hyperbolic cross approximation. Lecture notes given at the courses on constructive approximation and harmonic analysis, Barcelona, Spain, May 30 -- June 3, 2016
• On optimal recovery in \(L_2\)
• On the worst-case error of least squares algorithms for \(L_2\)-approximation with high probability
• Bounds on Kolmogorov widths and sampling recovery for classes with small mixed smoothness
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• The Marcinkiewicz-type discretization theorems for the hyperbolic cross polynomials
• 4. On the power of random information
• Exponential frames on unbounded sets
• Multivariate Approximation
• Optimal weighted least-squares methods

This page was built for publication: Function values are enough for \(L_2\)-approximation. II