Tractability of sampling recovery on unweighted function classes (Q6550282)

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.