Tractability of sampling recovery on unweighted function classes
Approximation by arbitrary nonlinear expressions; widths and entropy (41A46) Multidimensional problems (41A63) Trigonometric approximation (42A10) Algorithms for approximation of functions (65D15) Numerical integration (65D30) Numerical approximation of high-dimensional functions; sparse grids (65D40)
Recovering a signal in the set of square-integrable functions from a set of samples is an important application within, for example, the theory and applications of compressed sensing. This should be carried out in high-dimensional ambient spaces, but as so many tasks in approximation theory, the algorithms suffer from the ubiquitous so-called ``curse of dimensionality. That is, even for moderate dimensions \(d\) the problems become completely inefficient to solve in practice.\N\NThe problem is overcome in this contribution by restricting the functions to those that can be expanded with summable Fourier coefficients (the so-called Wiener algebra). The algorithms are non-linear, but the mentioned problems that appear both for Hölder classes of approximands as well as for Sobolev spaces with functions of mixed smoothness are solved.
- Sampling numbers of smoothness classes via \(\ell^1\)-minimization
- Weighted frames of exponentials and stable recovery of multidimensional functions from nonuniform Fourier samples
- Infinite-dimensional compressed sensing and function interpolation
- A note on sampling recovery of multivariate functions in the uniform norm
- On the informativeness of linear functionals.
- A mathematical introduction to compressive sensing
- Approximation of high-dimensional rank one tensors
- Compressed sensing
- Entropy and sampling numbers of classes of ridge functions
- Finite-order weights imply tractability of linear multivariate problems
- Homogeneous algorithms and solvable problems on cones
- scientific article; zbMATH DE number 3838682 (Why is no real title available?)
- Interpolation via weighted \(\ell_{1}\) minimization
- Lattice Rules
- Linear vs. nonlinear algorithms for linear problems
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series
- On the information complexity for integration in subspaces of the Wiener algebra
- On weak tractability of the Smolyak algorithm for approximation problems
- Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
- Product rules are optimal for numerical integration in classical smoothness spaces
- Quasi-Monte Carlo methods for high-dimensional integration: the standard (weighted Hilbert space) setting and beyond
- Random points are good for universal discretization
- Recovery algorithms for high-dimensional rank one tensors
- Sampling numbers of smoothness classes via \(\ell^1\)-minimization
- The curse of dimensionality for numerical integration of smooth functions
- The inverse of the star-discrepancy depends linearly on the dimension
- Tractability of approximation for weighted Korobov spaces on classical and quantum computers
- Tractability of approximation in the weighted Korobov space in the worst-case setting -- a complete picture
- Tractability of multivariate integration for periodic functions
- Tractability of the approximation of high-dimensional rank one tensors
- When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
- Widths of embeddings in function spaces
- Sampling numbers of smoothness classes via \(\ell^1\)-minimization
- Sampling and entropy numbers in the uniform norm
- Tractability results for integration in subspaces of the Wiener algebra
- The \(L_p\)-discrepancy for finite \(p>1\) suffers from the curse of dimensionality
- Best m-term trigonometric approximation in weighted Wiener spaces and applications
- Approximation of functions: optimal sampling and complexity
This page was built for publication: Tractability of sampling recovery on unweighted function classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6550282)
