PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Neural Network Approximation Theory

Dennis Elbrächter, Dmytro Perekrestenko, Philipp Grohs, Helmut Bölcskei

arXiv:1901.02220v4cs.LGcs.ITstat.ML

TL;DR

The paper asks what fundamental approximation limits deep neural networks achieve without constraints on learning algorithms or training-data quantity. It develops a Kolmogorov-Donoho framework linking function-class complexity to network connectivity and memory, and establishes optimal approximation across diverse classes, exponential rates for several functions, and a connectivity advantage for depth.

  • Problem

    The paper addresses how accurately neural networks can approximate function classes and how the required network complexity depends on the class complexity and target accuracy.

  • Method

    The paper develops a Kolmogorov-Donoho rate-distortion framework relating function-description complexity to network connectivity and memory for topology and quantized weights.

  • Results

    Deep networks are optimal approximants for Besov and modulation-space unit balls, achieve exponential accuracy for diverse functions, and use strictly smaller connectivity than finite-depth wide networks for sufficiently smooth functions.

  • Takeaways & Limitations

    The theory establishes broad universality for deep networks and a provable approximation benefit of depth within the studied function classes and settings.

Abstract

from arXiv · show

This paper develops fundamental limits of deep neural network learning by characterizing what is possible if no constraints are imposed on the learning algorithm and on the amount of training data. Concretely, we consider Kolmogorov-optimal approximation through deep neural networks with the guiding theme being a relation between the complexity of the function (class) to be approximated and the complexity of the approximating network in terms of connectivity and memory requirements for storing the network topology and the associated quantized weights. The theory we develop establishes that deep networks are Kolmogorov-optimal approximants for markedly different function classes, such as unit balls in Besov spaces and modulation spaces. In addition, deep networks provide exponential approximation accuracy - i.e., the approximation error decays exponentially in the number of nonzero weights in the network - of the multiplication operation, polynomials, sinusoidal functions, and certain smooth functions. Moreover, this holds true even for one-dimensional oscillatory textures and the Weierstrass function - a fractal function, neither of which has previously known methods achieving exponential approximation accuracy. We also show that in the approximation of sufficiently smooth functions finite-width deep networks require strictly smaller connectivity than finite-depth wide networks.

I. INTRODUCTION

The paper introduces a self-contained Kolmogorov-Donoho theory of approximation through deep neural networks, relating function-class complexity to network connectivity and memory. It establishes broad optimality, exponential approximation rates, and a provable advantage of depth.

  • Framework: Kolmogorov-Donoho theory relates the complexity of a function class to neural-network connectivity and memory for topology and quantized weights.Function-class complexity is measured through the bits needed to describe class elements to prescribed accuracy.
  • Purpose: The paper develops a comprehensive, self-contained introduction to Kolmogorov-Donoho rate-distortion optimal approximation through deep neural networks.It aims to provide mathematical tools sufficient to support further research.
  • Scope: The theory extends to ReLU networks and networks whose depth scales with approximation error.Some parts also carry over to strongly sigmoidal activation functions, but those extensions are not developed in the paper.
  • Universality: Deep networks are Kolmogorov-Donoho optimal approximants for unit balls in Besov spaces and modulation spaces.The paper attributes this universality to invariance under time-shifts, scalings, and frequency-shifts.
  • Exponential approximation: Approximation error decays exponentially in the number of nonzero network weights for multiplication, polynomials, sinusoidal functions, smooth functions, oscillatory textures, and the Weierstrass function.The latter two examples are presented as cases without previously known methods achieving exponential accuracy.
  • Depth: For sufficiently smooth functions, finite-width deep networks require strictly smaller connectivity than finite-depth wide networks.The paper presents this result as a formal case for depth in neural-network approximation.

III. APPROXIMATION OF MULTIPLICATION, POLYNOMIALS, SMOOTH FUNCTIONS, AND SINUSOIDALS

This section develops deep ReLU network constructions for multiplication, polynomials, smooth functions, and sinusoidal functions, using sawtooth-based approximation and depth to achieve high approximation efficiency.

  • Polynomials and smooth functions: The same algebraic building blocks are extended from multiplication to polynomials and then to general smooth and sinusoidal functions.The section explicitly develops an approximation algebra beginning with squaring, continuing through multiplication and polynomials, and ending with sinusoidal functions.
  • Squaring function: The squaring network uses constant width and bounded weights while its depth scales logarithmically with ε−1.The stated construction has W(Φε) = 3, B(Φε) = 1, and L(Φε) ≤ C log(ε−1).
  • Squaring function: The construction begins with a deep ReLU approximation of the squaring function based on recursively refined linear interpolation.The residual interpolation error repeats across subintervals, while the number of linear regions grows exponentially with depth.
  • Multiplication: Multiplication is obtained from the squaring approximation through the polarization identity and ReLU scaling on [−D,D].The resulting networks have depth bounded by C(log(⌈D⌉) + log(ε−1)), width at most 5, and weights bounded by 1.
  • Smooth functions: Every continuous function on a closed interval can be approximated arbitrarily accurately by a deep ReLU network of width no more than 9.For the smooth-function class S[−1,1], the construction achieves L(Ψf,ε) ≤ C(log(ε−1))^2, W(Ψf,ε) ≤ 9, and B(Ψf,ε) ≤ 1.
  • Approximation efficiency: These constructions yield exponential approximation accuracy in connectivity because connectivity grows no faster than polylogarithmically in ε−1.The paper states that the approximation error decays at least exponentially in connectivity, equivalently in the number of parameters used.
  • Sinusoidal functions: Cosine and sine approximations retain bounded width and weights while depth depends polylogarithmically on ε−1 and logarithmically on frequency and domain scale.For cosine, L(Ψa,D,ε) ≤ C((log(ε−1))^2 + log(⌈aD⌉)), W ≤ 9, and B ≤ 1; the sine result includes the corresponding shift parameter.

IV. APPROXIMATION OF FUNCTION CLASSES AND METRIC ENTROPY

This section reviews approximation-theoretic foundations and motivates a framework connecting function-class complexity with deep-network approximation complexity. It situates the framework within prior results on shallow and deep networks, dictionaries, and applications.

  • Related approximation results: Exponential approximation accuracy has been reported for polynomials, smooth functions, and sinusoidal functions when size is measured by total neurons.The cited results concern approximation error decaying exponentially with network size under that measurement.
  • Related approximation results: Deep networks have been studied for approximating general, continuous, smooth, polynomial, sinusoidal, and PDE-related functions.Prior work includes approximation results for multiple-hidden-layer networks, convolutional networks, and parametric PDE solution families.
  • Depth and expressivity: Some functions can be represented by small deep networks but require exponentially larger shallow or shallow convolutional networks.The reviewed examples establish a depth-related expressivity advantage for particular functions.
  • Framework motivation: The paper develops a framework for characterizing fundamental limits of deep neural-network approximation of entire function classes.The framework is intended to connect approximation limits with the complexity of the function class and the approximating network.
  • Framework motivation: The review introduces deterministic lossy data compression as a foundation for analyzing approximation and memory requirements.The presentation follows prior treatments of this theoretical foundation.

A. Kolmogorov-Donoho Rate Distortion Theory

Kolmogorov-Donoho rate-distortion theory measures the shortest binary description that uniformly approximates a compact function class to error ε. Its optimal exponent quantifies the class’s description complexity and associated memory growth.

  • Norm choice: Approximation error is measured in L2(Ω)-norm to parallel the Kolmogorov-Donoho framework, while L∞(Ω)-based results are stronger.For finite-measure domains, the norms satisfy ∥f∥L2(Ω) ≤ |Ω|^1/2∥f∥L∞(Ω).
  • Rate-distortion formulation: The central quantity is the minimal code length ℓ for an encoder-decoder pair achieving uniform error ε over a function class C.The encoder maps functions to binary strings and the decoder reconstructs approximations.
  • Rate-distortion formulation: The optimal exponent γ∗(C) determines the asymptotic growth of the minimal code length as ε tends to zero.It can equivalently describe the decay of the minimal achievable error for a given code length.
  • Interpretation: Larger γ∗(C) corresponds to slower code-length growth and smaller memory requirements for uniformly accurate reconstruction.The interpretation concerns storing functions from C with uniformly bounded error.
  • Interpretation: The optimal exponent is closely related to Kolmogorov-Tikhomirov epsilon entropy, also called metric entropy.The section uses this connection to relate coding complexity to covering behavior.

B. Metric entropy

Metric entropy quantifies the number of ε-sized metric balls needed to cover a set, equivalently measuring its description complexity in bits. Covering and packing arguments establish its scaling for finite-dimensional examples and function classes.

  • Definitions: Metric entropy is log N(ε; C, ρ), where N(ε; C, ρ) is the smallest number of ε-balls covering C.With logarithms to base 2, metric entropy is measured in bits and equals the minimum representation length for error at most ε.
  • Finite-dimensional examples: For the d-dimensional unit cube, log N(ε; C, ρ) ≍ d log(ε−1).This scaling is obtained by extending the interval-covering construction to d dimensions.
  • Coverings and packings: An ε-packing contains points separated by more than ε, and packing and covering numbers provide essentially the same measure of set size.The section relates them through inequalities involving M(2ε; C, ρ), N(ε; C, ρ), and M(ε; C, ρ).
  • Finite-dimensional examples: For unit balls in d-dimensional normed spaces, N(ε; B, ∥·∥) ≍ ε−d and log N(ε; B, ∥·∥) ≍ d log(ε−1).A volume-ratio argument establishes the covering-number bounds.
  • Function-class example: For the one-parameter class P, N(ε; P, ∥·∥L∞([0,1])) scales as ε−1 and its metric entropy scales as log(ε−1).The upper bound uses parameter points spaced by approximately ε.

V. APPROXIMATION WITH DICTIONARIES

This section develops nonlinear approximation with dictionaries and introduces effective best M-term rates to avoid the unrealistic advantages of unrestricted dense dictionaries. It connects these rates to function-class description complexity and Kolmogorov-Donoho optimality.

  • Linear and nonlinear approximation: Best M-term approximation selects up to M dictionary elements freely, unlike linear approximation, which is restricted to a fixed M-dimensional subspace.Nonlinear selection can improve approximation when relevant components are not among the first ordered dictionary elements.
  • Effective approximation: Unrestricted dense dictionaries can give γ∗(C, D) = ∞, because each target function may be approximated arbitrarily well by one dictionary element.Identifying that element is generally infeasible and requires infinitely many bits to describe its index.
  • Effective approximation: Effective best M-term approximation restricts the search to the first π(M) dictionary elements, with π polynomial.This makes dictionary-element identification compatible with polynomial-depth search.
  • Kolmogorov-Donoho optimality: For compact function classes, the effective best M-term approximation rate in any dictionary is upper-bounded by γ∗(C), the class’s description-complexity exponent.This gives γ∗(C) an operational meaning as a limit on effective dictionary approximation.
  • Kolmogorov-Donoho optimality: Kolmogorov-Donoho optimality means that a dictionary attains the function class’s optimal effective approximation rate.The theory is developed as a basis for the subsequent theory of best M-weight approximation with neural networks.
  • Encoding argument: Encoding an effective M-term approximation requires a bitstring proportional to M log(M), linking approximation rate ε = M−γ to code length.The construction encodes both participating dictionary indices and their coefficients.

VI. APPROXIMATION WITH DEEP NEURAL NETWORKS

This section develops best M-weight approximation for deep networks, measuring approximation rates by connectivity while controlling depth, weight growth, and quantization. It establishes fundamental limits through coding arguments and defines effective rates under polylogarithmic depth and polynomially bounded weights.

  • Core framework: Best M-weight approximation replaces dictionary sparsity with parsimony in the number of nonzero network weights.The infimum ranges over all network topologies and weight choices with fixed input dimension and at most M nonzero weights.
  • Core framework: The best M-weight approximation rate benchmarks every algorithm mapping a function and target error to a neural network.Its optimal exponent imposes a fundamental lower bound on connectivity growth and achievable error decay.
  • Effective rates: Network tree structure automatically supplies the polynomial depth-search constraint needed in effective best M-term approximation.Network architectures and nonzero-weight locations can be encoded with O(M(Φ) log(M(Φ))) bits.
  • Effective rates: Effective approximation restricts networks to polylogarithmic depth and polynomial weight magnitude relative to connectivity.These conditions support rate-distortion-optimal quantization of network weights.
  • Fundamental limits: Theorem VI.4 establishes that the optimal exponent γ∗(C) remains a fundamental bound for effective best M-weight approximation by deep networks.The result concerns compact function classes and networks with controlled depth, weight growth, and quantized weights.
  • Fundamental limits: A uniform error decay faster than O(M^-γ∗(C)) is impossible when γ∗(C) is the optimal approximation exponent.Equivalently, achieving error ε requires connectivity that cannot grow more slowly than O(ε^-1/γ∗(C)).

VII. THE TRANSFERENCE PRINCIPLE

This section develops a transfer principle from dictionary approximation to deep neural networks. If a dictionary is effectively representable and optimally approximates a function class, the class inherits optimal neural-network approximation under controlled connectivity and weights.

  • Consequences: For optimal dictionary–class pairs, the effective neural-network approximation exponent equals the dictionary exponent: γ∗,eff(C,D) = γ∗(C).Examples include unit balls in Besov spaces with wavelet bases and weighted modulation spaces with Wilson bases.
  • Motivation: The transfer framework asks which function classes are approximated in Kolmogorov-Donoho-optimal fashion by neural networks.It converts approximation results for dictionaries into neural-network results.
  • Effective representability: Effective representability requires each dictionary element to have a neural-network approximation with polylogarithmic connectivity growth in error and element index.The associated weight magnitude is required to grow polynomially in inverse error and index.
  • Transfer principle: The transfer theorem states that optimal dictionary approximation combined with effective neural-network representability implies optimal neural-network representation of the function class.The resulting network has connectivity only polylogarithmically larger than the number of dictionary terms.
  • Transfer principle: Theorem VII.2 constructs networks with L(Ψ(ε,f)) ≤ π(log(ε^-1)) and B(Ψ(ε,f)) ≤ π(ε^-1) while achieving L2 error at most ε.The weights are quantized at resolution controlled by log(ε^-1).
  • Consequences: The framework applies to a wide variety of dictionaries, yielding universal Kolmogorov-Donoho optimality for the listed function classes.The examples include affine dictionaries such as wavelets and curvelets and Weyl-Heisenberg dictionaries such as Fourier and Wilson bases.

VIII. AFFINE DICTIONARIES ARE EFFECTIVELY REPRESENTABLE BY NEURAL NETWORKS

This section shows how affine dictionaries can be effectively represented by neural networks. It develops the construction from a Haar-wavelet example and transfers suitable dictionary approximation properties to neural networks.

  • Section aim: The section aims to establish effective neural-network representability for affine dictionaries, including wavelets, ridgelets, curvelets, shearlets, and α-molecules.These dictionaries are treated as instances of a broader affine-dictionary framework.
  • Haar-wavelet construction: A Haar wavelet is approximated by a continuous piecewise linear ReLU network through a smoothed transition construction.The transition regions around 0, 1/2, and 1 shrink sufficiently fast to achieve error at most ε.
  • Haar-wavelet construction: Haar wavelet dictionary elements are ordered from coarse to fine scales before assigning network approximants.This ordering links each dictionary index to its scale and location.
  • Effective representability: The construction verifies the conditions for effective neural-network representability of the Haar dictionary.The network parameters are encoded using the dictionary element’s scale and location indices.

A. Affine Dictionaries with Canonical Ordering

This section formalizes affine dictionaries with canonical ordering and analyzes their structural requirements. The Haar wavelet system satisfies these conditions, with approximating-network weights growing linearly in dictionary index.

  • Affine dictionary definition: An affine dictionary is built from compactly supported generator functions, scale-dependent full-rank dilation matrices, translations, and bounded-domain restrictions.The framework permits multiple generators and generator-specific scale sets.
  • Canonical ordering: Canonical ordering arranges dictionary elements by scale, while allowing arbitrary ordering within each scale and requiring polynomial index-scale control.This ordering provides a controlled relationship between dictionary indices and dilation scales.
  • Haar example: The Haar wavelet dictionary is recovered as a nondegenerate affine dictionary on [0,1] with one generator and dyadic dilations.At scale j, its sub-dictionary contains 2^j−1 elements.
  • Haar example: Weights of networks approximating individual Haar dictionary elements grow linearly with the dictionary index.This follows from weights encoding the dilation factor and the inequality 2^n(i) ≤ i under the chosen ordering.
  • Canonical ordering: The canonical-ordering growth condition is weak: the authors report no known affine dictionaries that violate it.Dilation matrices need not be ordered by ascending size, although canonical ordering still guarantees limited ordering.

B. Invariance to Affine Transformations

Affine transformations preserve neural-network approximability: translations and dilations can be absorbed into the first layer, with quantitative control of connectivity, memory, and approximation domain. Consequently, neural networks inherit optimal representability from suitable affine dictionaries.

  • Affine invariance: Translations and dilations can be absorbed into a network’s first layer, preserving the generator’s approximability while changing weights, connectivity, and approximation domain quantitatively.The transformed domain is controlled through F = dE∥A∥∞ + ∥e∥∞.
  • Affine invariance: Proposition VIII.2 transfers approximation guarantees from f to affine transforms of f using networks whose connectivity grows polynomially with log(η−1) and log(⌈F⌉).The bound applies for full-rank A, translations e, and approximation scale E.
  • Effective representability: Generators that are well approximated by neural networks make canonically ordered affine dictionaries effectively representable by neural networks.The required generator approximants have polynomial memory and connectivity bounds in the approximation accuracy.
  • Scope: The stated theorem assumes bounded domains and compactly supported generators, while extensions to unbounded domains and sufficiently fast-decaying generators require additional technical steps.The extension details are deferred to later theorems.
  • Optimality transfer: All compact function classes optimally representable by such affine dictionaries are likewise optimally representable by neural networks.This transfers Kolmogorov-Donoho optimality from the dictionary to the neural-network approximants.

D. Spline wavelets

Spline wavelet dictionaries are shown to transfer their optimal approximation properties to deep neural networks. The key ingredient is logarithmic-size, one-bit-memory approximation of cardinal B-splines, which supports optimal representability of all compact classes optimized by the dictionary.

  • B-spline approximation: B-splines, being piecewise polynomial, can be approximated by deep neural networks with connectivity proportional to log(ε−1) and memory bound B(Φε) ≤1.The construction uses fixed-order spline structure and achieves global L∞(R) error at most ε.
  • Error norms: The B-spline approximation result also extends to L2(R)-error, with a different constant in the bound.Compact support converts the global L∞ estimate into an L2 estimate.
  • Spline wavelet structure: The resulting spline wavelet system forms a countable complete orthonormal wavelet basis in L2(R).It combines scaled and shifted spline wavelets with translated cardinal B-splines.
  • Dictionary construction: The spline wavelet system is a nondegenerate canonically ordered affine dictionary generated by a spline wavelet and a cardinal B-spline.The construction verifies the ordering and nondegeneracy conditions required for the transfer theorem.
  • Optimality transfer: Every compact function class optimally representable by the spline wavelet dictionary is optimally representable by neural networks.This follows by combining effective generator approximation with the affine-dictionary optimality transfer.

IX. WEYL-HEISENBERG DICTIONARIES

The paper extends neural-network approximation guarantees from affine dictionaries to Weyl-Heisenberg, or Gabor, dictionaries. Modulation and translation operations preserve effective representability, yielding optimal neural-network approximation for function classes optimized by suitable Gabor dictionaries.

  • Gabor dictionaries: Gabor dictionaries consist of time-frequency shifts of a generator, combining translations and modulations indexed through an explicit ordering.Their elements are written as ϕi = Mξ(i)Tx(i)g.
  • Invariance: Neural networks inherit approximation properties under frequency shifts, complementing the previously established invariance to affine scaling and translation.The modulation result is interpreted as a Weyl-Heisenberg analogue of affine invariance.
  • Effective representability: Generator approximants can be modulated and translated while retaining polynomial connectivity and memory bounds, establishing effective representability of Gabor dictionaries.For bounded domains, the construction combines affine transformations, modulation, and multiplication networks.
  • Scope: The treatment is directly real-valued; complex-valued generators require a complex multiplication result or a two-dimensional real-valued output representation.The paper omits the complex-valued construction details.
  • Global domains: For all of R^d with compactly supported generators, the construction additionally controls network support outside a translation-dependent region.This addresses the lack of global control that remains when approximation is established only on bounded sets.
  • Optimality transfer: All function classes optimally approximated by suitable Gabor dictionaries are optimally representable by neural networks.The result includes the modulation-space setting, where Wilson bases provide optimal nonlinear approximation of unit balls.

X. IMPROVING POLYNOMIAL APPROXIMATION RATES TO EXPONENTIAL RATES

Finite-width deep networks improve polynomial approximation rates to exponential rates for oscillatory textures and the Weierstrass function. The results provide exponential-accuracy constructions with bounded width and quantized weights, including for a fractal function and one-dimensional oscillatory textures.

  • Oscillatory textures: Finite-width deep networks improve prior low-order polynomial rates for oscillatory textures to exponential approximation rates.The prior results cited are based on wave-atom dictionaries and concern the two-dimensional case, whereas this section treats one-dimensional textures.
  • Oscillatory textures: Proposition X.2 approximates every f ∈FD,a on [−D,D] with depth scaling polylogarithmically in ε−1, width W(Γf,ε) ≤32, and memory B(Γf,ε) ≤1.The depth bound also depends logarithmically on ⌈a⌉, ⌈D⌉, and ⌈D−1⌉.
  • Oscillatory textures: The oscillatory-texture construction factors f into a rapidly oscillating cosine term and a warping function, then approximates the components with neural networks.The network combines approximations of gf and hf with multiplication and composition modules.
  • Weierstrass function: Deep ReLU networks achieve exponential accuracy for the Weierstrass function, which is continuous everywhere but differentiable nowhere.The paper contrasts this with the absence of previously known methods achieving exponential accuracy for the function.

XI. IMPOSSIBILITY RESULTS FOR FINITE-DEPTH NETWORKS

This section formalizes limitations of finite-depth networks and contrasts them with finite-width deep networks. For periodic and sufficiently smooth functions, finite-depth networks cannot maintain polylogarithmic connectivity while achieving arbitrarily small error, whereas finite-width deep networks can for several important functions.

  • Proof mechanism: Every ReLU network realizes a piecewise linear function, so finite-depth approximation limits follow from bounds on the number of linear pieces.The proof bounds the network’s sawtooth complexity using depth and weight count, then compares it with the complexity required by the target function.
  • Periodic functions: Finite-depth networks with width and connectivity scaling polylogarithmically in a periodic function’s highest frequency cannot achieve arbitrarily small approximation error.The result applies to nonconstant periodic functions under bounded depth and polynomial width growth in the logarithm of frequency.
  • Periodic functions: For f(x)=cos(x), finite-depth networks require faster-than-polylogarithmic connectivity growth to approximate x 7→cos(ax) with arbitrarily small error.Finite-width networks can achieve the same approximation with polylogarithmic connectivity growth.
  • Smooth functions: Any at-least-three-times continuously differentiable function with nonvanishing second derivative cannot be approximated by finite-depth networks with connectivity polylogarithmic in inverse error.The lower bound on required linear pieces grows polynomially in ε^-1, exceeding the finite-depth network’s polylogarithmic sawtooth growth.
  • Depth advantage: Finite-width deep networks can achieve polylogarithmic connectivity growth for several smooth functions, including polynomials and sinusoidal functions.This establishes a depth advantage over finite-depth wide networks for a broad class of approximation problems.

APPENDIX A

The appendix develops constructions that realize affine maps, normalize weight magnitudes, sum networks without width depending on the number of summands, and patch local approximations. These tools support bounded-weight, finite-width approximation networks on general intervals.

  • Network constructions: Affine transformations Ax+b can be realized with depth at most ⌊log(|a|)⌋+5, width at most max{d, 3d′}, and weight bound B(ΦA,b)≤1.The matrix A and vector b are assumed to have entries in [−a,a].
  • Network constructions: Any network can be replaced by an equivalent network with weights bounded by 1, increasing depth by a logarithmic factor while keeping width controlled.The construction preserves the realized function and uses positive homogeneity of ReLU.
  • Network aggregation: A sum of N networks with shared input can be implemented with width independent of N, bounded by 2d+2d′+max{2d,max_i W(Φi)}.The resulting network preserves the constituent networks’ depth and has weight magnitude max{1,max_i B(Φi)}.
  • Patching local approximations: Local approximations can be patched using multiplication networks and hat functions whose supports overlap so that at most two local terms are active at any point.This yields a global approximation while controlling the resulting network’s depth, width, and weight bound.
  • Interval approximation: For g∈S[a,b] on arbitrary finite intervals, there are approximating networks with width at most 16 and weight bound at most 1.Their depth scales as C max{2,b−a}((log(ε^-1))^2+log(⌈max{|a|,|b|}⌉)+log(⌈1/(b−a)⌉)).

APPENDIX B

The appendix verifies tail compactness for unit balls in Besov and weighted modulation spaces using wavelet or Wilson-basis coefficient representations. The resulting coefficient-tail bounds provide the decay conditions needed for approximation analysis.

  • Besov spaces: Besov-space unit balls are analyzed through coefficients in an orthonormal wavelet basis grouped by resolution levels.The level sets contain 2^n coefficients, enabling tail estimates via Hölder’s inequality and ℓp-to-ℓ2 comparisons.
  • Besov spaces: For Besov unit balls, the coefficient-tail estimate establishes tail compactness with C=1 and β=m.This follows from the wavelet coefficient bounds and finite level-set cardinalities.
  • Modulation spaces: Weighted modulation spaces are represented using Wilson-basis coefficients that are norm-equivalent to the modulation-space norm.The coefficient characterization uses constants D≥1 satisfying two-sided norm bounds.
  • Modulation spaces: The modulation-space construction uses a Wilson dictionary derived from a tight Gabor frame and a Schwartz window function.The resulting Wilson dictionary is an orthonormal basis for L2(R).
  • Modulation spaces: For modulation-space unit balls with p,q≤2, the ordered Wilson-basis coefficients satisfy tail compactness with C=(3/2)^−sD and β=s.The result uses orthonormality and the inequality ∥·∥ℓ2≤∥·∥ℓp for p≤2.
Loading 1901.02220v4…