Random points are good for universal discretization

DOI10.1016/J.JMAA.2023.127570zbMATH Open1528.41024arXiv2301.12536MaRDI QIDQ6074492FDOQ6074492

Authors: Feng Dai, V. N. Temlyakov 

Publication date: 19 September 2023

Published in: Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

Abstract: There has been significant progress in the study of sampling discretization of integral norms for both a designated finite-dimensional function space and a finite collection of such function spaces (universal discretization). Sampling discretization results turn out to be very useful in various applications, particularly in sampling recovery. Recent sampling discretization results typically provide existence of good sampling points for discretization. In this paper, we show that independent and identically distributed random points provide good universal discretization with high probability. Furthermore, we demonstrate that a simple greedy algorithm based on those points that are good for universal discretization provides excellent sparse recovery results in the square norm.

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

Recommendations

• On universal sampling recovery in the uniform norm
• Universal sampling discretization
• Sampling discretization of integral norms and its application
• Sampling discretization of the uniform norm and applications
• Sampling discretization and related problems

zbMATH Keywords

recoveryuniversalitysampling discretization

Mathematics Subject Classification ID

Asymptotic approximations, asymptotic expansions (steepest descent, etc.) (41A60) Inequalities in approximation (Bernstein, Jackson, Nikol'ski?-type inequalities) (41A17) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65)

Cites Work

• Multivariate approximation
• Diophantine approximation
• A mathematical introduction to compressive sensing
• Approximation of zonoids by zonotopes
• Weak greedy algorithms
• An Improved Estimate in the Restricted Isometry Problem
• Greedy approximation with regard to non-greedy bases
• Constructive sparse trigonometric approximation and other problems for functions with mixed smoothness
• An inequality for the entropy numbers and its application
• Sparse Approximation and Recovery by Greedy Algorithms
• Optimal weighted least-squares methods
• Integral norm discretization and related problems
• Sampling discretization and related problems
• Some improved bounds in sampling discretization of integral norms

Cited In (5)

• Universal sampling discretization
• On universal sampling recovery in the uniform norm
• One-sided discretization inequalities and sampling recovery
• Sparse-grid sampling recovery and numerical integration of functions having mixed smoothness
• Tractability of sampling recovery on unweighted function classes

This page was built for publication: Random points are good for universal discretization

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