Towards Optimal Sampling for Learning Sparse Approximations in High Dimensions

Ben Adcock (), Juan M. Cardenas (), Nick Dexter () and Sebastian Moraga ()
Additional contact information
Ben Adcock: Simon Fraser University
Juan M. Cardenas: Simon Fraser University
Nick Dexter: Simon Fraser University
Sebastian Moraga: Simon Fraser University

A chapter in High-Dimensional Optimization and Probability, 2022, pp 9-77 from Springer

Abstract: Abstract In this chapter, we discuss recent work on learning sparse approximations to high-dimensional functions on data, where the target functions may be scalar-,’ vector- or even Hilbert space-valued. Our main objective is to study how the sampling strategy affects the sample complexity—that is, the number of samples that suffice for accurate and stable recovery—and to use this insight to obtain optimal or near-optimal sampling procedures. We consider two settings. First, when a target sparse representation is known, in which case we present a near-complete answer based on drawing independent random samples from carefully designed probability measures. Second, we consider the more challenging scenario when such representation is unknown. In this case, while not giving a full answer, we describe a general construction of sampling measures that improves over standard Monte Carlo sampling. We present examples using algebraic and trigonometric polynomials, and for the former, we also introduce a new procedure for function approximation on irregular (i.e. nontensorial) domains. The effectiveness of this procedure is shown through numerical examples. Finally, we discuss a number of structured sparsity models and how they may lead to better approximations.

Date: 2022
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-031-00832-0_2

Ordering information: This item can be ordered from
http://www.springer.com/9783031008320

DOI: 10.1007/978-3-031-00832-0_2

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().