Sampling numbers of smoothness classes via \(\ell^1\)-minimization

DOI10.1016/j.jco.2023.101786arXiv2212.00445OpenAlexW4385605328MaRDI QIDQ6062173

Felix Voigtlaender, Thomas Jahn, Tino Ullrich

Publication date: 30 November 2023

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

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

zbMATH Keywords

samplingrate of convergenceinformation based complexitysampling numberssmoothness class

Mathematics Subject Classification ID

Function spaces arising in harmonic analysis (42B35) Multidimensional problems (41A63) Rate of convergence, degree of approximation (41A25) Algorithms for approximation of functions (65D15) Banach spaces of continuous, differentiable or analytic functions (46E15) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46) Sampling theory in information and communication theory (94A20)

Related Items (3)

On the reconstruction of functions from values at subsampled quadrature points ⋮ On universal sampling recovery in the uniform norm ⋮ On the information complexity for integration in subspaces of the Wiener algebra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A mathematical introduction to compressive sensing
• Sparse Legendre expansions via \(\ell_1\)-minimization
• Linear vs. nonlinear algorithms for linear problems
• Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness
• Randomized approximation of Sobolev embeddings. II
• Function spaces in Lipschitz domains and optimal rates of convergence for sampling
• Interpolation via weighted \(\ell_{1}\) minimization
• On the relation between linear n-widths and approximation numbers
• Tractability of multivariate problems. Volume I: Linear information
• Widths of embeddings in function spaces
• Regularity and approximability of electronic wave functions
• Non-linear sampling recovery based on quasi-interpolant wavelet representations
• Nonlinear approximation by trigonometric sums
• Optimal sampling recovery of mixed order Sobolev embeddings via discrete {L}ittlewood--{P}aley type characterizations
• Numerical Fourier analysis
• Function values are enough for \(L_2\)-approximation. II
• 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\)
• Approximation of functions with small mixed smoothness in the uniform norm
• \(s\)-numbers of embeddings of weighted Wiener algebras
• A new upper bound for sampling numbers
• Function values are enough for \(L_2\)-approximation
• Bounds on Kolmogorov widths and sampling recovery for classes with small mixed smoothness
• Worst-case recovery guarantees for least squares approximation using random samples
• Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling
• Approximation of functions of several variables by trigonometric polynomials with given number of harmonics, and estimates of \(\epsilon\)- entropy
• A sharp upper bound for sampling numbers in \(L_2\)
• Sparse grid approximation in weighted Wiener spaces
• Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations
• Constructive sparse trigonometric approximation and other problems for functions with mixed smoothness
• High-Dimensional Statistics
• Classical Fourier Analysis
• An Improved Estimate in the Restricted Isometry Problem
• The Restricted Isometry Property of Subsampled Fourier Matrices
• Constructive subsampling of finite frames with applications in optimal function recovery

This page was built for publication: Sampling numbers of smoothness classes via \(\ell^1\)-minimization