Worst-case recovery guarantees for least squares approximation using random samples
From MaRDI portal
Publication:2243884
DOI10.1007/s00365-021-09555-0zbMath1484.41004arXiv1911.10111OpenAlexW3194792970MaRDI QIDQ2243884
Toni Volkmer, Tino Ullrich, Lutz Kämmerer
Publication date: 11 November 2021
Published in: Constructive Approximation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.10111
Analysis of algorithms (68W40) General nonlinear regression (62J02) Trigonometric approximation (42A10) Asymptotic approximations, asymptotic expansions (steepest descent, etc.) (41A60) Multidimensional problems (41A63) Approximation by polynomials (41A10) Rate of convergence, degree of approximation (41A25) Approximate quadratures (41A55) Numerical quadrature and cubature formulas (65D32) Sampling theory in information and communication theory (94A20)
Related Items
On the power of standard information for tractability for \(L_2\)-approximation in the average case setting, Sampling discretization and related problems, A new upper bound for sampling numbers, Lower bounds for integration and recovery in \(L_2\), Grouped Transformations and Regularization in High-Dimensional Explainable ANOVA Approximation, A Note on Sampling Recovery of Multivariate Functions in the Uniform Norm, 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, Random sampling of signals concentrated on compact set in localized reproducing kernel subspace of \(L^p (\mathbb{R}^n)\), Error guarantees for least squares approximation with noisy samples in domain adaptation, On the reconstruction of functions from values at subsampled quadrature points, Fast hyperbolic wavelet regression meets ANOVA, On the power of standard information for tractability for \(L_{\infty}\) approximation of periodic functions in the worst case setting, On the stability of unevenly spaced samples for interpolation and quadrature, Sampling discretization of the uniform norm, \(L_2\)-norm sampling discretization and recovery of functions from RKHS with finite trace, Generalized sparse grid interpolation based on the fast discrete Fourier transform, The uniform sparse FFT with application to PDEs with random coefficients
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal approximation of multivariate periodic Sobolev functions in the sup-norm
- A mathematical introduction to compressive sensing
- On the stability and accuracy of least squares approximations
- Sparse Legendre expansions via \(\ell_1\)-minimization
- Sums of random Hermitian matrices and an inequality by Rudelson
- B-spline quasi-interpolant representations and sampling recovery of functions with mixed smoothness
- Tractability through increasing smoothness
- Tractability of multivariate problems. Volume III: Standard information for operators
- Sampling, Marcinkiewicz-Zygmund inequalities, approximation, and quadrature rules
- Approximation of mixed order Sobolev functions on the \(d\)-torus: asymptotics, preasymptotics, and \(d\)-dependence
- Interpolation via weighted \(\ell_{1}\) minimization
- Linear information versus function evaluations for \(L_2\)-approximation
- Tractability of multivariate problems. Volume I: Linear information
- Optimal importance sampling for the approximation of integrals
- Tractability of multivariate problems. Volume II: Standard information for functionals.
- On the power of standard information for multivariate approximation in the worst case setting
- Tensor products of Sobolev-Besov spaces and applications to approximation from the hyperbolic cross
- Non commutative Khintchine and Paley inequalities
- Polynomial interpolation results in Sobolev spaces
- Random vectors in the isotropic position
- Hyperbolic wavelet approximation
- The Marcinkiewicz-type discretization theorems
- Tensor power sequences and the approximation of tensor product operators
- On the convergence rate of sparse grid least squares regression
- Correction to: ``On the stability and accuracy of least squares approximations
- How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings
- Numerical performance of optimized Frolov lattices in tensor product reproducing kernel Sobolev spaces
- On optimal recovery in \(L_2\)
- \(L_2\)-norm sampling discretization and recovery of functions from RKHS with finite trace
- A new upper bound for sampling numbers
- On the worst-case error of least squares algorithms for \(L_2\)-approximation with high probability
- Function values are enough for \(L_2\)-approximation
- Sampling discretization error of integral norms for function classes
- Approximation of multivariate periodic functions by trigonometric polynomials based on sampling along rank-1 lattice with generating vector of Korobov form
- Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness
- Relevant sampling of band-limited functions
- 4. On the power of random information
- The power of standard information for multivariate approximation in the randomized setting
- Exponential frames on unbounded sets
- Support Vector Machines
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- Irregular sampling, Toeplitz matrices, and the approximation of entire functions of exponential type
- Shannon sampling and function reconstruction from point values
- Optimal weighted least-squares methods
- Error Estimates for Multivariate Regression on Discretized Function Spaces
- New Preasymptotic Estimates for Approximation of Periodic Sobolev Functions
- Integral norm discretization and related problems
- Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the square
- Discrete least squares polynomial approximation with random evaluations − application to parametric and stochastic elliptic PDEs
- On the power of function values for the approximation problem in various settings
- High-dimensional integration: The quasi-Monte Carlo way
- On the power of standard information for weighted approximation
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
