Tractability of sampling recovery on unweighted function classes
type: Item
instance of: scholarly article
title: Tractability of sampling recovery on unweighted function classes
zbMATH Open document ID: 1540.41061
author: David Krieg
published in: Proceedings of the American Mathematical Society. Series B
publication date: 2024-06-05T00:00:00Z
review text: 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.
reviewed by: Martin D. Buhmann
Mathematics Subject Classification ID: 41A63
Mathematics Subject Classification ID: 41A46
Mathematics Subject Classification ID: 65D40
Mathematics Subject Classification ID: 42A10
Mathematics Subject Classification ID: 65D15
Mathematics Subject Classification ID: 65D30
zbMATH DE Number: 7860049
zbMATH Keywords: sampling recovery
zbMATH Keywords: Wiener algebras
zbMATH Keywords: summable Fourier coefficients
zbMATH Keywords: compressed sensing
MaRDI profile type: MaRDI publication profile
cites work: Approximation of high-dimensional rank one tensors
cites work: Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
cites work: On the information complexity for integration in subspaces of the Wiener algebra
cites work: Linear vs. nonlinear algorithms for linear problems
cites work: Random points are good for universal discretization
cites work: Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series
cites work: Lattice Rules
cites work: Compressed sensing
cites work: Tractability of approximation in the weighted Korobov space in the worst-case setting -- a complete picture
cites work: A mathematical introduction to compressive sensing
cites work: Q3310375
cites work: Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
cites work: The inverse of the star-discrepancy depends linearly on the dimension
cites work: Tractability of multivariate integration for periodic functions
cites work: The curse of dimensionality for numerical integration of smooth functions
cites work: Product rules are optimal for numerical integration in classical smoothness spaces
cites work: Sampling numbers of smoothness classes via \(\ell^1\)-minimization
cites work: Homogeneous algorithms and solvable problems on cones
cites work: Recovery algorithms for high-dimensional rank one tensors
cites work: Quasi-Monte Carlo methods for high-dimensional integration: the standard (weighted Hilbert space) setting and beyond
cites work: Entropy and sampling numbers of classes of ridge functions
cites work: Tractability of the approximation of high-dimensional rank one tensors
cites work: Tractability of approximation for weighted Korobov spaces on classical and quantum computers
cites work: Interpolation via weighted \(\ell_{1}\) minimization
cites work: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
cites work: Widths of embeddings in function spaces
cites work: Finite-order weights imply tractability of linear multivariate problems
cites work: On weak tractability of the Smolyak algorithm for approximation problems
DOI: 10.1090/BPROC/216
description: scientific article; zbMATH DE number 7860049