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

recoverysampling discretizationuniversality

Mathematics Subject Classification ID

Inequalities in approximation (Bernstein, Jackson, Nikol'ski?-type inequalities) (41A17) Asymptotic approximations, asymptotic expansions (steepest descent, etc.) (41A60) 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.

Review text

In many areas of approximation theory and applications such as sampling, discretisation of integrals and especially of norms defined by integrals is essential. A key question is the distribution of the evaluation points that defined the finite sums which are employed to approximate the integral. In other words, one wants to know which distributions are optimal in some sense, minimising the number of points and maximising the accuracy. In this paper, very powerful results are presented which give bounds on the accuracy of these discretisations that are fulfilled with high probability. The interesting point is that these points are best chosen randomly. The discretisation problems can be formed as sampling discretisation where for a fixed (finite) dimensional function space upper and lower bounds of the discretised version of the norms are sought by the actual \(p\)-norms (so-called Marcinkiewicz-type discretisaton theorems). These upper and lower bounds have of course some fixed numerical factors that turn out to be \(1\mp\frac12\). On top of this, the article studies the problem of universal discretization where for a finite selection of fixed (finite) dimensional function spaces (\(k\) of them, say), upper and lower bounds of the discretised version of the norms are sought by the actual \(p\)-norms. Of course one is also interested in minimising the number of sampling points in the discretisation when the Marcinkiewicz-type discretisaton bounds are sought. The subspaces that are used are in this case subspaces generated by so-called dictionaries. The article's main and remarkable results provide lower bounds on the probability that the estimates are reached for upper and lower factors \(1\mp\frac12\) under the condition that the number of sampling points too satisfies a lower bound that depends on the size of the dictionary. A greedy (descent) method is also presented (in another main theorem) to give sparse recovery results.

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

(18)

• On universal sampling recovery in the uniform norm
• Universal sampling discretization
• Tractability of sampling recovery on unweighted function classes
• One-sided discretization inequalities and sampling recovery
• Sparse-grid sampling recovery and numerical integration of functions having mixed smoothness
• Sparse approximation and sampling recovery on function classes with a structural condition
• Some lower bounds for optimal sampling recovery of functions with mixed smoothness
• Sampling recovery of functions with mixed smoothness
• Research work at the Chair of Theory of Functions and Functional Analysis
• Bounds for the sampling discretization error and their applications to the universal sampling discretization
• Universal discretization and sparse recovery
• Sampling recovery on function classes with a structural condition
• Sparse sampling recovery in integral norms on some function classes
• Best m-term trigonometric approximation in weighted Wiener spaces and applications
• Lebesgue type inequalities in sparse sampling recovery
• Approximation of functions: optimal sampling and complexity
• Sparse sampling recovery by greedy algorithms
• Some theoretical and practical results on noisy signals recovery

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)