PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal approximation of infinite-dimensional holomorphic functions

Ben Adcock, Nick Dexter, Sebastian Moraga

arXiv:2305.18642v2math.NAcs.NA

TL;DR

Approximating infinite-dimensional functions from samples is challenging when evaluations are expensive, and the limits of such approximation for Banach-valued holomorphic functions are not well characterized. The paper uses m-widths to establish lower and upper bounds for known and unknown anisotropy. It finds near-matching rates when approximation is possible, but finite-sample approximation is impossible in the unrestricted unknown-anisotropy class H(p).

  • Problem

    Finite-sample approximation of expensive, unknown infinite-dimensional functions is important, but the limits for the studied function classes have received little attention.

    Source: §1 · p. 2

  • Method

    The paper estimates adaptive m-widths using lower-bound theory for Gelfand, Kolmogorov, and general m-widths, and establishes upper bounds for sampling and reconstruction.

    Source: §4.2 · p. 7

  • Results

    Rates close to m^(1/2−1/p) are established when bounds decay, while approximation from finite samples is impossible in H(p) without an ordering of variables.

    Source: §1 · p. 2, §4.3.1 · p. 9, §6 · p. 26

  • Takeaways & Limitations

    The results distinguish the monotone unknown-anisotropy case, where optimal recovery is attainable, from H(p), where no decay of the m-width occurs.

    Source: §4.3.1 · p. 9, §6 · p. 26

    The upper-bound theorems consider the uniform probability measure, and whether their rates extend to Banach-valued V remains open for Theorem 4.7.

    Source: §4.3.2 · p. 11

Abstract

from arXiv · show

Over the last decade, approximating functions in infinite dimensions from samples has gained increasing attention in computational science and engineering, especially in computational uncertainty quantification. This is primarily due to the relevance of functions that are solutions to parametric differential equations in various fields, e.g. chemistry, economics, engineering, and physics. While acquiring accurate and reliable approximations of such functions is inherently difficult, current benchmark methods exploit the fact that such functions often belong to certain classes of holomorphic functions to get algebraic convergence rates in infinite dimensions with respect to the number of (potentially adaptive) samples $m$. Our work focuses on providing theoretical approximation guarantees for the class of $(\boldsymbol{b},\varepsilon)$-holomorphic functions, demonstrating that these algebraic rates are the best possible for Banach-valued functions in infinite dimensions. We establish lower bounds using a reduction to a discrete problem in combination with the theory of $m$-widths, Gelfand widths and Kolmogorov widths. We study two cases, known and unknown anisotropy, in which the relative importance of the variables is known and unknown, respectively. A key conclusion of our paper is that in the latter setting, approximation from finite samples is impossible without some inherent ordering of the variables, even if the samples are chosen adaptively. Finally, in both cases, we demonstrate near-optimal, non-adaptive (random) sampling and recovery strategies which achieve close to same rates as the lower bounds.

1 Introduction

The introduction motivates sample-based approximation of expensive, infinite-dimensional Banach-valued functions and asks what accuracy finite samples can achieve. It establishes lower bounds for known and unknown anisotropy and upper bounds showing near-optimal rates are attainable.

1 Introduction

  • The work addresses Banach-valued functions arising in infinite-dimensional models, including models of physical processes and parametric differential equations.The introduction situates these models in applications including biology, chemistry, economics, and engineering.Source: §1 · pp. 1–2
  • Finite-sample approximation is important because the target functions are often unknown and expensive to evaluate through simulations or physical experiments.Nonintrusive surrogate models use pointwise samples to construct approximations that are accurate and inexpensive to use.Source: §1 · p. 2
  • The lower bounds show that no adaptive sampling operator and reconstruction map can beat the rate m^(1/2−1/p) for the stated function classes.The upper bounds achieve this rate up to a possible logarithmic factor; the paper studies known and unknown anisotropy separately.Source: §1 · p. 2
  • The paper estimates m-widths using information-based complexity, including lower estimates for Gelfand and Kolmogorov widths.These widths frame limits on sampling and reconstruction.Source: §1 · p. 2

2 Preliminaries

The preliminaries establish notation and the function-space setting used for the paper’s approximation problems.

2.1 Notation

  • The notation section specifies multi-indices, componentwise ordering, Hadamard products, weighted ℓp spaces, and coordinate restrictions.It also distinguishes finite-dimensional sequence spaces and weighted (quasi-)norm unit balls.Source: §2.1 · p. 3

2.2 Lebesgue–Bochner spaces

  • The paper works with functions on the infinite-dimensional hypercube U = [−1, 1]^N, taking values in a Banach space V.A probability measure on U is built as a tensor product of a univariate Borel probability measure on [−1, 1].Source: §2.2 · pp. 3–4
  • Lebesgue–Bochner spaces Lq_ρ(U; V) provide the normed setting for strongly measurable V-valued functions with finite norm.For V = R, the paper writes L2_ρ(U; R) as L2_ρ(U).Source: §2.2 · p. 4

3 The space of (b, ε)-holomorphic functions and anisotropy

The paper studies holomorphic function classes whose anisotropy parameter describes variable-wise smoothness. It distinguishes known anisotropy from unknown anisotropy, where the reconstruction procedure cannot use that parameter.

3.1 (b, ε)-holomorphic functions

  • A function is (b, ε)-holomorphic when it is holomorphic in a region determined by b and ε; the paper takes ε = 1 without loss of generality by rescaling b.The region is described using Bernstein polyellipses, and the class is relevant because solution maps of many common parametric differential equations belong to it.Source: §3.1 · p. 4
  • The class H(b) is studied with b in ℓp(N), while the paper also considers the more structured monotone ℓp setting.Best s-term polynomial approximation has rate s^(1/2−1/p); under the monotone condition, approximation can use anchored sets that are more amenable to computation.Source: §3.1 · pp. 4–5

3.2 Known versus unknown anisotropy

  • The anisotropy parameter b describes variable-wise smoothness: larger b_i corresponds to less smoothness in y_i, while smaller or zero b_i corresponds to greater smoothness.This relation follows from the admissible polyellipse parameters in the definition.Source: §3.2 · p. 5
  • The paper treats known anisotropy, where reconstruction can use b, and unknown anisotropy, where reconstruction has no access to b.In black-box uncertainty-quantification settings, the behavior of the target with respect to its variables, and therefore b, is a priori unknown.Source: §3.2 · p. 5

4 Summary and main results

This section defines adaptive sampling and m-widths, then bounds recovery error for known and unknown anisotropy. The bounds show when finite-sample approximation can decay and describe nonadaptive sampling strategies that approach the lower bounds.

4.1 Sampling operators

  • Adaptive sampling allows each later sample to depend on earlier measurements; the Banach-valued definition supports lower bounds under an additional condition.Whether those bounds hold in the Banach-valued case without that condition remains open.Source: §4.1 · pp. 6–7

4.2 Adaptive m-widths

  • The m-width measures the best worst-case recovery error over a function class, optimized over sampling and reconstruction maps.The sampling operator takes m V-valued measurements, while reconstruction maps those measurements into the target space.Source: §4.2 · p. 7
  • The m-width framework extends scalar-valued measurements to Banach-valued measurements, which are relevant for sampling-based approximation of parametric PDEs.The standard definitions use measurements in R^m.Source: §4.2 · p. 7

4.3.1 Lower bounds

  • For known anisotropy, the lower bounds show that m^(1/2−1/p) is sharp across unit-norm b, and nearly sharp for a fixed b.The fixed sequence can be chosen using a slowly growing function g.Source: §4.3.1 · pp. 8–9
  • In the unknown-anisotropy class H(p), the m-width does not decay, while restricting to H(p, M) restores a lower bound of order m^(1/2−1/p).The H(p) result means approximation from finite samples is impossible in that class.Source: §4.3.1 · p. 9

4.3.2 Upper bounds

  • For fixed known b, a nonadaptive linear sampler and reconstruction attain the m^(1/2−1/p) rate, with a constant depending on b.The sampling operator computes Legendre coefficients from an index set selected using b, and reconstruction forms the corresponding polynomial expansion.Source: §4.3.2 · p. 10
  • For unknown anisotropy, the upper-bound strategy treats polynomial coefficients as approximately sparse and uses Gaussian measurements with nonlinear ℓ1-minimization recovery.The coefficient vector is truncated using a hyperbolic-cross index set under the monotone ℓp assumption.Source: §4.3.2 · pp. 10–11
  • In the unknown-anisotropy setting, nonadaptive random sampling and recovery approach the lower-bound rate; one bound attains m^(1/2−1/p) with a constant depending on b.The reconstruction is independent of b and p; for the other bound, the rate can be arbitrarily close to, but not equal to, the exponent.Source: §4.3.2 · p. 11

5 Proof of main theorems

The proofs establish the main theorems through discrete approximation and width estimates for lower bounds, polynomial expansions for upper bounds, and recovery arguments for unknown anisotropy. They also analyze Gaussian sampling with Hilbert-valued basis pursuit to derive probability and expected error bounds.

5.1 Widths and standard results on widths

  • The proof overview reviews Gelfand, adaptive compressive, and Kolmogorov widths and their relationships as tools for lower bounds.The adaptive compressive m-width coincides with Θm(K; X, X) for X = L2ρ(U; R) and V = R.Source: §5.1 · pp. 11–12

5.2 Proof of Theorem 4.4

  • Legendre polynomial expansions yield lower bounds by reducing the continuous problem to a discrete one and applying width results for weighted ℓp balls.For known anisotropy, order-one polynomials provide the holomorphy step in this reduction.Source: §5.2 · pp. 12, 15

5.3 Proof of Theorem 4.5

  • Theorem 4.5’s proof first proceeds as in Theorem 4.4 and uses Lemma 5.4’s bound to prove part (a) of the unknown-anisotropy result for the m-width θm(p).Source: §5.3 · pp. 16–17

5.4 Proof of Theorem 4.6

  • For Theorem 4.6, the proof selects Legendre expansion indices using b and p, then defines sampling and reconstruction from those coefficients.Its part (b) constant c_{p,q} is unknown and must blow up as q approaches p; the q = p case would require a different proof technique.Source: §5.4 · pp. 18–19

5.5 Proof of Theorem 4.7

  • For unknown b, Theorem 4.7’s proof uses compressed sensing because coefficient-index sets chosen from b can range across the infinite index set.Restricting b to the monotone ℓp space allows anchored sets to retain the approximation rate while their union fits in a finite search space.Source: §5.5 · pp. 19–20

5.5.1 Setup and the vector recovery problem

  • The proof defines sampling and reconstruction maps, then reduces recovery to Hilbert-valued basis pursuit for approximately sparse coefficient vectors.The reconstruction map selects a minimum-ℓ2-norm minimizer to ensure uniqueness and returns zero when the input is outside the matrix range.Source: §5.5.1 · pp. 20–21

5.5.2 Error bounds in probability

  • Gaussian sampling yields a robust null space property with probability at least 1 − ǫ under the stated sample condition, enabling stable recovery by basis pursuit.The proof applies this property to obtain reconstruction error bounds; the constants in the probability bounds depend on b and p.Source: §5.5.1 · pp. 21–22, §5.5.2 · p. 22
  • The proof of Theorem 4.7 first establishes error bounds in probability and then uses them to obtain an error bound in expectation.The probability analysis combines robust null space recovery with coefficient approximation bounds for functions in H(b).Source: §5.5.2 · pp. 22, 23, 25

6 Conclusions and open problems

The paper establishes lower and upper m-width bounds for Banach-valued, (b, 1)-holomorphic functions: optimal recovery is attainable in the monotone case, while finite-data approximation is impossible in the unknown-anisotropy space without prior variable information.

6 Conclusions and open problems

  • Optimal recovery is attainable when b belongs to the monotone class, but finite-data approximation is impossible in H(p) when b is unknown and only known to belong to ℓp(N).When the bounds decay, they do so at a rate close to m^(1/2−1/p); the paper uses reconstruction maps involving convex optimization minimizers, not algorithms achieving these rates.Source: §6 · p. 26
  • Uniform upper bounds for pointwise i.i.d. samples remain open; the paper’s upper bounds do not use pointwise samples.The cited i.i.d.-sample guarantees are nonuniform because their decay rates hold for a fixed function, whereas this paper’s results hold for any function in the class.Source: §6 · p. 26
  • The upper bounds for θm(p, M) and θm(p, M) are non-sharp against the lower bounds by an algebraic factor, though the authors conjecture this gap can be closed.They suggest uniformly bounding constants C(b, p) and CA(b, p) over the specified monotone class as one possible route.Source: §6 · p. 26
  • For known anisotropy, a lower bound for θm(p) decays at m^(1/2−1/p), but the paper gives no analogous upper bound.The authors leave open whether θm(p) decays at that rate or remains nondecreasing as in the unknown-anisotropy case.Source: §6 · p. 26
  • Extending Theorem 4.7 to Banach-valued functions remains open; the indicated extension would yield a worse exponent than 1/2−1/p (or 1/2−1/q).The authors identify matching Hilbert- and Banach-valued rates as a gap to close.Source: §6 · p. 26
  • Bounds in the L∞(U; V)-norm remain open because the lower-bound proof relies on the L2ρ(U; V)-norm.The authors conjecture corresponding theorems with exponent 1−1/p (or 1−1/q) instead of 1/2−1/p (or 1/2−1/q).Source: §6 · p. 26

A Summability and best s-term polynomial approximation rates

The appendix collects four coefficient-summability lemmas used to derive upper bounds on the m-widths.

A Summability and best s-term polynomial approximation rates

  • Four lemmas on Legendre coefficient summability for (b, 1)-holomorphic functions support the appendix’s upper bounds on m-widths.The functions are those introduced in §3.1, and the bounds concern m-widths (4.3)–(4.5).Source: A Summability and best s-term… · p. 27

A.1 Legendre polynomial expansions

This appendix section sets up infinite multi-indices and the tensorized Legendre expansion, then defines its finite truncation.

A.1 Legendre polynomial expansions

  • The section introduces infinite multi-indices and identifies the finite-support indices through their support.The support records the coordinates with nonzero entries.Source: §A.1 · p. 27
  • The uniform probability measure on U = [−1, 1]^N and a tensorized orthonormal Legendre basis define the expansion setting for functions in L2ρ(U; V).Each Ψν is a univariate orthonormal Legendre polynomial of degree ν.Source: §A.1 · p. 27
  • For a finite index set S, the section defines the truncated series of f using the indices in S.The set S has size N.Source: §A.1 · p. 27

A.2 ℓp-summability and best s-term rates

This section develops coefficient summability and best s-term approximation results for Legendre expansions, including an algebraic rate for anchored sets.

A.2 ℓp-summability and best s-term rates

  • For each s, the section identifies a set of at most s indices depending only on b and p, and notes that the coefficient-bounding sequence makes the index set independent of f.The result is stated for Legendre coefficients of (b, 1)-holomorphic functions.Source: §A.2 · p. 30
  • An anchored set is lower and, when it contains ej, also contains e1 through ej; the section defines the anchored majorant and best s-term error using anchored support.The anchored majorant is used to define the ℓp A space.Source: §A.3 · pp. 30–31
  • Legendre coefficients of a (b, 1)-holomorphic function satisfy an ℓp A summability result, with CA(b, p) depending only on b and p.The passage introduces this as analogous to the coefficient-summability result in Lemma A.1.Source: §A.3 · p. 30
  • For b ∈ ℓp M(N), an anchored set S of size at most s gives σs,A(c)q;V ≤ ∥c − cS∥q;V ≤ CA(b, p) · s^(1/q−1/p) for every f ∈ H(b).The result states an algebraic best s-term rate for anchored sets.Source: §A.3 · p. 32

B Widths of weighted ℓp-norm balls in RN

Appendix B develops width results for weighted ℓp-balls in finite-dimensional spaces. It presents a Gelfand-width lower bound, a Gelfand/Kolmogorov-width equality, Stesin duality, and a comparison of unit balls using Kolmogorov widths.

B Widths of weighted ℓp-norm balls in RN

Loading 2305.18642v2…