Sparse Harmonic Transforms: A New Class of Sublinear-Time Algorithms for Learning Functions of Many Variables
- PDF / 1,641,214 Bytes
- 55 Pages / 439.37 x 666.142 pts Page_size
- 17 Downloads / 201 Views
Sparse Harmonic Transforms: A New Class of Sublinear-Time Algorithms for Learning Functions of Many Variables Bosu Choi1 · Mark A. Iwen2,3 · Felix Krahmer4 Received: 15 August 2018 / Revised: 11 May 2020 / Accepted: 12 May 2020 © SFoCM 2020
Abstract In this paper we develop fast and memory efficient numerical methods for learning functions of many variables that admit sparse representations in terms of general bounded orthonormal tensor product bases. Such functions appear in many applications including, e.g., various Uncertainty Quantification (UQ) problems involving the solution of parametric PDE that are approximately sparse in Chebyshev or Legendre product bases (Chkifa et al. in Polynomial approximation via compressed sensing of high-dimensional functions on lower sets. arXiv:1602.05823, 2016; Rauhut and Schwab in Math Comput 86(304):661–700, 2017). We expect that our results provide a starting point for a new line of research on sublinear-time solution techniques for UQ applications of the type above which will eventually be able to scale to significantly higher-dimensional problems than what are currently computationally feasible. More concretely, let B be a finite Bounded Orthonormal Product Basis (BOPB) of cardinality |B| = N . Herein we will develop methods that rapidly approximate any function f that is sparse in the BOPB, that is, f : D ⊂ R D → C of the form f (x) =
cb · b(x)
b∈S
with S ⊂ B of cardinality |S| = s N . Our method adapts the CoSaMP algorithm (Needell and Tropp in Appl Comput Harmon Anal 26(3):301–321, 2009) to use additional function samples from f along a randomly constructed grid G ⊂ R D with universal approximation properties in order to rapidly identify the multi-indices of the most dominant basis functions in S component by component during each CoSaMP
Communicated by Francis Bach. Mark Iwen was supported in part by NSF DMS-1416752 and NSF CCF-1615489. Bosu Choi was supported in part by NSF DMS-1416752. Felix Krahmer was supported in part by the German Science foundation in the context of the Emmy Noether junior research group KR 4512/1-1. Extended author information available on the last page of the article
123
Foundations of Computational Mathematics
iteration. It has a runtime of just (s log N )O(1) , uses only (s log N )O(1) function evaluations on the fixed and nonadaptive grid G, and requires not more than (s log N )O(1) bits of memory. We emphasize that nothing about S or any of the coefficients cb ∈ C is assumed in advance other than that S ⊂ B has |S| ≤ s. Both S and its related coefficients cb will be learned from the given function evaluations by the developed method. For s N , the runtime (s log N )O(1) will be less than what is required to simply enumerate the elements of the basis B; thus our method is the first approach applicable in a general BOPB framework that falls into the class referred to as sublinear-time. This and the similarly reduced sample and memory requirements set our algorithm apart from previous works based on standard compressive sensin
Data Loading...
