Tractability of sampling recovery on unweighted function classes

David Krieg

doi:10.1090/bproc/216

journal article Open Access May 15, 2024

Tractability of sampling recovery on unweighted function classes

Proceedings of the American Mathematical Society, Series B Vol. 11 No. 12 pp. 115-125 · American Mathematical Society (AMS)

View at Publisher Save 10.1090/bproc/216

Abstract

It is well-known that the problem of sampling recovery in the

L
2

L_2

-norm on unweighted Korobov spaces (Sobolev spaces with mixed smoothness) as well as classical smoothness classes such as Hölder classes suffers from the curse of dimensionality. We show that the problem is tractable for those classes if they are intersected with the Wiener algebra of functions with summable Fourier coefficients. In fact, this is a relatively simple implication of powerful results from the theory of compressed sensing. Tractability is achieved by the use of non-linear algorithms, while linear algorithms cannot do the job.

Topics

No keywords indexed for this article. Browse by subject →

References

31

[1]

Bachmayr, Markus "Approximation of high-dimensional rank one tensors" Constr. Approx. (2014) 10.1007/s00365-013-9219-x

[2]

Candes, Emmanuel J. "Near-optimal signal recovery from random projections: universal encoding strategies?" IEEE Trans. Inform. Theory (2006) 10.1109/tit.2006.885507

[3]

Chen, Liang "On the information complexity for integration in subspaces of the Wiener algebra" J. Complexity (2024) 10.1016/j.jco.2023.101819

[4]

Creutzig, Jakob "Linear vs. nonlinear algorithms for linear problems" J. Complexity (2004) 10.1016/j.jco.2004.05.003

[5]

Dai, F. "Random points are good for universal discretization" J. Math. Anal. Appl. (2024) 10.1016/j.jmaa.2023.127570

[6]

Dick, Josef "Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series" J. Approx. Theory (2014) 10.1016/j.jat.2014.03.015

[7]

J. Dick, P. Kritzer, and F. Pillichshammer, Lattice rules, Cham, Switzerland: Springer, 2022. 10.1007/978-3-031-09951-9

[8]

Compressed sensing

D.L. Donoho

IEEE Transactions on Information Theory 2006 10.1109/tit.2006.871582

[9]

Ebert, Adrian "Tractability of approximation in the weighted Korobov space in the worst-case setting—a complete picture" J. Complexity (2021) 10.1016/j.jco.2021.101571

[10]

Foucart, Simon (2013) 10.1007/978-0-8176-4948-7

[11]

Garnaev, A. Yu. "The widths of a Euclidean ball" Dokl. Akad. Nauk SSSR (1984)

[12]

Gluskin, E. D. "Norms of random matrices and diameters of finite-dimensional sets" Mat. Sb. (N.S.) (1983)

[13]

Goda, Takashi "Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series" Proc. Amer. Math. Soc. (2023) 10.1090/proc/16444

[14]

Heinrich, Stefan "The inverse of the star-discrepancy depends linearly on the dimension" Acta Arith. (2001) 10.4064/aa96-3-7

[15]

Hickernell, Fred J. "Tractability of multivariate integration for periodic functions" J. Complexity (2001) 10.1006/jcom.2001.0592

[16]

Hinrichs, A. "The curse of dimensionality for numerical integration of smooth functions" Math. Comp. (2014) 10.1090/s0025-5718-2014-02855-x

[17]

Hinrichs, Aicke "Product rules are optimal for numerical integration in classical smoothness spaces" J. Complexity (2017) 10.1016/j.jco.2016.09.001

[18]

Jackson, Dunham (1994)

[19]

Jahn, Thomas "Sampling numbers of smoothness classes via ℓ¹-minimization" J. Complexity (2023) 10.1016/j.jco.2023.101786

[20]

D.Krieg and P.Kritzer, Homogeneous algorithms and solvable problems on cones, Journal of Complexity, Volume 83, August 2024, 101840. See \url{https://doi.org/10.1016/j.jco.2024.101840}. 10.1016/j.jco.2024.101840

[21]

Krieg, David "Recovery algorithms for high-dimensional rank one tensors" J. Approx. Theory (2019) 10.1016/j.jat.2018.08.002

[22]

Kuo, F. Y. "Quasi-Monte Carlo methods for high-dimensional integration: the standard (weighted Hilbert space) setting and beyond" ANZIAM J. (2011) 10.1017/s1446181112000077

[23]

Mayer, Sebastian "Entropy and sampling numbers of classes of ridge functions" Constr. Approx. (2015) 10.1007/s00365-014-9267-x

[24]

Novak, Erich "Tractability of the approximation of high-dimensional rank one tensors" Constr. Approx. (2016) 10.1007/s00365-015-9282-6

[25]

Novak, Erich "Tractability of approximation for weighted Korobov spaces on classical and quantum computers" Found. Comput. Math. (2004) 10.1007/s10208-002-0074-6

[26]

Rauhut, Holger "Interpolation via weighted ℓ₁ minimization" Appl. Comput. Harmon. Anal. (2016) 10.1016/j.acha.2015.02.003

[27]

Sloan, Ian H. "When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?" J. Complexity (1998) 10.1006/jcom.1997.0463

[28]

M.Sonnleitner and M.Ullrich, On the power of iid information for linear approximation, J. Appl. Num. Anal. 1 (2023), 88–126. 10.30970/ana.2023.1.88

[29]

Vybíral, Jan "Widths of embeddings in function spaces" J. Complexity (2008) 10.1016/j.jco.2008.01.002

[30]

Wasilkowski, G. W. "Finite-order weights imply tractability of linear multivariate problems" J. Approx. Theory (2004) 10.1016/j.jat.2004.06.011

[31]

Xu, Guiqiao "On weak tractability of the Smolyak algorithm for approximation problems" J. Approx. Theory (2015) 10.1016/j.jat.2014.10.016

Metrics

5

Citations

31

References

Details

Published: May 15, 2024
Vol/Issue: 11(12)
Pages: 115-125
License: View

Authors

D

David Krieg

Funding

Austrian Science Fund Award: M 3212-N

Cite This Article

David Krieg (2024). Tractability of sampling recovery on unweighted function classes. Proceedings of the American Mathematical Society, Series B, 11(12), 115-125. https://doi.org/10.1090/bproc/216

Tractability of sampling recovery on unweighted function classes

You May Also Like