Random points are good for universal discretization

DOI10.1016/J.JMAA.2023.127570MaRDI QIDQ6074492zbMATH OpenFDO

Authors Feng Dai, V. N. Temlyakov

Publication date 19 September 2023

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

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

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)

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.

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

Cites work

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

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)