Sparse Harmonic Transforms: A New Class of Sublinear-Time Algorithms for Learning Functions of Many Variables

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., 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 vertical bar B vertical bar = N. Herein we will develop methods that rapidly approximate any functionfthat is sparse in the BOPB, that is,f: D subset of R-D -> C of the form f(x)= Sigma(b is an element of S) c(b)center dot b(x) with S subset of B of cardinality vertical bar S vertical bar = 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 fromfalong a randomly constructed grid G subset of 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 iteration. It has a runtime of just(slogN)O(1), uses only(slogN)O(1) function evaluations on the fixed and nonadaptive grid G, and requires not more than(slogN)O(1) bits of memory. We emphasize that nothing about S or any of the coefficientscb is an element of Cis assumed in advance other than that S subset of B has |S| <= s. Both S and its related coefficientscb will be learned from the given function evaluations by the developed method. For s << N, the runtime(slogN)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 assublinear-time. This and the similarly reduced sample and memory requirements set our algorithm apart from previous works based on standard compressive sensing algorithms such as basis pursuit which typically store and utilize full intermediate basis representations of size omega(N) during the solution process.