PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal approximation of infinite-dimensional holomorphic functions II: recovery from i.i.d. pointwise samples

Ben Adcock, Nick Dexter, Sebastian Moraga

arXiv:2310.16940v3math.NAcs.NA

TL;DR

Recovering infinite-dimensional holomorphic functions from samples matters for surrogate construction, but prior lower-bound results did not directly address pointwise sampling. This paper gives explicit least-squares and compressed-sensing procedures for i.i.d. Jacobi samples and shows that their rates are near-optimal for Hilbert-valued functions.

  • Problem

    Pointwise samples are the practical input for surrogate construction, but prior m-width lower bounds based on arbitrary measurements do not directly establish recovery guarantees for them.

    Source: §1 · p. 2

  • Method

    The paper uses least-squares or compressed-sensing reconstruction with Jacobi polynomial expansions for i.i.d. samples from tensor-product Jacobi measures.

    Source: §1 · p. 2, §4.3 · p. 9

  • Results

    For Hilbert-valued functions, i.i.d. pointwise samples from essentially arbitrary tensor-product Jacobi measures achieve rates close to the m-width lower bounds.

    Source: §1 · p. 2, §1.1 · p. 3, §3 · p. 7

  • Takeaways & Limitations

    The results identify i.i.d. pointwise samples as near-optimal information for recovering the studied holomorphic functions and provide explicit recovery procedures.

    Source: §1 · p. 2

    The matching upper-bound results apply to Hilbert-valued functions; comparable upper bounds for Banach-valued functions remain unknown.

    Source: §4.3 · p. 9

Abstract

from arXiv · show

Infinite-dimensional, holomorphic functions have been studied in detail over the last several decades, due to their relevance to parametric differential equations and computational uncertainty quantification. The approximation of such functions from finitely many samples is of particular interest, due to the practical importance of constructing surrogate models to complex mathematical models of physical processes. In a previous work, [6] we studied the approximation of so-called Banach-valued, $(\boldsymbol{b},\varepsilon)$-holomorphic functions on the infinite-dimensional hypercube $[-1,1]^{\mathbb{N}}$ from $m$ (potentially adaptive) samples. In particular, we derived lower bounds for the adaptive $m$-widths for classes of such functions, which showed that certain algebraic rates of the form $m^{1/2-1/p}$ are the best possible regardless of the sampling-recovery pair. In this work, we continue this investigation by focusing on the practical case where the samples are pointwise evaluations drawn identically and independently from a probability measure. Specifically, for Hilbert-valued $(\boldsymbol{b},\varepsilon)$-holomorphic functions, we show that the same rates can be achieved (up to a small polylogarithmic or algebraic factor) for essentially arbitrary tensor-product Jacobi (ultraspherical) measures. Our reconstruction maps are based on least squares and compressed sensing procedures using the corresponding orthonormal Jacobi polynomials. In doing so, we strengthen and generalize past work that has derived weaker nonuniform guarantees for the uniform and Chebyshev measures (and corresponding polynomials) only. We also extend various best $s$-term polynomial approximation error bounds to arbitrary Jacobi polynomial expansions. Overall, we demonstrate that i.i.d.\ pointwise samples are near-optimal for the recovery of infinite-dimensional, holomorphic functions.

1 Introduction

Infinite-dimensional parametric models can make direct evaluation costly, while limited samples and the curse of dimensionality complicate surrogate construction. This paper develops explicit recovery procedures for Hilbert-valued holomorphic functions from i.i.d. pointwise samples, extending the analysis to tensor-product Jacobi measures and obtaining rates close to prior lower bounds.

1 Introduction

  • Costly differential-equation solves, limited samples, and infinite dimensionality make nonintrusive surrogate construction challenging.The target functions map parameters to outputs in an infinite-dimensional function space.Source: §1 · p. 2
  • The earlier m-width analysis showed that rates cannot be faster than m^(1/2−1/p) under the stated summability assumptions, but did not address pointwise samples.The lower bounds applied to arbitrary adaptive linear measurements and reconstruction maps.Source: §1 · p. 2

1.1 Contributions and related work

  • Explicit recovery procedures achieve rates close to prior m-width lower bounds from i.i.d. pointwise samples for Hilbert-valued functions.The bounds hold in expectation and probability, with rates uniform in b under the stated known- or unknown-anisotropy assumptions.Source: §1 · p. 2, §1.1 · p. 3
  • The analysis generalizes polynomial approximation bounds and recovery procedures from Chebyshev or Legendre polynomials to arbitrary tensor-product Jacobi polynomials.The broader measure class also has practical relevance when parameters follow beta distributions.Source: §1.1 · pp. 3–4

2 Preliminaries

The preliminaries define the function classes and approximation framework used in the paper, then recap prior m-width lower bounds. Those bounds provide the benchmark for the paper’s i.i.d. Jacobi-sample recovery results.

2.2 The space of (b, ε)-holomorphic functions

  • The function class uses a sequence b to encode variable-wise smoothness and defines holomorphicity through extension to a specified complex region.The scale parameter ε can be rescaled to 1 in this paper.Source: §2.2 · p. 5
  • Known anisotropy allows the reconstruction map to depend on b, whereas unknown anisotropy requires it to be independent of b.The paper considers Hilbert-valued functions on the infinite-dimensional hypercube and tensor-product probability measures.Source: §2.2 · p. 5, §3 · p. 6
  • Prior lower bounds show that no sampling-recovery pair can beat m^(1/2−1/p) in the stated known-anisotropy and restricted unknown-anisotropy settings.For the unrestricted unknown-anisotropy class H(p), finite-sample approximation is impossible because important variables can occur in infinitely many configurations.Source: §3 · pp. 6–7
  • Suitable recovery maps can nearly achieve the m^(1/2−1/p) rates from i.i.d. pointwise samples drawn from general tensor-product Jacobi measures.The reconstruction uses the corresponding tensor Jacobi polynomials.Source: §3 · p. 7

4 Main results

The results treat tensor-product Jacobi measures with uniformly bounded parameters and give distinct reconstruction guarantees for known and unknown anisotropy. The discussion identifies rate, logarithmic-factor, and Hilbert-space boundaries.

4.1 Jacobi measures

  • The tensor-product Jacobi results assume uniformly bounded α_j and β_j, a condition under which the paper's lower bounds apply.Assumption 4.1 requires τ^-1 ≤ α_j, β_j ≤ 1/τ for every j.Source: §4.1 · p. 8

4.2 Upper bounds in expectation

  • Known-anisotropy recovery uses least squares, while unknown-anisotropy recovery uses compressed sensing with a reconstruction map independent of both b and p.The known-anisotropy map may depend on b, p, α, and β; the unknown-anisotropy map depends on α and β.Source: §4.2 · p. 8

4.3 Discussion

  • The lower bounds apply to Banach-valued functions, but the main upper-bound results cover only Hilbert-valued functions; matching Banach-valued upper bounds remain unknown.The paper notes that prior Banach-valued upper bounds for Legendre and Chebyshev approximations have slower algebraic rates.Source: §4.3 · p. 9
  • The second expectation bounds trade a logarithmic factor for an arbitrarily small reduction in the algebraic rate because the proof cannot uniformly bound the constants.The constants cannot be bounded uniformly over the specified unit balls of b sequences using the current proof techniques.Source: §4.3 · p. 9
  • The paper suspects the i.i.d. sampling rate may retain a logarithmic factor, while non-i.i.d. sampling may permit its removal.The suspected rate is (m/log(m))^(1/2−1/p) for the stated function class; the possibility of removing the factor with non-i.i.d. samples is presented tentatively.Source: §4.3 · p. 9
  • The compressed-sensing approach requires a weighted RIP, which contributes a log^4(m) factor to Theorem 4.3's first bound.Improving logarithmic factors in RIP-type estimates is described as a challenging open problem.Source: §4.3 · pp. 9–10
  • A least-squares alternative for unknown anisotropy has a strictly slower θ_m(b) rate and requires a reconstruction map that depends on p.The alternative uses a dominating sequence b_p to obtain bounds for admissible b.Source: §4.3 · p. 10

4.4 Upper bounds in probability

  • For the in-probability results, known-anisotropy guarantees concern a fixed b, whereas the unknown-anisotropy guarantee covers events for all admissible b and p.The known-anisotropy reconstruction map depends on b; the unknown-anisotropy map is independent of b.Source: §4.4 · pp. 10–11

5 Jacobi polynomial expansions and best polynomial approximation

This section develops tensor-product Jacobi polynomial expansions and establishes coefficient summability bounds for holomorphic functions. It uses weighted and anchored Stechkin inequalities to derive best-term approximation results with nested index sets, providing estimates used in the paper’s recovery analysis.

5.2 Jacobi polynomial expansions

  • The tensorized Jacobi polynomials form an orthonormal basis of L2ρ(U), allowing Hilbert- or Banach-valued functions in L2ρ(U; V) to be expanded with coefficients in V.The basis is formed by tensorizing the univariate orthonormal Jacobi polynomials.Source: §5.1 · p. 11, §5.2 · p. 12

5.1 Jacobi polynomials

  • Assumption 4.1 controls the growth of constituent Jacobi polynomials’ L∞ norms, a key ingredient in the weighted best-approximation bounds.The assumption is equivalent to a polynomial growth bound whose polynomial depends only on α and β.Source: §5.1 · p. 12

5.3 ℓp spaces, norms and best approximation of sequences

  • The section defines sequence norms and best-term errors in unweighted, weighted, and anchored settings to describe polynomial-coefficient approximation.Anchored approximation uses a minimal anchored majorant of coefficient magnitudes.Source: §5.3 · pp. 12–13

5.4 Best approximation of polynomial coefficients

  • Theorem 5.3 gives an anchored best s-term approximation bound, also valid in the stronger weighted ℓq u(F; V)-norm.The sets can be chosen nested as s increases.Source: §5.4 · p. 14

5.5 Bounds for Jacobi polynomial coefficients of holomorphic functions and an abstract summability lemma

  • Lemma 5.4 bounds tensor Jacobi coefficients of functions holomorphic in Eρ, and Lemma 5.5 establishes ℓp and anchored ℓp summability for sequences satisfying a corresponding bound.The abstract lemma also provides uniform constant bounds; combined with Lemma 5.4, it yields summability results for arbitrary Jacobi coefficients.Source: §5.5 · pp. 15–16
  • For normalized b in ℓp M(N), the coefficient-bound constants are uniformly controlled in terms of p, r, ε, c, γ, and ξ, completing the proofs of (5.20) and (5.18).The proof bounds C2 by a parameter-dependent constant using the summability of the surrogate sequence.Source: §5.5 · p. 21

5.6 Proofs of Theorems 5.2 and 5.3

  • Theorem 5.2’s proof establishes weighted coefficient summability and uses weighted Stechkin to construct nested sets for the best-term approximation bound.The sets depend on k, b, and the intrinsic weights determined by α and β.Source: §5.6 · p. 22
  • Theorem 5.3’s proof uses an anchored majorant and Stechkin’s inequality to obtain the anchored approximation bound with nested anchored index sets.The sets are constructed from the largest entries of the anchored majorant.Source: §5.6 · pp. 22–23

6 Proofs of Theorems 4.5 and 4.6

This section proves reconstruction guarantees for known and unknown anisotropy using tensor-product Jacobi polynomials and high-probability bounds, and describes the reconstruction maps. The proof of Theorem 4.6 uses a sharper probabilistic bound to allow a smaller n, though the implications for uniform rates remain unclear.

6.1 Reconstruction map: known anisotropy

  • For known anisotropy, the map reorders b into nonincreasing order and uses the corresponding tensor-product Jacobi polynomials to construct its index sets and least-squares reconstruction.The permutation lets the bound depend on the monotone rearrangement bπ and yield θm(p), rather than only θm(p, M).Source: §6.1 · pp. 23–24

6.2 Proof of Theorem 4.5

  • For known anisotropy, Theorem 4.5 gives a uniform high-probability bound for arbitrary Jacobi polynomials, stronger than the nonuniform Chebyshev- or Legendre-only guarantee in [4, Thm. 4.4].The proof splits the error across nested index sets and uses repeated matrix Chernoff bounds to obtain a guarantee independent of f.Source: §6.2 · pp. 24, 27

6.3 Reconstruction map: unknown anisotropy

  • For unknown anisotropy, the reconstruction map uses a compressed sensing problem and achieves the factor log^4(m)g(m), where g(m) → +∞ subalgebraically; Theorems 4.3 and 4.6 follow with g(m) = log(m).Its finite index set contains every anchored set of size at most n.Source: §6.3 · pp. 27–28

6.4 Proof of Theorem 4.6

  • For any m ≥ 3, combining the two cases yields a guarantee with probability at least 1 − ǫ, allowing C1 and C2 to change by constants independent of b.For a uniform guarantee, the proof bounds ∥e∥2;V deterministically by ∥f − fΛ∥L∞(U;V).Source: §6.4 · p. 30
  • Using an L2ρ(U;V) bound with Bernstein’s inequality permits n ≈ m/(c0L), whereas the cruder bound requires larger n and raises the reconstruction cost, which scales linearly with N = |Λ|.It remains unclear whether uniform bounds with Theorem 4.6’s convergence rate hold for the smaller n.Source: §6.4 · p. 31

7 Proofs of Theorems 4.2 and 4.3

The proofs combine reconstruction maps with probability-event bounds to establish the results of Theorems 4.2 and 4.3. They remove logarithmic factors by choosing an auxiliary exponent arbitrarily close to p.

Proofs of Theorems 4.2 and 4.3

  • Theorem 4.2’s bound is obtained by controlling the reconstruction error on an event and its complement, then applying total expectation.The proof removes the log(m) factor because t can be chosen arbitrarily in (p, 1), up to a change in the constant.Source: §7 · pp. 31–32
  • The reconstruction map T:(U × V)^m→L2ρ(U;V) is defined by T=C◦T0; the proof treats E and its complement separately before applying the law of total expectation.The log^4(m)g(m) factor is removed because t∈(p,1) is arbitrary and g grows subalgebraically fast in m, up to a possible change in the constant eC(p,t,g,τ).Source: §7 · pp. 31, 32, 34
  • Theorem 4.3’s second part applies Theorem 4.5 with an exponent t greater than p and invokes Theorems 5.2 and 5.3.The proof uses the resulting event bound and total expectation to obtain the final estimate.Source: §7 · pp. 32–34

A Supporting results on Jacobi polynomials

The appendix supplies Jacobi-polynomial estimates and supporting results on how approximation-width quantities behave under coordinate permutations. It also relates a polynomial-growth assumption to Assumption 4.1.

A Supporting results on Jacobi polynomials

  • The appendix develops Jacobi-polynomial bounds used in the proofs of Theorems 5.2 and 5.3.It introduces a uniform-growth lemma for orthonormal Jacobi polynomials and supporting polynomial estimates.Source: A Supporting results on Jacobi… · pp. 34–35
  • Proposition A.4 states that Assumption A.3 is equivalent to Assumption 4.1; A.3 requires a polynomial p, depending on α and β, to bound the univariate Jacobi polynomials in L∞([-1,1]) for every ν_j and j.Assumption A.3 can hold only if α_i and β_i are uniformly bounded away from −1.Source: A Supporting results on Jacobi… · pp. 35–36
  • Under a coordinate permutation, the width quantity is expressed using the permuted sequence and measure; for identical coordinate measures, the width is unchanged.The appendix also states that the corresponding terms in (3.3) coincide for a tensor product of one repeated measure.Source: A Supporting results on Jacobi… · pp. 36–37

C Notation

The section points readers to a table of the paper’s notation and states how notation changes for scalar-valued spaces and norms.

C Notation

  • Table 1 summarizes the paper’s notation; scalar-valued spaces and norms omit the ; V marker.Source: C Notation · p. 37
Loading 2310.16940v3…