Paper deep dive

Spectral Convergence of Random Feature Method in Multiple Dimensions

Pingbing Ming, Hao Yu

Year: 2026Venue: arXiv preprintArea: math.NAType: PreprintEmbeddings: 223

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%

Last extracted: 9/4/2026, 3:06:05 AM

Summary

This paper establishes the spectral convergence of the Random Feature Method (RFM) for multidimensional targets in various regularity classes (Sobolev, Gevrey, ultra-analytic, bandlimited). It proves that a single sampled random feature space can approximate any target in a source ball with spectral accuracy across all admissible error norms simultaneously. The study also derives error estimates for strong- and weak-form RFM discretizations of elliptic boundary value problems and analyzes the singular value decay and ill-conditioning of random feature matrices, linking high accuracy to severe ill-conditioning.

Entities (9)

Random Feature Method · method · 98%Random Feature Matrix · data-structure · 95%Ill-conditioning · property · 93%Spectral Convergence · property · 92%Gevrey Class · mathematical-space · 90%Sobolev Space · mathematical-space · 90%Elliptic Boundary Value Problem · problem-type · 88%Fourier Features · feature-type · 85%Tanh Features · feature-type · 85%

Relation Signals (6)

Random Feature Method → achieves → Spectral Convergence

confidence 95% · We first prove spectral convergence of the random feature method (RFM) for multidimensional targets...

Random Feature Matrix → exhibits → Ill-conditioning

confidence 92% · The analysis identifies a common mechanism: the same spectral approximation that yields high accuracy also drives severe ill-conditioning.

Random Feature Method → appliesto → Elliptic Boundary Value Problem

confidence 90% · ...converting the preceding approximation bounds into convergence estimates for multidimensional second-order elliptic boundary value and eigenvalue problems.

Fourier Features → causes → Super-exponential Singular-value Decay

confidence 88% · ...we prove super-exponential singular-value decay with Fourier features...

Tanh Features → causes → Exponential Singular-value Decay

confidence 88% · ...and exponential decay with tanh features...

Random Feature Method → handles → Sobolev Space

confidence 85% · ...spectral convergence of the random feature method (RFM) for multidimensional targets in Sobolev... classes.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:We first prove spectral convergence of the random feature method (RFM) for multidimensional targets in Sobolev, Gevrey, ultra-analytic, and bandlimited classes. The analysis establishes general high-probability approximation estimates in the interpolation scale generated by a kernel integral operator. On a single event determined only by the sampled features, one random space approximates every target in a prescribed source ball; moreover, for each target, a single coefficient vector defines an approximant that attains spectral accuracy simultaneously in all admissible error norms. For both regularity-adapted frequency distributions and uniform distributions on growing frequency windows, the resulting rates range from super-exponential to algebraic, depending on the regularity of the target. Second, we establish abstract error estimates for strong- and weak-form RFM discretizations, thereby converting the preceding approximation bounds into convergence estimates for multidimensional second-order elliptic boundary value and eigenvalue problems. Finally, for random feature matrices (RFMtxs), we prove super-exponential singular-value decay with Fourier features and exponential decay with $\tanh$ features, together with corresponding condition-number lower bounds. The analysis identifies a common mechanism: the same spectral approximation that yields high accuracy also drives severe ill-conditioning.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

219,837 characters extracted from source content.

Expand or collapse full text

Spectral Convergence of Random Feature Method in Multiple Dimensions Pingbing Ming and Hao Yu Address: SKLMS, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China Address: School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China Email address: mpb@lsec.c.ac.cn Email address: yuhao@amss.ac.cn Abstract. We first prove spectral convergence of the random feature method (RFM) for multidimensional targets in Sobolev, Gevrey, ultra-analytic, and bandlimited classes. The analysis establishes general high-probability approximation estimates in the interpolation scale generated by a kernel integral operator. On a single event determined only by the sampled features, one random space approximates every target in a prescribed source ball; moreover, for each target, a single coefficient vector defines an approximant that attains spectral accuracy simultaneously in all admissible error norms. For both regularity-adapted frequency distributions and uniform distributions on growing frequency windows, the resulting rates range from super-exponential to algebraic, depending on the regularity of the target. Second, we establish abstract error estimates for strong- and weak-form RFM discretizations, thereby converting the preceding approximation bounds into convergence estimates for multidimensional second-order elliptic boundary value and eigenvalue problems. Finally, for random feature matrices (RFMtxs), we prove super-exponential singular-value decay with Fourier features and exponential decay with tanh features, together with corresponding condition-number lower bounds. The analysis identifies a common mechanism: the same spectral approximation that yields high accuracy also drives severe ill-conditioning. Key words and phrases: Random feature method, random Fourier features, spectral convergence, simultaneous approximation, leverage-score sampling, kernel interpolation spaces, ill-conditioning 1. Introduction Recently, learning-based methods have emerged as an active paradigm for solving partial differential equations (PDEs). Inherently meshfree, these methods enjoy the flexibility to handle complex geometries and high-dimensional problems, facilitating the integration of experimental data. However, current learning-based PDE solvers still face significant challenges, such as high computational costs and a lack of strategies to consistently improve accuracy. A parallel line of work analyzes learning-based and data-driven discretizations through the classical numerical-analysis concepts of approximation, stability, and conditioning. Random features (RFs) provide a particularly transparent setting for this program. Their hidden parameters are sampled from a prescribed distribution and only the output coefficients are optimized, so training reduces to a linear least-squares problem. Introduced as scalable approximations of kernel machines [61], RFs now form a useful interface between kernel approximation, randomized numerical linear algebra, and shallow neural networks. These developments lead to a unified question: once the trial space and sampling mechanism are specified, what are the approximation rate, the stability of the residual map, and the conditioning of the resulting algebraic system? Against this background, recent efforts have sought to bridge traditional numerical solvers with machine learning through extreme learning machines, the random feature method (RFM), and related randomized neural networks. The core idea is to approximate the solution by a neural network with prescribed inner-layer weights, thereby reducing training to a linear least-squares problem for the outer-layer weights. Representative examples include RFM discretizations for stationary and time-dependent problems [8, 9] and dimension-robust solvers for Kolmogorov equations [28]. A hallmark of these approaches is the spectral or near-spectral accuracy observed even on complicated geometries [8, 18, 72]. A critical issue, however, is the severe ill-conditioning of the random feature matrix (RFMtx) in high-accuracy computations [10]. Moreover, a multidimensional convergence theory must answer three questions simultaneously: how the sampling law should reflect the regularity of the target, whether one sampled space works uniformly over an entire target class, and whether the same reconstruction controls the several derivative norms required by PDE stability estimates. Standard fixed-target or fixed-norm bounds do not provide this combination, nor do they explain spectral approximation and rapid singular-value decay within a common framework. Our analysis is built on concentration of the empirical feature operator around its population counterpart, an approach developed for kernel quadrature and RF regression [3, 66]. The central new ingredient is an abstract estimate on the interpolation scale of the kernel integral operator that preserves the quantifiers needed for simultaneous approximation. Combined with an effective-dimension bound, this estimate yields a single high-probability event, independent of the target, on which every target admits one reconstruction that works simultaneously across all admissible error norms. The resulting approximation theory also supplies the decisive low-dimensional approximation mechanism in our analysis of singular-value decay. 1.1. Our contributions The main results can be summarized as follows. (1) Simultaneous, target-uniform spectral approximation. Theorem 2.3 supplies the abstract approximation principle which, combined with the effective-dimension estimates in Section 3, yields the following twofold uniformity. With probability at least 1−δ1-δ, a single sampled space contains a spectrally accurate approximant for every target in a source ball, and each target admits a single coefficient vector, independent of the error norm, whose associated approximant attains spectral accuracy simultaneously in all admissible error norms. This error-norm simultaneity is enabled by formulating the ridge problem in ℋθH^θ; when θ>0θ>0, this regression norm is stronger than L2=ℋ0L^2=H^0. In particular, if p≤θp≤θ, the same ℋθH^θ-ridge reconstruction and the same target-independent event control the entire admissible weaker-norm scale. With p¯=max⁡p,2θ−1 p= \p,2θ-1\, the rate is governed by s−p¯s- p and saturates below p=2θ−1p=2θ-1. If p≥θp≥θ, the stronger error norm retains the unsaturated rate λ(s−p)/(2(1−θ))λ^(s-p)/(2(1-θ)), but the sampling condition depends on p through γ=1−pγ=1-p. This distinction identifies when one feature sample controls a full norm scale and when stronger derivative estimates require a stronger sampling condition, which is essential for the subsequent PDE analysis. (2) Multidimensional spectral rates for random Fourier features. Theorems 3.2 and 3.4 establish multidimensional rates for both regularity-adapted reference measures and uniform measures on explicitly growing frequency windows. The latter is a particularly simple sampling strategy widely used in practice. The resulting rates and the corresponding sampling strategies are summarized in Table 1. Importantly, the error estimates are not restricted to the conventional L2L^2 norm; they hold simultaneously in the general Sobolev norms Wt,p(Ω)W^t,p( ), 1≤p≤∞1≤ p≤∞. Table 1. Sample-size convergence rates and reference frequency measures in Theorems 3.2 and 3.4. For fixed δ, set LN:=N/log⁡(N/δ)L_N:=N/ (N/δ) and J:=⌊c0LN1/d⌋J:= c_0L_N^1/d , where c0=c0(d)>0c_0=c_0(d)>0 is sufficiently small. The uniform reference measure is dτSJ(w)=(2SJ)−d1QSJ(w)dwd _S_J(w)=(2S_J)^-d1_Q_S_J(w)dw; the last column records only the bandwidth SJS_J. Target class Convergence rate Reference measure in Theorem 3.2 Bandwidth in Theorem 3.4 Sobolev. LN−(s−t)/dL_N^-(s-t)/d dτ(w)∝(1+|w|2)−s¯dwdτ(w) (1+|w|^2)^- sdw SJ=J/(4R∗)S_J=J/(4R_*) Stretched exponential (s≥1)(s≥ 1). exp⁡(−cLN1/(sd)) (-cL_N^1/(sd)) dτ(w)∝exp⁡(−2κ¯|w|1/s)dwdτ(w) (-2 κ|w|^1/s)dw SJ=J/(4R∗)S_J=J/(4R_*) Super-exponential (s>1)(s>1). exp⁡(−cLN1/dlog⁡LN) (-cL_N^1/d L_N) dτ(w)∝exp⁡(−2κ¯|w|s)dwdτ(w) (-2 κ|w|^s)dw SJ=(Jlog⁡J)1/s4R∗ S_J= (J J)^1/s4R_* Bandlimited. exp⁡(−cLN1/dlog⁡LN) (-cL_N^1/d L_N) dτS(w)∝1QS(w)dwd _S(w) 1_Q_S(w)dw SJ=S_J=S The parameter M in Theorem 3.2 is an auxiliary complexity scale. For fixed δ and sufficiently large N, the sampling condition permits M≍LNM L_N, where LN:=N/log⁡(N/δ)L_N:=N/ (N/δ), which gives the sample-size rates in Table 1. The Sobolev case is algebraic, whereas the Gevrey case has the stretched-exponential rate exp⁡(−cLN1/(sd)) (-cL_N^1/(sd)), with the exponential endpoint s=d=1s=d=1. The ultra-analytic and bandlimited cases have rate exp⁡(−cLN1/dlog⁡LN) (-cL_N^1/d L_N), which is super-exponential in the linear resolution scale LN1/dL_N^1/d. (3) Consequences for PDE and eigenvalue solvers. Combining the approximation estimates with elliptic regularity, a strong-form stability estimate, Céa’s lemma, and compact-operator spectral approximation, we obtain error estimates for strong- and weak-form RFM discretizations of elliptic boundary value problems and for the associated eigenspaces and eigenvalues. (4) Rapid singular-value decay and ill-conditioning of random feature matrices. For collocation matrices generated by Fourier and tanh features, we prove, respectively, super-exponential and exponential decay of high-index singular values, together with corresponding lower bounds on their condition numbers. These results give a quantitative explanation for the severe ill-conditioning observed in high-accuracy RFM computations. Compared with our one-dimensional predecessor [46], the present paper is not merely a tensor-product extension. The earlier work uses a direct one-dimensional construction to derive expectation bounds in prescribed Wσ,pW^σ,p norms and relates one-dimensional spectral approximation to matrix ill-conditioning. Here we instead develop an operator-theoretic framework on multidimensional bounded domains, based on kernel interpolation scales, effective dimension, and empirical-operator concentration. This framework yields target-independent high-probability events and norm-independent reconstructions, covers both regularity-adapted sampling and uniform sampling on growing frequency windows, transfers the estimates to multidimensional elliptic boundary value and eigenvalue problems, and proves multidimensional singular-value decay for Fourier and tanh features. Thus the spatial setting, the probabilistic quantifiers, and the simultaneous norm control are all strengthened. A principal distinction of the first two contributions is their twofold uniformity. For each regularity class and feature representation ϱ , the high-probability event depends only on the sampled features, so the single space span⁡ϕϱ(⋅,vjϱ):1≤j≤Nspan\ _ (·,v_j ):1≤ j≤ N\ works for every target in the class. For each target u, a single coefficient vector αϱ(u)α (u) defines an approximant uNϱu_N that simultaneously attains the corresponding spectral convergence rate in every admissible error norm. Thus the random event is uniform over the target class, while the reconstruction is uniform over the error norms. To the best of our knowledge, this combination of target-uniform high-probability control, norm-independent reconstruction, and simultaneous spectral convergence throughout an admissible Sobolev/interpolation scale has not previously been established for RF approximation. 1.2. Related work For learning-based PDE solvers, random-weight approaches include RFM discretizations for stationary and time-dependent problems [8, 9] and dimension-robust methods for Kolmogorov equations [28]. Recent extensions address discontinuous interface problems [70], structure-adaptive approximation of high-dimensional elliptic equations [38], and nonlinear evolution equations [80]. Our analysis is complementary to these algorithmic developments: it isolates the approximation, PDE stability, and conditioning mechanisms needed to explain the accuracy and numerical behavior of the resulting linear least-squares discretizations. Theoretical foundations of RFM approximation. RFMs belong to the broader class of randomized neural architectures, including extreme learning machines and deep randomized networks [34, 25]. Their approximation theory includes universal and activation-specific results [33, 73], uniform random-feature approximation [61, 62], and inverse approximation theory [19]. At infinite width, these models are related to Gaussian processes [50, 79]. Within the kernel framework, Rudi and Rosasco [66] show that RFs can attain kernel-learning rates with substantially fewer features than data, while Bach [3] obtains kernel-quadrature bounds uniform over an RKHS unit ball in a prescribed L2L^2 error norm. Leverage-score and adaptive sampling further reduce feature complexity [65, 35, 40, 11]. RF architectures have also been analyzed for high-dimensional PDEs and dynamical systems [28, 27, 17, 53], and extended to operator learning between infinite-dimensional spaces [51, 52]. Spectral approximation of Gevrey targets is classical for hphp-finite elements [30, 31, 44, 23]. Related neural-network results establish geometric or exponential rates for smooth, analytic, and generalized bandlimited functions [45, 20, 48, 16]. For randomized models, spectral convergence in a fixed L2L^2-type best-approximation problem was proved by Fabiani [21], while our one-dimensional predecessor gives spectral RFM estimates in prescribed Wσ,pW^σ,p norms, in expectation [46]. Fu and Wang construct a sample-dependent operator that is uniform over a Sobolev ball and simultaneous in integer HmH^m norms, but with algebraic rates [24]. In contrast, our leverage-score analysis combines target-uniform high-probability control, one norm-independent reconstruction, and spectral convergence across the full admissible norm scale. Simultaneous approximation of a function and its derivatives is classical [43, 15] and has been used to construct common approximants in Lebesgue and Sobolev norms [22]. Such control is natural in PDE discretization, where the same trial function enters interior, boundary, and derivative-dependent estimates. The point specific to the present RF result is the conjunction of a target-uniform random event, a single reconstruction for each target, an entire admissible norm scale, and spectral rather than algebraic convergence. Conditioning of RFMtxs. Conditioning has been studied in probabilistic high-dimensional regimes [12, 13]; for structured Fourier matrices, exponential ill-conditioning is known even for contiguous submatrices [4]. Numerical work has documented the resulting difficulties in high-accuracy RFM computations [10] and motivated preconditioning strategies [74]. Our analysis instead derives multidimensional decay rates directly from low-dimensional approximation of bounded smooth features, thereby placing spectral convergence and severe ill-conditioning within the same approximation-theoretic mechanism. The remainder of the paper is organized as follows. Section 2 develops the abstract interpolation-space estimate. Section 3 specializes it to random Fourier features and relates Fourier decay to spatial regularity. Section 4 transfers the estimates to elliptic boundary value and eigenvalue problems, and Section 5 studies singular values and condition numbers. Section 6 summarizes the main results. The appendices contain the proofs and technical estimates. 1.3. Notation We denote by ℕN the set of nonnegative integers and by ℕ+N_+ the set of positive integers. For a finite set ℐI, |ℐ||I| denotes its cardinality. For a vector α, ||p| α|_p denotes its ℓp ^p-norm, and ||:=||2| α|:=| α|_2. Throughout the paper, d denotes the ambient dimension. Unless stated otherwise, Ω⊂ℝd ^d denotes a bounded Lipschitz domain. Let (,ρ)(X,ρ) be a measure space. For 1≤p≤∞1≤ p≤∞, Lp(,ρ)L^p(X,ρ) denotes the corresponding Lebesgue space. When ρ is the Lebesgue measure on Ω , we write Lp(Ω)L^p( ). In the complex case, the inner product on L2(,ρ)L^2(X,ρ) is ⟨f,g⟩ρ=∫f⁡(x)g⁡(x)¯ρ(x) f,g _ρ= _Xf(x) g(x)dρ(x). Hs(Ω)H^s( ) and Ws,p(Ω)W^s,p( ) denote the standard Sobolev spaces[1]. Hilbert-space statements are understood over ℝR or ℂC as appropriate. In the complex case, inner products are linear in the first argument and conjugate-linear in the second. For a Hilbert space ℋH, ⟨⋅,⋅⟩ℋ ·,· _H and ∥⋅∥ℋ\|·\|_H denote its inner product and norm. ∥⋅∥\|·\| denotes the operator norm when the domain and range are clear. Let ℋ1H_1, ℋ2H_2 be two Hilbert spaces, and v∈ℋ1,u∈ℋ2v _1,u _2. The rank-one operator u⊗v:ℋ1→ℋ2u v:H_1 _2 is defined as (u⊗v)x=⟨x,v⟩ℋ1u(u v)x= x,v _H_1u for x∈ℋ1x _1. For self-adjoint operators A and B on the same Hilbert space, A⪯BA B means that B−AB-A is positive semidefinite, and A⪰BA B means B⪯AB A. For a positive self-adjoint operator A, fractional powers AαA^α are defined by spectral calculus; negative powers are understood on the positive spectral subspace. We write tr⁡(A)tr(A) for the trace of a trace-class operator A. For a multi-index η=(η1,…,ηd)∈ℕdη=( _1,…, _d) ^d, set |η|:=η1+⋯+ηd|η|:= _1+·s+ _d, η!:=η1!⋯ηd!η!:= _1!·s _d!, ∂η:=∂1η1⋯∂dηd∂^η:= _1 _1·s _d _d, and wη:=w1η1⋯wdηdw^η:=w_1 _1·s w_d _d for w∈ℝdw ^d. The Fourier transform of f in the sense of distributions is denoted by f f. In particular, for any f∈L1(ℝd)f∈ L^1(R^d), the Fourier transform f f is defined as f^(ξ)=1(2π)d/2∫ℝdf(x)e−ix⋅ξdx. f(ξ)= 1(2π)^d/2 _R^df(x)e^-ix·ξ\,dx. The notation a≲ba b means a≤Cba≤ Cb for some constant C independent of b. An unsubscripted ≲ implies that C is universal, while subscripts indicate its dependence on specific parameters. We write a≃ba b if both a≲ba b and b≲ab a hold. Finally, a∝ba b denotes equality up to a positive normalization constant. 2. Approximation in kernel interpolation spaces This section proves an abstract approximation estimate for RFs in the interpolation scale generated by the kernel integral operator. The estimate accommodates independent choices of source regularity s, regression norm θ, and error norm p within their admissible ranges, thereby providing a unified route from kernel effective-dimension bounds to approximation rates across a broad class of target norms. 2.1. RKHS, interpolation spaces and feature representation Let (,ρ)(X,ρ) be a measure space. A kernel k:×→ℂk:X×X is called Hermitian positive definite if k⁡(x,y)=k⁡(y,x)¯k(x,y)= k(y,x) and, for all n∈ℕ+n _+ and xii=1n⊂\x_i\_i=1^n , the matrix (k⁡(xi,xj))1≤i,j≤n(k(x_i,x_j))_1≤ i,j≤ n is positive semidefinite. Given such a kernel k, there is a unique Hilbert space ℋkH_k such that k⁡(⋅,x)∈ℋk(·,x) _k for all x∈x , and f⁡(x)=⟨f,k⁡(⋅,x)⟩ℋkf(x)= f,k(·,x) _H_k for all f∈ℋkf _k and x∈x . The second property is known as the reproducing property and ℋkH_k is referred to as the RKHS [5, 59] associated with k. We abbreviate ℋkH_k as ℋH when no confusion arises. Assume that k is measurable and satisfies the trace condition ∫k⁡(x,x)ρ(x)<∞ _Xk(x,x)dρ(x)<∞. We also assume that the canonical embedding Iρ:ℋk→L2(,ρ)I_ρ:H_k→ L^2(X,ρ), Iρf=[f]ρI_ρf=[f]_ρ, is injective, so that functions in ℋkH_k are identified unambiguously with their L2(ρ)L^2(ρ) equivalence classes. The associated integral operator Σ:L2(,ρ)→L2(,ρ) :L^2(X,ρ)→ L^2(X,ρ) is defined by (Σf)(x)=∫k⁡(x,y)f(y)ρ(y).( f)(x)= _Xk(x,y)f(y)dρ(y). Under these assumptions, Σ is self-adjoint, positive, and trace class [69]. Let (λj,ej)j≥1\( _j,e_j)\_j≥ 1 be the positive eigenpairs of Σ , with the eigenvalues arranged in decreasing order and the eigenfunctions orthonormal in L2(,ρ)L^2(X,ρ). Then, the spectral decomposition Σ=∑j=1∞λjej⊗ej = _j=1^∞ _je_j e_j holds. Without loss of generality, we assume that ejj=1∞\e_j\_j=1^∞ forms a complete basis of L2(,ρ)L^2(X,ρ), otherwise we work on the closed positive spectral subspace of Σ , namely span¯ej:λj>0 span\e_j: _j>0\. All spectral powers below are taken on this positive spectral subspace. Following [71, 42], for a∈ℝa define ⁡(Σa) ( ^a) :=f=∑j=1∞fjej∈L2(,ρ):∑j=1∞λj2a|fj|2<∞, := \f= _j=1^∞f_je_j∈ L^2(X,ρ): _j=1^∞ _j^2a|f_j|^2<∞ \, Σaf ^af :=∑j=1∞λjafjej,f∈(Σa). := _j=1^∞ _j^af_je_j, f ( ^a). Thus Σa ^a is bounded on L2L^2 for a≥0a≥ 0 and is generally unbounded for a<0a<0. For every a∈ℝa , let ℋaH^a be the completion of span⁡ej:j≥1span\e_j:j≥ 1\ under ‖∑j=1∞fjej‖ℋa2:=∑j=1∞λj−a|fj|2. \| _j=1^∞f_je_j \|_H^a^2:= _j=1^∞ _j^-a|f_j|^2. For a≥0a≥ 0, this space is identified with f∈L2:∑jλj−a|fj|2<∞\f∈ L^2: _j _j^-a|f_j|^2<∞\, and the displayed norm equals ∥Σ−a/2f∥L2\| ^-a/2f\|_L^2. For a<0a<0, ℋaH^a is equivalently the completion of L2L^2 in this norm, or the anti-dual of ℋ−aH^-a with L2L^2 as pivot. By [71, Theorem 2.11], Σ12 12 is an isometry from L2(,ρ)L^2(X,ρ) to ℋH and ℋ1=ℋH^1=H. Additionally, ℋ0=L2(,ρ)H^0=L^2(X,ρ) and ℋa↪ℋbH^a ^b for a≥ba≥ b. The following interpolation identity is used later to connect the spectral scale with Sobolev spaces. Proposition 2.1 ([71, Theorem 4.6]). For a∈(0,1)a∈(0,1), ℋa=(L2(,ρ),ℋ)a,2H^a=(L^2(X,ρ),H)_a,2. Let (,τ)(V,τ) be a measurable parameter space equipped with a probability measure τ. Consider a parametric feature function ϕ∈L2(×,ρ⊗τ,ℂ)φ∈ L^2(X×V,ρ τ;C), where X and V denote the input and weight domains, respectively. We assume that k admits an RF representation of the form (2.1) k⁡(x,y)=∫ϕ⁡(x,v)ϕ⁡(y,v)¯τ(v).k(x,y)= _Vφ(x,v) φ(y,v)dτ(v). The corresponding feature operator :L2(,dτ)→L2(,dρ)T:L^2(V,dτ)→ L^2(X,dρ) and its adjoint operator ∗T^* are (g)(x):=∫g⁡(v)ϕ(x,v)τ(v),(∗f)(v)=∫f⁡(x)ϕ⁡(x,v)¯ρ(x).(Tg)(x):= _Vg(v)φ(x,v)dτ(v), (T^*f)(v)= _Xf(x) φ(x,v)dρ(x). It follows from Fubini’s theorem that Σ=∗ =TT^*, or equivalently, (2.2) Σ=∫ϕ⁡(⋅,v)⊗ϕ⁡(⋅,v)τ(v). = _Vφ(·,v) φ(·,v)dτ(v). Furthermore, the RKHS admits the feature-space characterization [59, Theorem 11.3] (2.3) ℋk=Ran⁡(),‖f‖ℋk=inf‖g‖L2(,dτ):g=f.H_k=Ran(T), \|f\|_H_k= \\|g\|_L^2(V,dτ):Tg=f \. 2.2. Ridge approximation in ℋθH^θ We now formulate the ridge approximation problem in the interpolation space introduced above. Specifically, let N∈ℕ+N _+ and draw v1,…,vNv_1,…,v_N independently from qdτqdτ, where q is a probability density with respect to τ satisfying the support condition specified below. Define the RF operator Φ:ℂN→L2(,dρ) :C^N→ L^2(X,dρ) by (Φ)(x)=∑j=1Nβjq(vj)−12ϕ(x,vj). ( β)(x)= _j=1^N _jq(v_j)^- 12φ(x,v_j). Assume the target function u∈ℋsu ^s with s≥0s≥ 0, which is the source condition. For θ≤sθ≤ s, we consider the minimization problem (2.4) ∗=arg⁡min∈ℂN⁡‖u−Φ‖ℋθ2+λN||2, β^*= _ β ^N \|u- β \|_H^θ^2+λ N| β|^2, where λ>0λ>0 is a regularization parameter. Then, for p≤sp≤ s, we measure the error of the RF solution as ℰ⁡(N,s,θ,p):=sup‖u‖ℋs≤1‖u−Φ∗‖ℋp.E(N,s,θ,p):= _\|u\|_H^s≤ 1 \|u- β^* \|_H^p. We aim to prove upper bounds for ℰ⁡(N,s,θ,p)E(N,s,θ,p) and |∗|| β^*| in this part. As for Problem (2.4), although practically implementing ℋθH^θ-norm is more difficult than L2L^2-norm (θ=0θ=0) in general cases, it demonstrates the possibility of solving problems by RFs under a norm stronger than L2L^2-norm. In particular, with the relation clarified in Proposition B.8, it has implications for solving PDEs in Sobolev spaces. Inspired by [42], we refined the concepts of maximum RF dimension and the effective dimension of the kernel integral operator. For θ<1θ<1, λ>0λ>0, and γ>0γ>0, denote (2.5) r⁡(x)=(x1−θ+λ)−γ2(1−θ)xγ−12,for x≥0.r(x)= (x^1-θ+λ )^- γ2(1-θ)x γ-12, $x≥ 0$. Set ℓλ(v,θ,γ):=‖r⁡(Σ)ϕ(⋅,v)‖L2(,ρ)2. _λ(v;θ,γ):=\|r( )φ(·,v)\|_L^2(X,ρ)^2. Let q be a probability density with respect to τ such that q>0q>0 τ-almost everywhere on ℓλ>0\ _λ>0\. The quotient ℓλ/q _λ/q is understood τ-almost everywhere and is set to zero on ℓλ=q=0\ _λ=q=0\. We define dmax(q,λ,θ,γ):=τ-esssupv∈⁡ℓλ(v,θ,γ)q⁡(v), d_ (q,λ;θ,γ):= *τ-ess\,sup_v _λ(v;θ,γ)q(v), d⁡(λ,θ,γ):=tr⁡(Σr2(Σ)). d(λ;θ,γ):=tr ( r^2( ) ). By (2.2), d⁡(λ,θ,γ) d(λ;θ,γ) =∫ℓλ(v,θ,γ)dτ(v) = _V _λ(v;θ,γ)dτ(v) =∫ℓλ(v,θ,γ)q⁡(v)q(v)dτ(v)≤dmax(q,λ,θ,γ). = _V _λ(v;θ,γ)q(v)q(v)dτ(v)≤ d_ (q,λ;θ,γ). Equality is attained by the normalized leverage-score density defined below. Definition 2.2 (Leverage score sampling). Assume 0<d⁡(λ,θ,γ)<∞0<d(λ;θ,γ)<∞. The normalized leverage-score density with respect to τ is (2.6) qλ∗(v,θ,γ)=ℓλ(v,θ,γ)d⁡(λ,θ,γ).q^*_λ(v;θ,γ)= _λ(v;θ,γ)d(λ;θ,γ). Sampling features from qλ∗dτq^*_λdτ is referred to as leverage-score sampling [3, 65, 35, 37, 40, 11, 41]. For a fixed penalty level λ>0λ>0, we call λ admissible for (N,δ,q,θ,γ)(N,δ,q,θ,γ) if (2.7) N≥3dmax(q,λ,θ,γ)max⁡ln⁡(14d(λ,θ,γ)/δ),1.N≥ 3d_ (q,λ;θ,γ) \ (14d(λ;θ,γ)/δ),1 \. This admissibility condition is the sampling threshold used in the empirical-operator concentration estimate below. Conversely, for N∈ℕ+N _+, the associated critical penalty level is defined by ςN(δ,q,θ,γ)=infλ>0:(2.7) holds, _N(δ,q,θ,γ)= \λ>0: ineq: N > d_max(lambda) ln(d(lambda)/delta), interpolation holds \, analogously to the construction in [42]. For fixed q,θ,γq,θ,γ, the functions dmax(q,λ,θ,γ)d_ (q,λ;θ,γ) and d⁡(λ,θ,γ)d(λ;θ,γ) are nonincreasing in λ, so every penalty level strictly above ςN(δ,q,θ,γ) _N(δ,q,θ,γ) is admissible. 2.3. Main abstract estimate and its interpretation The following theorem is the central estimate of this section. It controls both the approximation error and the Euclidean norm of the associated ridge-regression coefficient vector. It applies to the real or complex Hilbert-space setting described above. The high-probability event in the theorem depends only on the sampled features and is therefore uniform over the unit ball of ℋsH^s. Theorem 2.3. Let N∈ℕ+N _+, 0≤θ≤s≤10≤θ≤ s≤ 1, p≤sp≤ s, max⁡(θ,p)<1 (θ,p)<1, and 0<δ<10<δ<1. Assume ∑j=1∞λj1−max⁡(θ,p)<∞ _j=1^∞ _j^1- (θ,p)<∞. (1) If p≤θp≤θ, denote p¯=max⁡(p,2θ−1) p= (p,2θ-1). For any λ>0λ>0, with probability at least 1−δ1-δ, ℰ⁡(N,s,θ,p)≤16max⁡(λ,ςN)s−p¯2(1−θ)‖Σ‖p¯−p2, (N,s,θ,p)≤ 16 (λ, _N) s- p2(1-θ) \| \| p-p2, |∗|≤16N−12λs−12(1−θ)max⁡(1,ςN/λ)s−θ2(1−θ), | β^*|≤ 16N^- 12λ s-12(1-θ) (1, _N/λ) s-θ2(1-θ), where ςN=ςN(δ,q,θ,1−θ) _N= _N(δ,q,θ,1-θ). (2) If p≥θp≥θ, for any λ>0λ>0 satisfying (2.7) with γ=1−pγ=1-p, with probability at least 1−δ1-δ, ℰ⁡(N,s,θ,p)≤16λs−p2(1−θ),and |∗|≤16N−12λs−12(1−θ). (N,s,θ,p)≤ 16λ s-p2(1-θ), | β^*|≤ 16N^- 12λ s-12(1-θ). In particular, this holds for every λ>ςN(δ,q,θ,1−p)λ> _N(δ,q,θ,1-p). The proof is given in Appendix A. It first reduces the ridge error to operator norms involving the empirical resolvent (Σ~+λI)−1( +λ I)^-1, and then bounds these norms on a high-probability concentration event. Remark. Theorem 2.3 has the following interpretation. If p≤θp≤θ, the regression norm is stronger than the error norm, and the same sampling event with ςN(δ,q,θ,1−θ) _N(δ,q,θ,1-θ) controls the error simultaneously for all admissible p in this range. In particular, for 2θ−1≤p≤θ2θ-1≤ p≤θ, choosing λ≲ςNλ _N yields the spectral rate predicted by the source smoothness. The threshold p¯=max⁡(p,2θ−1) p= (p,2θ-1) records a saturation in weaker norms: when p<2θ−1p<2θ-1, lowering the error norm does not further improve the rate because the coefficient estimate is limited by the concentration of Σ~ . If p≥θp≥θ, the error norm is stronger than the regression norm, and the admissible penalty depends on 1−p1-p; thus larger p requires a correspondingly stronger regularization condition. Finally, the coefficient bound shows that |∗|| β^*| increases as λ→0+λ→ 0^+, while s=1s=1 and λ≳ςNλ _N give the scale |∗|≲N−12| β^*| N^- 12. 3. Uniform approximation of regularity classes by random Fourier features 3.1. Two equivalent forms of random Fourier features We introduce two real implementations of random Fourier features [61] generated by the same frequency measure dτ(w)dτ(w). They are distinguished at the level of the finite-dimensional trial space, but they induce the same population kernel. Randomly shifted cosine features. Consider the parameter space ph=ℝd×[0,π]V_ph=R^d×[0,π] equipped with the probability measure dμτph(w,b)=π−1dτ(w)dbd _τ^ph(w,b)=π^-1dτ(w)db. For v=(w,b)∈phv=(w,b) _ph, the feature function is defined by ϕph(x,(w,b))=2cos⁡(w⊤x+b) _ph(x,(w,b))= 2 (w x+b). The corresponding finite expansion is (3.1) uNph(x)=∑j=1Nαj2cos⁡(wj⊤x+bj).u_N^ph(x)= _j=1^N _j 2 (w_j x+b_j ). According to (2.1), the corresponding kernel is (3.2) k⁡(x,y) k(x,y) =2π∫ℝd∫0πcos⁡(w⊤x+b)cos⁡(w⊤y+b)dbdτ(w) = 2π _R^d _0^π (w x+b) (w y+b)dbdτ(w) =1π∫ℝd∫0πcos⁡(w⊤(x−y))dbdτ(w) = 1π _R^d _0^π (w (x-y))dbdτ(w) =∫ℝdcos⁡(w⊤(x−y))dτ(w). = _R^d (w (x-y))dτ(w). Cosine-sine features from the complex exponential representation. Alternatively, consider cx=ℝdV_cx=R^d equipped with dμτcx(w)=dτ(w)d _τ^cx(w)=dτ(w) and use the complex Fourier feature ϕcx(x,w)=eiw⊤x _cx(x,w)=e^iw x. According to (2.1), if τ⁡(A)=τ⁡(−A)τ(A)=τ(-A) for every Borel set A⊂ℝdA ^d, this feature induces kcx(x,y)=∫ℝdeiw⊤(x−y)τ(w)=∫ℝdcos⁡(w⊤(x−y))τ(w).k_cx(x,y)= _R^de^iw (x-y)dτ(w)= _R^d (w (x-y))dτ(w). This kernel is identical to the one in (3.2), and therefore induces the same real RKHS and associated integral operator Σ . Writing γj=aj−ibj _j=a_j-ib_j gives the equivalent real-valued expansion (3.3) uNcs(x):=Re∑j=1Nγjeiwj⊤x=∑j=1N[ajcos(wj⊤x)+bjsin(wj⊤x)].u_N^cs(x):=Re _j=1^N _je^iw_j x= _j=1^N [a_j (w_j x)+b_j (w_j x) ]. Thus each sampled frequency contributes the two real components ψcs(x,w)=(cos⁡(w⊤x),sin⁡(w⊤x)) _cs(x,w)= ( (w x), (w x) ). We use ϱ∈ph,cx ∈\ph,cx\ to index the two representations and write (ϱ,μτϱ,ϕϱ)(V_ , _τ , _ ) for the corresponding parameter space, sampling measure, and feature map. To apply the spectral framework above on the whole space L2(Ω)L^2( ), we need the associated kernel integral operators to be injective. All frequency measures considered below have symmetrized support with nonempty interior. The following lemma therefore implies that every such operator is injective and that its positive spectral subspace (ker⁡Σ)⟂( ) coincides with L2(Ω)L^2( ). Lemma 3.1 (Injectivity of translation-invariant kernel integral operators). Let Ω⊂ℝd ^d be a bounded domain, let τ be a finite nonnegative Borel measure on ℝdR^d, and let Σ be the integral operator on L2(Ω)L^2( ) induced by the kernel (3.2). Denote the symmetrization of τ by τs(A):=[τ⁡(A)+τ⁡(−A)]/2 _s(A):=[τ(A)+τ(-A)]/2 for Borel sets A⊂ℝdA ^d. If supp⁡τssupp _s has nonempty interior, then ker⁡Σ=0 =\0\; hence every eigenvalue of Σ is strictly positive. Remark. The support assumption on τs _s is essential. Without it, injectivity of Σ may fail. For example, if τ is a finite discrete measure, then the associated Fourier kernel has finite rank, and hence the corresponding integral operator has a nontrivial null space on the infinite dimensional space L2(Ω)L^2( ). The proof is given in Appendix B. 3.2. Approximation with regularity-adapted reference measures We now derive convergence rates uniformly over several target classes. For κ,a>0κ,a>0, define ℱκ,a(Ω):=u:∥u∥κ,a<∞,∥u∥κ,a:=infU|Ω=u‖eκ|⋅|aU^‖L2(ℝd),F_κ,a( ):=\u:\|u\|_κ,a<∞\, \|u\|_κ,a:= _U|_ =u \|e^κ|·|^a U \|_L^2(R^d), where the infimum is taken over all U∈L2(ℝd)U∈ L^2(R^d) whose restriction to Ω is u and whose weighted Fourier norm is finite. For S>0S>0, let ℬS(Ω)B_S( ) be the space of restrictions to Ω of functions in L2(ℝd)L^2(R^d) bandlimited to [−S,S]d[-S,S]^d, equipped with the norm ∥u∥ℬS(Ω):=inf∥U∥L2(ℝd):U|Ω=u,suppU^⊂[−S,S]d.\|u\|_B_S( ):= \\|U\|_L^2(R^d):U|_ =u,\ supp U⊂[-S,S]^d\. For any normed space X, denote its closed unit ball by X:=u∈X:‖u‖X≤1B_X:=\u∈ X:\|u\|_X≤ 1\. Theorem 3.2 is the first result in this paper that establishes spectral convergence for random Fourier feature approximation. It combines regularity-adapted reference measures with optimal leverage-score sampling and controls both the approximation error and the coefficient norm. The theorem applies separately to the two feature representations introduced in Subsection 3.1. We use ϱ∈ph,cx ∈\ph,cx\ to denote the phase and complex representations, respectively, and write uNϱu_N and αϱ(u)α (u) for the corresponding approximant and coefficient vector, where N is the number of sampled frequencies. For real-valued targets, the complex representation is realized by the cosine–sine expansion (3.3). For ρ>0ρ>0, write Qρ:=(−ρ,ρ)dQ_ρ:=(-ρ,ρ)^d. Suppose that Ω is contained, after a translation, in QRQ_R, and let Ω~ be a translated copy of QRQ_R containing Ω . For each case in Theorem 3.2, choose dτdτ and λ as specified there. For each representation ϱ , let qλ,ϱ∗q^*_λ, be the leverage-score density with respect to μτϱ _τ for the kernel integral operator on Ω in case (1) and on Ω~ in cases (2)–(4). Draw vjϱj=1N\v_j \_j=1^N independently from qλ,ϱ∗dμτϱq^*_λ, d _τ . For a density q on ϱV_ and points vj∈ϱv_j _ , define |α|ℓ2(q):=(∑j=1Nq⁡(vj)|αj|2)1/2|α|_ ^2(q):=( _j=1^Nq(v_j)| _j|^2)^1/2 for α∈ℂNα ^N. Theorem 3.2 (Regularity-adapted reference measures). Let Ω , R, and Ω~ be as above. Let ν≥0ν≥ 0 and 0<δ<10<δ<1. Let M>0M>0 and N∈ℕ+N _+ satisfy M≥eδ/14M≥ eδ/14 and N≥3Mln⁡(14M/δ)N≥ 3M (14M/δ). In (2)–(4), assume additionally that M is sufficiently large in terms of the fixed parameters. In (2) and (3), let 0<κ≤κ¯0<κ≤ κ. For each case and representation ϱ , with probability at least 1−δ1-δ, every admissible target u admits coefficients αϱ(u)α (u) such that uNϱu_N satisfies the stated bounds for all admissible error indices. The event depends only on the corresponding sampled features. (1) Sobolev ball. Let ν+d/2<s≤s¯ν+d/2<s≤ s and dτ≃(1+|w|2)−s¯dwdτ (1+|w|^2)^- sdw. There is a constant c1=c1(d,s¯,ν,Ω)>0c_1=c_1(d, s,ν, )>0. Set λ=c1M−2(s¯−ν)/dλ=c_1M^-2( s-ν)/d. Then, for all u∈Hs(Ω)u _H^s( ) and max⁡0,2ν−s¯≤t≤ν \0,2ν- s\≤ t≤ν, ∥u−uNϱ∥Ht(Ω)≲d,s¯,s,ν,t,ΩM−(s−t)/d, \|u-u_N \|_H^t( ) _d, s,s,ν,t, M^-(s-t)/d, |αϱ(u)|ℓ2(qλ,ϱ∗)≲d,s¯,s,ν,ΩN−1/2M(s¯−s)/d. |α (u)|_ ^2(q^*_λ, ) _d, s,s,ν, N^-1/2M^( s-s)/d. (2) Stretched-exponential Fourier ball. Let s≥1s≥ 1 and dτ∝e−2κ¯|w|1/sdwdτ e^-2 κ|w|^1/sdw. There exist constants cλ,aλ,ae>0c_λ,a_λ,a_e>0 and ac≥0a_c≥ 0, depending only on κ,κ¯,d,s,Rκ, κ,d,s,R. Set λ=cλexp⁡(−aλM1/(sd))λ=c_λ (-a_λM^1/(sd)). Then, for all u∈ℱκ,1/s(Ω)u _F_κ,1/s( ), t≥0t≥ 0, and 1≤p≤∞1≤ p≤∞, ∥u−uNϱ∥Wt,p(Ω)≲κ,κ¯,d,s,t,p,Rexp(−aeM1/(sd)), \|u-u_N \|_W^t,p( ) _κ, κ,d,s,t,p,R (-a_eM^1/(sd)), |αϱ(u)|ℓ2(qλ,ϱ∗)≲κ,κ¯,d,s,RN−1/2exp(acM1/(sd)). |α (u)|_ ^2(q^*_λ, ) _κ, κ,d,s,RN^-1/2 (a_cM^1/(sd)). (3) Super-exponential Fourier ball. Let s>1s>1 and dτ∝e−2κ¯|w|sdwdτ e^-2 κ|w|^sdw. There exist constants cλ,aλ,ae>0c_λ,a_λ,a_e>0 and ac≥0a_c≥ 0, depending only on κ,κ¯,d,s,Rκ, κ,d,s,R. Set λ=cλexp⁡(−aλM1/dln⁡M)λ=c_λ (-a_λM^1/d M). Then, for all u∈ℱκ,s(Ω)u _F_κ,s( ), t≥0t≥ 0, and 1≤p≤∞1≤ p≤∞, ∥u−uNϱ∥Wt,p(Ω)≲κ,κ¯,d,s,t,p,Rexp(−aeM1/dlnM), \|u-u_N \|_W^t,p( ) _κ, κ,d,s,t,p,R (-a_eM^1/d M), |αϱ(u)|ℓ2(qλ,ϱ∗)≲κ,κ¯,d,s,RN−1/2exp(acM1/dlnM). |α (u)|_ ^2(q^*_λ, ) _κ, κ,d,s,RN^-1/2 (a_cM^1/d M). (4) Bandlimited ball. Let S>0S>0 and dτ=(2S)−d1(−S,S)d(w)dwdτ=(2S)^-d1_(-S,S)^d(w)dw. There exist positive constants cλ,aλc_λ,a_λ, and aea_e, depending only on d,S,Rd,S,R. Set λ=cλexp⁡(−aλM1/dln⁡M)λ=c_λ (-a_λM^1/d M). Then, for all u∈ℬS(Ω)u _B_S( ), t≥0t≥ 0, and 1≤p≤∞1≤ p≤∞, ∥u−uNϱ∥Wt,p(Ω)≲d,t,p,S,Rexp(−aeM1/dlnM), \|u-u_N \|_W^t,p( ) _d,t,p,S,R (-a_eM^1/d M), |αϱ(u)|ℓ2(qλ,ϱ∗)≲d,S,RN−1/2. |α (u)|_ ^2(q^*_λ, ) _d,S,RN^-1/2. All constants are independent of M,N,δM,N,δ, and u; they may depend on the fixed domain and the displayed regularity and kernel parameters. One admissible explicit choice of the rate constants in cases (2)–(4) is listed in Table 2. Put σ:=κ/κ¯σ:=κ/ κ and ξs:=1−1/s _s:=1-1/s. In case (2), let b2b_2 denote the right-hand side of (B.2) with θ=σ/2θ=σ/2 and the decay parameter there replaced by κ¯ κ. For case (3), set b3:=2−1/de⁡(ξs−1(1−σ/2)−1+3/2).b_3:= 2^-1/de ( _s^-1(1-σ/2)^-1+3/2 ). Table 2. Explicit admissible rate constants in Theorem 3.2. Case aλa_λ aea_e aca_c (2) b2/2b_2/2 3σ4(2−σ)aλ 3σ4(2-σ)a_λ 1−σ2−σaλ 1-σ2-σa_λ (3) 12(1−σ/2)ξsb3 12(1-σ/2) _sb_3 3σ4(2−σ)aλ 3σ4(2-σ)a_λ 1−σ2−σaλ 1-σ2-σa_λ (4) 21−1/d28e 2^1-1/d28e 3aλ/43a_λ/4 00 In case (1), s specifies the Sobolev regularity of the target class, s¯ s determines the polynomial decay of the reference frequency measure and hence the kernel smoothness scale, and ν is the highest Sobolev order controlled by the approximation estimate. In cases (2) and (3), κ and κ¯ κ play the corresponding target and reference roles: κ quantifies the Fourier decay of the target class, whereas κ¯ κ determines the reference frequency distribution and hence the kernel interpolation scale. The parameter M is an auxiliary complexity scale. For fixed δ and sufficiently large N, the sampling condition permits M≍LNM L_N, where LN:=N/log⁡(N/δ)L_N:=N/ (N/δ), which gives the sample-size rates reported in Table 1. Case (1) gives the algebraic rate LN−(s−t)/dL_N^-(s-t)/d, whereas case (2) gives the stretched-exponential rate exp⁡(−cLN1/(sd)) (-cL_N^1/(sd)), with the exponential endpoint s=d=1s=d=1. Cases (3) and (4) yield exp⁡(−cLN1/dlog⁡LN) (-cL_N^1/d L_N), which is super-exponential in the linear resolution scale LN1/dL_N^1/d. A key strength of Theorem 3.2 is its twofold uniformity. With probability at least 1−δ1-δ, the single sampled space span⁡ϕϱ(⋅,vjϱ):1≤j≤Nspan\ _ (·,v_j ):1≤ j≤ N\ contains an approximant attaining the asserted convergence rate for every target u in the prescribed class. For each such u, one can choose a single coefficient vector αϱ(u)α (u) so that the corresponding approximant uNϱu_N satisfies all admissible error estimates simultaneously, indexed by t in case (1) and by (t,p)(t,p) in cases (2)–(4). Thus the high-probability event is uniform over the target class, while the selected approximant is uniform over the error norms. Both uniformities follow from the abstract error estimate in Theorem 2.3: the high-probability event is independent of the target, and the resulting error bounds hold simultaneously throughout the admissible interpolation scale. The proof is given in Appendix B.3. 3.3. Approximation with growing-bandwidth uniform reference measures This subsection establishes spectral convergence for a simple, broadly applicable reference-measure design: a uniform distribution on a frequency cube whose support expands at an explicit rate. The bandwidth growth law adapts this readily implementable construction to different target regularities, and the features are sampled from the associated leverage-score distribution. All results below apply separately to each fixed representation ϱ∈ph,cx ∈\ph,cx\. Since τS _S is symmetric, the two representations induce the same kernel integral operator and hence the same effective dimension, while their leverage-score densities and sampled features are representation dependent. We therefore use qλ,ϱ∗q^*_λ, and μτSϱ _ _S for the corresponding density and parameter measure. For real-valued targets in the complex representation, taking the real part gives the cosine–sine realization (3.3); the error bounds are preserved by contractivity, and |γj|2=aj2+bj2| _j|^2=a_j^2+b_j^2 preserves the weighted coefficient norm. Figure 1 summarizes the fixed and growing reference measures used below. (a) Reference measures in Theorem 3.2Schematic one-dimensional profiles; normalizing constants are suppressed.r=|w|r=|w|Polynomial taildτ(w)≍(1+|w|2)−s¯dwdτ(w) (1+|w|^2)^- s\,dwtarget: Hs(Ω)H^s( )r=|w|r=|w|Stretched-exponential taildτ(w)∝e−2κ¯|w|1/sdwdτ(w) e^-2 κ|w|^1/s\,dw, s≥1s≥ 1target: ℱκ,1/s(Ω)F_κ,1/s( )r=|w|r=|w|Super-exponential taildτ(w)∝e−2κ¯|w|sdwdτ(w) e^-2 κ|w|^s\,dw, s>1s>1target: ℱκ,s(Ω)F_κ,s( )w1w_1−S-SSSCompact spectral supportdτ(w)=(2S)−d1(−S,S)d(w)dwdτ(w)=(2S)^-d1_(-S,S)^d(w)\,dwtarget: ℬS(Ω)B_S( )(b) Growing uniform supports in Theorem 3.4dτSJ(w)=(2SJ)−d1QSJ(w)dw _S_J(w)=(2S_J)^-d1_Q_S_J(w)\,dw,QSJ=(−SJ,SJ)dQ_S_J=(-S_J,S_J)^d: uniform inside the cube and zero outside.Linear bandwidth growthSJ=J/(4R∗)S_J=J/(4R_*)Sobolev and stretched-exponential targetsJ1J_1J2J_2J3J_3Sublinear log-corrected 1/s1/s-power growthSJ=(Jlog⁡J)1/s/(4R∗)S_J=(J J)^1/s/(4R_*), s>1s>1, and SJ/J→0S_J/J→ 0Super-exponential Fourier targetsJ1J_1J2J_2J3J_3dashed outlines: linear-growth benchmark Figure 1. Reference frequency measures underlying Theorems 3.2 and 3.4. Panel (a) compares schematic one-dimensional profiles of the four reference measures. Panel (b) illustrates the two bandwidth growth laws for the cube-supported uniform reference measure. Proposition 3.3 (Leverage approximation of a growing-bandwidth target). Suppose that Ω is contained, after a translation, in QRQ_R. Let 0<a,δ<10<a,δ<1 and N∈ℕ+N _+. Suppose that U∈L2(ℝd)U∈ L^2(R^d) and supp⁡U^⊂QS¯supp U⊂ Q_S. Let J≥max⁡2SR,2J≥ \2SR,2\ be an integer. For the constant Ca,d≥1C_a,d≥ 1 supplied by Lemma B.9, set (3.4) λJ,S=Ca,d(πS)daJ−1(1+SR)a(SRJ)2aJ, _J,S=C_a,d ( πS )^daJ^-1(1+SR)^a ( SRJ )^2aJ, and assume (3.5) N≥6Jdlog⁡(28Jd/δ).N≥ 6J^d (28J^d/δ). Fix ϱ∈ph,cx ∈\ph,cx\ and draw vjϱj=1N\v_j \_j=1^N independently from qλJ,S,ϱ∗(⋅,1−a,a)dμτSϱq^*_ _J,S, (\,·\,;1-a,a)d _ _S . Then, with probability at least 1−δ1-δ, Problem 2.4 has an RF solution uN,Sϱu_N,S satisfying, for all t≥0t≥ 0 and 1≤p≤∞1≤ p≤∞, (3.6) ‖U−uN,Sϱ‖Wt,p(Ω) \|U-u_N,S \|_W^t,p( ) ≤Cd,t,p,a,R(1+dS2)(2t+d+1)/4J−1/2(1+SR)a/2(SR/J)aJ∥U∥L2(ℝd). ≤ C_d,t,p,a,R(1+dS^2)^(2t+d+1)/4J^-1/2(1+SR)^a/2(SR/J)^aJ\|U\|_L^2(R^d). The coefficients satisfy (3.7) |αϱ|ℓ2(qλJ,S,ϱ∗(⋅,1−a,a))≤16N−1/2(S/π)d/2∥U∥L2(ℝd).|α |_ ^2(q^*_ _J,S, (\,·\,;1-a,a))≤ 16N^-1/2(S/π)^d/2\|U\|_L^2(R^d). The proof is given in Appendix B.5. Theorem 3.4 (Growing uniform reference measures). Let Ω and R be as in Proposition 3.3, let 0<δ<10<δ<1 and N∈ℕ+N _+, and put R∗=max⁡R,1R_*= \R,1\. Let J be a sufficiently large integer satisfying (3.5). For each case and each fixed ϱ∈ph,cx ∈\ph,cx\, sample as in Proposition 3.3 with a=1/2a=1/2 and S=SJS=S_J. Then, with probability at least 1−δ1-δ, every admissible target admits an approximation uN,Jϱu_N,J satisfying the corresponding bounds simultaneously for all admissible t and p. The constants are independent of J,N,δJ,N,δ, and the target. (1) Sobolev ball. Let s>0s>0, 1≤p≤∞1≤ p≤∞, and u∈Ws,p(Ω)u _W^s,p( ). Take SJ=J/(4R∗)S_J=J/(4R_*). Then, for all 0≤t≤s0≤ t≤ s, (3.8) ‖u−uN,Jϱ‖Wt,p(Ω)≤CJ−(s−t).\|u-u_N,J \|_W^t,p( )≤ CJ^-(s-t). (2) Stretched-exponential Fourier ball. Let s≥1s≥ 1, κ0>0 _0>0, and u∈ℱκ0,1/s(Ω)u _F_ _0,1/s( ). Take SJ=J/(4R∗)S_J=J/(4R_*). Then, for all t≥0t≥ 0 and 1≤p≤∞1≤ p≤∞, (3.9) ‖u−uN,Jϱ‖Wt,p(Ω)≤Cexp⁡(−cJ1/s).\|u-u_N,J \|_W^t,p( )≤ C (-cJ^1/s ). The endpoint s=1s=1 is the analytic case. (3) Super-exponential Fourier ball. Let s>1s>1 and κ0>0 _0>0. Assume u∈ℱκ0,s(Ω)u _F_ _0,s( ), and take SJ=(Jlog⁡J)1/s/(4R∗)S_J=(J J)^1/s/(4R_*). Then, for all t≥0t≥ 0 and 1≤p≤∞1≤ p≤∞, (3.10) ‖u−uN,Jϱ‖Wt,p(Ω)≤Cexp⁡(−cJlog⁡J).\|u-u_N,J \|_W^t,p( )≤ C (-cJ J ). The fixed-bandwidth bandlimited case is already covered by Theorem 3.2(4). For all sufficiently large N, choose J=⌊c0(N/log⁡(N/δ))1/d⌋J= c_0 (N/ (N/δ) )^1/d , where c0=c0(d)>0c_0=c_0(d)>0 is sufficiently small, and put LN,δ:=N/log⁡(N/δ)L_N,δ:=N/ (N/δ). Then (3.5) holds, and the three rates are, respectively, (3.11) LN,δ−(s−t)/d,exp(−cLN,δ1/(sd)),exp(−cLN,δ1/dlogLN,δ).L_N,δ^-(s-t)/d, (-cL_N,δ^1/(sd)), (-cL_N,δ^1/d L_N,δ). Thus (3.11) agrees with the sample-size orders in Theorem 3.2; the conversion uses Jd≍N/log⁡(N/δ)J^d N/ (N/δ). The proof is given in Appendix B.6. Besides matching the regularity-dependent rates of Theorem 3.2, Theorem 3.4 preserves its twofold uniformity: the sampling event is target-uniform, while for each target one reconstruction attains the estimates simultaneously in all admissible Wt,pW^t,p norms. It also replaces the regularity-adapted reference measures by a particularly simple one: the uniform measure on QSJQ_S_J, with the features drawn from its associated leverage-score distribution. For both Sobolev and stretched-exponential Fourier classes, the regularity-independent bandwidth SJ=J/(4R∗)S_J=J/(4R_*), where J≍LN,δ1/dJ L_N,δ^1/d, yields the corresponding algebraic and spectral rates without prior knowledge of the target regularity; equivalently, the frequency-cube side length grows as N1/dN^1/d up to logarithmic factors. For the higher, super-exponential Fourier regularity, the faster rate is obtained by the slower bandwidth growth SJ=(Jlog⁡J)1/s/(4R∗)=o⁡(J)S_J=(J J)^1/s/(4R_*)=o(J), which concentrates the reference measure on a narrower frequency window. 3.4. Spatial interpretation of the regularity conditions Theorems 3.2 and 3.4 are formulated in Sobolev spaces and in the weighted Fourier classes ℱκ,a(Ω)F_κ,a( ). The latter classes make the approximation rates transparent, whereas the following conditions relate them to standard smoothness assumptions in the physical variable x. For completeness, we recall the Gevrey classes used below [64]. For s≥1s≥ 1, a function f∈C∞(Ω)f∈ C^∞( ) belongs to Gs(Ω)G^s( ) if, for every compact subset K⊂ΩK⊂ , there exist positive constants M,CM,C, independent of β and x∈Kx∈ K, such that |∂βf⁡(x)|≤MC|β|1(β!)s(β∈ℕ0d,x∈K).|∂^βf(x)|≤ MC^|β|_1(β!)^s (β _0^d,\ x∈ K). For s>1s>1, let G0s(Ω)G_0^s( ) denote the subspace of functions in Gs(Ω)G^s( ) with compact support in Ω . The classes are nested: Gs(Ω)⊂Gt(Ω)G^s( )⊂ G^t( ) whenever 1≤s≤t1≤ s≤ t, and G1(Ω)G^1( ) is the space of analytic functions on Ω . Moreover, both inclusions G1(Ω)⊂⋂s>1Gs(Ω),⋃s≥1Gs(Ω)⊂C∞(Ω)G^1( )⊂ _s>1G^s( ), _s≥ 1G^s( )⊂ C^∞( ) are strict. Assumption 3.5 (Spatial regularity conditions). (a) Sobolev regularity. u∈Hs(Ω)u∈ H^s( ) with s>d/2+νs>d/2+ν. (b) Gevrey regularity. For some s>1s>1, there exists a bounded open set Ω′ with Ω¯⋐Ω′ such that u extends to a function in Gs(Ω′)G^s( ). (c) Analytic regularity. For some ρ>0ρ>0, u admits an analytic continuation to ζ∈ℂd:|Im⁡ζ|<ρ\ζ ^d:|Imζ|<ρ\. Moreover, u(⋅+iy)∈L2(ℝd)u(·+iy)∈ L^2(R^d) for |y|<ρ|y|<ρ, and sup|y|≤κ∥u(⋅+iy)∥L2(ℝd)<∞for every 0<κ<ρ. _|y|≤κ\|u(·+iy)\|_L^2(R^d)<∞ every 0<κ<ρ. (d) Super-exponential Fourier decay. For some s>1s>1 and κ>0κ>0, u has an extension U to ℝdR^d satisfying eκ|⋅|sU^∈L2(ℝd)e^κ|·|^s U∈ L^2(R^d). (e) Bandlimited regularity. For some S>0S>0, u has an extension U∈L2(ℝd)U∈ L^2(R^d) satisfying supp⁡U^⊂[−S,S]dsupp U⊂[-S,S]^d. Lemma 3.6. Under Assumption 3.5, the following statements hold. (i) If (b) holds, then there exists κ>0κ>0 such that ‖u‖κ,1/s<∞\|u\|_κ,1/s<∞. (i) If (c) holds, then ‖u‖κ,1<∞\|u\|_κ,1<∞ for every 0<κ<ρ0<κ<ρ. The proof is given in Appendix B. More generally, if u∈ℱκ,a(Ω)u _κ,a( ), then Fourier multiplication and Plancherel’s identity give ‖∂βu‖L2(Ω)≤Cκ,a|β|+1(|β|!)1/a‖u‖κ,a(β∈ℕ0d).\|∂^βu\|_L^2( )≤ C_κ,a^|β|+1(|β|!)^1/a\|u\|_κ,a (β _0^d). Thus a=1/s<1a=1/s<1 yields the derivative growth of a Gevrey class of order s>1s>1, the endpoint a=1a=1 corresponds to analytic regularity, and a>1a>1 imposes an ultra-analytic derivative bound stronger than analyticity. Bandlimited functions satisfy every exponential Fourier weight and obey the Bernstein estimate ‖∂βU‖2≤(dS)|β|‖U‖2\|∂^βU\|_2≤( d\,S)^|β|\|U\|_2. Gelfand–Shilov interpretation of super-exponential decay. To make the physical-space content of Assumption 3.5(d) precise, we recall the Roumieu Gelfand–Shilov classes. For α,β>0α,β>0, the space Sαβ(ℝd)S_α^β(R^d) consists of all f∈C∞(ℝd)f∈ C^∞(R^d) for which there exist C,h>0C,h>0 such that (3.12) supx∈ℝd|xμ∂νf⁡(x)|≤Ch|μ|+|ν|(μ!)α(ν!)β,μ,ν∈ℕ0d. _x ^d|x^μ∂^νf(x)|≤ Ch^|μ|+|ν|(μ!)^α(ν!)^β, μ,ν _0^d. With this convention, the lower index controls decay in the physical variable and the upper index controls derivative growth; the Fourier transform interchanges the two indices. The Roumieu space is nontrivial exactly when α+β≥1α+β≥ 1. On the critical line α+β=1α+β=1, the existential quantifier in h is essential: the corresponding Beurling space, defined by requiring (3.12) for every h>0h>0 with a constant depending on h, is trivial [54, Chapter 6]. The reciprocal indices associated with Assumption 3.5(d) admit the following equivalent characterizations; see, for example, [54, Definition 6.1.1, Theorem 6.1.6, and Proposition 6.1.7]. Proposition 3.7 (Gelfand–Shilov characterization). Let s>1s>1, set q=s/(s−1)q=s/(s-1), α=1−1/s=1/qα=1-1/s=1/q, and β=1/sβ=1/s, and let f∈L2(ℝd)f∈ L^2(R^d). Then the following assertions are equivalent. (i) f∈S1−1/s 1/s(ℝd)f∈ S_1-1/s^\,1/s(R^d). (i) There exist a,κ>0a,κ>0 such that ea|x|s/(s−1)f∈L2(ℝd),eκ|ξ|sf^∈L2(ℝd).e^a|x|^s/(s-1)f∈ L^2(R^d), e^κ|ξ|^s f∈ L^2(R^d). (i) The function f has a C∞C^∞ representative, and there exist C,A,a>0C,A,a>0 such that |∂νf⁡(x)|≤CA|ν|(ν!)1/se−a|x|s/(s−1),x∈ℝd,ν∈ℕ0d.|∂^νf(x)|≤ CA^|ν|(ν!)^1/se^-a|x|^s/(s-1), x ^d, ν _0^d. (iv) The function f has its canonical Schwartz representative, and there exist C,a,b>0C,a,b>0 such that |f(x)|≤Ce−a|x|s/(s−1),|f^(ξ)|≤Ce−b|ξ|s,x,ξ∈ℝd.|f(x)|≤ Ce^-a|x|^s/(s-1), | f(ξ)|≤ Ce^-b|ξ|^s, x,ξ ^d. The constants in the different assertions need not coincide. In particular, when a pointwise estimate is converted into a weighted L2L^2 estimate, the weight exponent must in general be chosen strictly smaller than the exponent in the pointwise bound. Applied to the extension U in Assumption 3.5(d), Proposition 3.7 shows that the Fourier condition in (d), supplemented by ea|x|s/(s−1)U∈L2(ℝd)e^a|x|^s/(s-1)U∈ L^2(R^d) for some a>0a>0, is equivalent to U∈S1−1/s1/s(ℝd)U∈ S_1-1/s^1/s(R^d). Thus condition (d) supplies the frequency-side requirement of the Gelfand–Shilov characterization, while the additional weighted condition records the matching physical-space decay. Together with Lemma 3.6, this characterization connects Assumption 3.5 to the rate regimes in Theorems 3.2 and 3.4. Condition (a) gives the Sobolev case of the former theorem, conditions (b) and (c) yield its stretched-exponential case, and conditions (d) and (e) give the super-exponential and bandlimited cases. The latter theorem follows the same correspondence, with Ws,p(Ω)W^s,p( ) in its Sobolev case. At the Fourier level, increasingly rapid decay, from polynomial through stretched-exponential, exponential, and super-exponential decay to compact spectral support, yields the corresponding hierarchy of approximation rates. 4. RFM discretizations of PDE and eigenvalue problems This section establishes abstract error estimates for RFM discretizations. These bounds are independent of the particular RF realization and rely only on the stability of the underlying PDEs and the approximation capacity of the trial space. Throughout, VRFV_RF denotes a random linear trial space generated by finite RF expansions. Typical examples are the randomly shifted cosine space in (3.1) and the equivalent cosine–sine space in (3.3); more generally, VRFV_RF is the range of the feature operator Φ introduced in Section 2.2. Here, n denotes the unit outward normal vector on ∂Ω∂ . 4.1. Strong-form RFM Consider the boundary value problem of a general second order linear differential operator (4.1) Lu:=∑k,l=1dakl∂klu+∑k=1dbk∂ku+cu=f,x∈Ω,Bu:=g1∂u∂+g2u=g,x∈∂Ω. \ aligned Lu&:= _k,l=1^da_kl _klu+ _k=1^db_k _ku+cu=f,&&x∈ ,\\ Bu&:=g_1 ∂ u +g_2u=g,&&x∈∂ . aligned . where f∈L2(Ω)f∈ L^2( ) and g∈L2(∂Ω)g∈ L^2(∂ ). The operator B accommodates general boundary conditions. If a Dirichlet condition is imposed on ∂ΩD⊂∂Ω∂ _D⊂∂ and a Neumann or Robin condition is imposed on ∂ΩN=∂Ω∖∂ΩD∂ _N=∂ ∂ _D, then g1=g~1∂ΩNg_1= g_11_∂ _N and g2=∂ΩD+g~2∂ΩNg_2=1_∂ _D+ g_21_∂ _N. We impose the following assumptions on the coefficients of the operators L and B. Assumption 4.1. Let A=(akl)d×dA=(a_kl)_d× d be a symmetric matrix and b=(b1,…,bd)⊤b=(b_1,…,b_d) . There exist positive constants Λii=15\ _i\_i=1^5 such that for a.e. x∈Ωx∈ , ‖A⁡(x)‖2≤Λ1\|A(x)\|_2≤ _1, |b⁡(x)|≤Λ2|b(x)|≤ _2, |c⁡(x)|≤Λ3|c(x)|≤ _3, and ‖g1‖L∞(∂Ω)≤Λ4\|g_1\|_L^∞(∂ )≤ _4, ‖g2‖L∞(∂Ω)≤Λ5\|g_2\|_L^∞(∂ )≤ _5. The strong-form loss function associated with Problem (4.1) is defined as (4.2) ℒ⁡(u)= (u)= ‖Lu−f‖L2(Ω)2+γ‖Bu−g‖Hs(∂Ω)2, \|Lu-f \|_L^2( )^2+γ \|Bu-g \|_H^s(∂ )^2, where γ>0γ>0 is the boundary penalty parameter, s≥0s≥ 0, and we assume g∈Hs(∂Ω)g∈ H^s(∂ ). We evaluate the boundary residual in the general Hs(∂Ω)H^s(∂ ) norm, as recent studies [49, 36, 81] demonstrate that such stronger trace-space control may enhance the stability and accuracy of the PDE approximations. The RFM solution is then obtained by uRF∈arg⁡minu∈VRF⁡ℒ⁡(u).u_RF∈ _u∈ V_RFL(u). Under certain conditions, the error of uRFu_RF can be bounded by the approximation error of u by VRFV_RF, as established in the following theorem. Theorem 4.2 (Strong-form RFM). Assume that ∂Ω∂ is smooth, L is properly elliptic, and the coefficients of L and B are in C∞(Ω¯)C^∞( ). Let B be a normal boundary operator of order l covering L, where l=0l=0 for a Dirichlet boundary condition and l=1l=1 for a Neumann or Robin boundary condition. Let 0≤s≤3/2−l0≤ s≤ 3/2-l, assume that VRF⊂H2(Ω)V_RF⊂ H^2( ), and let u∈H2(Ω)u∈ H^2( ) be a solution to Problem (4.1). Then there exists a constant C>0C>0, independent of u and uRFu_RF, such that infv∈V‖u−uRF−v‖Hs+l+1/2(Ω)≤Cinfw∈VRF‖u−w‖H2(Ω), _v∈ V\|u-u_RF-v\|_H^s+l+1/2( )≤ C _w∈ V_RF\|u-w\|_H^2( ), where V=v∈C∞(Ω¯):Lv=0 in Ω,Bv=0 on ∂ΩV=\v∈ C^∞( ):Lv=0 in ,Bv=0 on ∂ \ is the null space. In particular, if the problem admits a unique solution, the estimate simplifies to ‖u−uRF‖Hs+l+1/2(Ω)≤Cinfw∈VRF‖u−w‖H2(Ω).\|u-u_RF\|_H^s+l+1/2( )≤ C _w∈ V_RF\|u-w\|_H^2( ). This result accommodates various boundary conditions and problems with a nontrivial null space, such as the Laplace equation with a Neumann boundary condition. In certain cases, the regularity assumptions on the coefficients and the domain boundary can be further relaxed [26, 29]; this issue is beyond the scope of the present paper. The proof is given in Appendix D.1. 4.2. Weak-form RFM Let V be a Hilbert space with norm ∥⋅∥V\|·\|_V. Consider the variational problem: find u∗∈Vu^*∈ V such that (4.3) a⁡(u∗,v)=F⁡(v),∀v∈V,a(u^*,v)=F(v), ∀ v∈ V, where a:V×V→ℝa:V× V is a bilinear form and F:V→ℝF:V is a bounded linear functional. Assume that a is continuous and coercive, i.e., there exist constants M,α>0M,α>0 such that (4.4) |a(w,v)|≤M∥w∥V∥v∥V,a(v,v)≥α∥v∥V2,∀w,v∈V.|a(w,v)|≤ M\|w\|_V\|v\|_V, a(v,v)≥α\|v\|_V^2, ∀ w,v∈ V. By the Lax–Milgram theorem, Problem (4.3) admits a unique solution. Let VRF⊂V_RF⊂ V be the RF trial space. The weak-form RFM solution uRF∈VRFu_RF∈ V_RF is defined by a⁡(uRF,v)=F⁡(v),∀v∈VRF.a(u_RF,v)=F(v), ∀ v∈ V_RF. A direct application of Céa’s lemma [7] gives Theorem 4.3 (Weak-form RFM). Under Assumption (4.4), it holds that ‖u∗−uRF‖V≤Mαinfw∈VRF‖u∗−w‖V.\|u^*-u_RF\|_V≤ Mα _w∈ V_RF\|u^*-w\|_V. We now give a concrete example. Consider the Neumann boundary value problem (4.5) −∇⋅(A(x)∇u)+cu=f,x∈Ω,A(x)∇u⋅=g,x∈∂Ω, cases-∇· (A(x)∇ u )+cu=f,&x∈ ,\\ A(x)∇ u·n=g,&x∈∂ , cases where f∈L2(Ω)f∈ L^2( ) and g∈H−1/2(∂Ω)g∈ H^-1/2(∂ ). We make the following assumption on A and c. Assumption 4.4. Let A∈L∞(Ω,ℝd×d)A∈ L^∞( ;R^d× d) be symmetric and let c∈L∞(Ω)c∈ L^∞( ). There exist positive constants Λ1 _1, a¯ a, Λ3 _3 and c¯ c such that a¯|ξ|2≤ξ⊤A(x)ξ≤Λ1|ξ|2 a|ξ|^2≤ξ A(x)ξ≤ _1|ξ|^2 and c¯≤c⁡(x)≤Λ3 c≤ c(x)≤ _3 for a.e. x∈Ωx∈ and all ξ∈ℝdξ ^d. The weak formulation of Problem (4.5) fits the abstract form (4.3) with V=H1(Ω)V=H^1( ). More precisely, (4.6) a⁡(u,v) a(u,v) =∫Ω(A(x)∇u⋅∇v+cuv)dx, = _ (A(x)∇ u·∇ v+cuv )dx, F⁡(v) F(v) =∫Ωfvdx+⟨g,v⟩∂Ω. = _ fvdx+ g,v _∂ . Here ⟨g,v⟩∂Ω g,v _∂ denotes the duality pairing between H−1/2(∂Ω)H^-1/2(∂ ) and H1/2(∂Ω)H^1/2(∂ ) through the trace of v; if g∈L2(∂Ω)g∈ L^2(∂ ), it reduces to ∫∂Ωgvs _∂ gv\,ds. Under Assumption 4.4, the bilinear form a is continuous and coercive on H1(Ω)H^1( ) with M=max⁡Λ1,Λ3M= \ _1, _3\ and α=min⁡a¯,c¯α= \ a, c\. 4.3. RFM for Eigenvalue Problems We now consider the RFM approximation for elliptic eigenvalue problems. Let a⁡(⋅,⋅)a(·,·) be a symmetric, continuous and coercive bilinear form as in the weak formulation, and let m⁡(⋅,⋅)m(·,·) be a symmetric, continuous and nonnegative bilinear form on V×V× V. Assume that the solution operator T:V→VT:V→ V defined by a⁡(Tf,v)=m⁡(f,v)a(Tf,v)=m(f,v) for all v∈Vv∈ V is compact. The continuous eigenvalue problem is to find (λ,u)∈ℝ×V(λ,u) × V, u≠0u≠ 0, such that (4.7) a⁡(u,v)=λm(u,v),∀v∈V.a(u,v)=λ m(u,v), ∀ v∈ V. The RFM eigenvalue approximation is to find (λRF,uRF)∈ℝ×VRF( _RF,u_RF) × V_RF, uRF≠0u_RF≠ 0, such that (4.8) a⁡(uRF,vRF)=λRFm(uRF,vRF),∀vRF∈VRF.a(u_RF,v_RF)= _RFm(u_RF,v_RF), ∀ v_RF∈ V_RF. Let λ be an eigenvalue of (4.7) with multiplicity q, and let E be the corresponding eigenspace. Define the best approximation error of E in VRFV_RF by ηRF(E):=supu∈E,‖u‖V=1infwRF∈VRF‖u−wRF‖V. _RF(E):= _u∈ E,\ \|u\|_V=1 _w_RF∈ V_RF\|u-w_RF\|_V. The following theorem is a direct consequence of [6, Theorems 9.12 and 9.13]. Theorem 4.5 (RFM for eigenvalue problems). Under the above assumptions, for VRFV_RF sufficiently rich, the discrete problem (4.8) has exactly q eigenvalues λRF,jj=1q\ _RF,j\_j=1^q converging to λ, counted with multiplicity. Let ERFE_RF be the space spanned by the corresponding discrete eigenfunctions. Then, there exists a constant C>0C>0, independent of VRFV_RF, such that supu∈E,‖u‖V=1infv∈ERF‖u−v‖V≤CηRF(E), _u∈ E,\ \|u\|_V=1 _v∈ E_RF\|u-v\|_V≤ C _RF(E), max1≤j≤q⁡|λ−λRF,j|≤CηRF2(E). _1≤ j≤ q|λ- _RF,j|≤ C _RF^2(E). Theorem 4.5 indicates that the convergence rate of the eigenspace matches the best approximation error, whereas the eigenvalues converge at twice this rate. We now give a concrete example. Consider the elliptic eigenvalue problem with a Neumann boundary condition −∇⋅(A(x)∇u)+cu=λu,x∈Ω,A(x)∇u⋅=0,x∈∂Ω. cases-∇· (A(x)∇ u )+cu=λ u,&x∈ ,\\ A(x)∇ u·n=0,&x∈∂ . cases Under Assumption 4.4, this problem fits the abstract formulation (4.7) with V=H1(Ω)V=H^1( ), a defined as in (4.6), and m⁡(u,v)=⟨u,v⟩L2(Ω)m(u,v)= u,v _L^2( ). Since a is symmetric, continuous and coercive on H1(Ω)H^1( ), and the embedding H1(Ω)↪L2(Ω)H^1( ) L^2( ) is compact, the associated solution operator is compact. 5. Singular values and exponential ill-conditioning of RFMtxs In this part, we analyze the exponential ill-conditioning of RFMtxs. In practical calculations, collocation points xii=1n1⊂Ω\x_i\_i=1^n_1⊂ , xii=n1+1n1+n2⊂∂Ω\x_i\_i=n_1+1^n_1+n_2⊂∂ , are selected for numerical integration to approximate the loss ℒ⁡()L( α). Denote the total number of collocation points by n=n1+n2n=n_1+n_2. Without loss of generality, in this part we set γ=1γ=1 and n>2Nn>2N. Assume Ω⊂(−1,1)d ⊂(-1,1)^d. Otherwise, a scaling argument can be applied. Define the operator L~ L by L~=L L=L in Ω and L~=B L=B on ∂Ω∂ . The vector α of trainable parameters can be obtained by solving the least squares problem = α=F, where =(Ψij)∈ℝn×2N = ( _ij ) ^n× 2N is the RFMtx with Ψij=L~ψj(xi) _ij= L _j(x_i), and =(f⁡(x1),…,f⁡(xn1),g⁡(xn1+1),…,g⁡(xn1+n2))⊤F=(f(x_1),…,f(x_n_1),g(x_n_1+1),…,g(x_n_1+n_2)) . Each column of corresponds to a feature and each row corresponds to a collocation point. For Fourier features, ψj=cos(kj⊤⋅) _j= (k_j ·) and ψj+N=sin(kj⊤⋅) _j+N= (k_j ·) for 1≤j≤N1≤ j≤ N. For tanh features, ψj=tanh(kj⊤⋅+vj) _j= (k_j ·+v_j) for 1≤j≤2N1≤ j≤ 2N. Let σm()m=12N\ _m( )\_m=1^2N be the singular values of in descending order. The following theorem estimates the decay rate of σm _m and shows that the condition number of may be extremely large. Theorem 5.1 (Fast decay of singular values). Let M>0M>0 be sufficiently large in terms of d and S, and let m∈ℕm satisfy 3Mln⁡(15M)+1≤m≤2N3M (15M)+1≤ m≤ 2N. (1) If is generated by Fourier features with kj∈[−S,S]dk_j∈[-S,S]^d, 1≤j≤N1≤ j≤ N, then (5.1) σm≲Ω,d,Λii=15,SnNexp(−aFM1/dlnM), _m _ ,d,\ _i\_i=1^5,S nN (-a_FM^1/d M ), where one may take aF:=3⋅21−1/d/(112e)a_F:=3· 2^1-1/d/(112e). (2) If is generated by tanh features with kj∈[−S,S]dk_j∈[-S,S]^d, 1≤j≤2N1≤ j≤ 2N, then (5.2) σm≲Ω,d,Λii=15,SnNexp(−aTM1/d), _m _ ,d,\ _i\_i=1^5,S nN (-a_TM^1/d ), where aT=aT(d,S)>0a_T=a_T(d,S)>0 can be chosen explicitly in terms of d and S. Theorem 5.2 (Lower bounds for condition number). Suppose that there is a constant a¯>0 a>0 such that −ξ⊤A(x)ξ≥a¯|ξ|2-ξ A(x)ξ≥ a|ξ|^2 and c⁡(x)≥0c(x)≥ 0 for all x∈Ωx∈ and ξ∈ℝdξ ^d. Let M>0M>0 be sufficiently large in terms of d and S, and assume 2N−1≥3Mln⁡(15M)2N-1≥ 3M (15M). Let aFa_F and aTa_T be as in Theorem 5.1. Use the convention σ1/σ2N=∞ _1/ _2N=∞ when σ2N=0 _2N=0. (1) Fourier features. Let kj∈[−S,S]dk_j∈[-S,S]^d. Define C,G≥0C,G≥ 0 by C2:=n1−1∑i=1n1c2(xi)C^2:=n_1^-1 _i=1^n_1c^2(x_i) and G2:=n2−1∑i=n1+1ng22(xi)G^2:=n_2^-1 _i=n_1+1^ng_2^2(x_i). Then σ1σ2N≳Ω,d,Λii=15,Sn1(a¯+C)+n2GnNexp(aFM1/dlnM). _1 _2N _ ,d,\ _i\_i=1^5,S n_1( a+C)+ n_2G nN (a_FM^1/d M ). (2) Tanh features. Let kj∈[−S,S]dk_j∈[-S,S]^d and |vj|≤dS|v_j|≤ dS. Assume b≡0b≡ 0 and that, for some r0>0r_0>0 independent of M and N, the interior collocation points satisfy (5.3) infθ∈d−1(max1≤i≤n1⁡θ⊤xi−min1≤i≤n1⁡θ⊤xi)≥2r0. _θ ^d-1 ( _1≤ i≤ n_1θ x_i- _1≤ i≤ n_1θ x_i )≥ 2r_0. Then, setting a~T:=min⁡aT,dln⁡2/(4e) a_T:= \a_T,d 2/(4e)\, we have (5.4) σ1σ2N≳Ω,d,Λii=15,S,r0a¯nNexp(a~TM1/d). _1 _2N _ ,d,\ _i\_i=1^5,S,r_0 a nN ( a_TM^1/d ). Remark. Assumption (5.3) is a quantitative full-dimensionality condition on the interior point cloud. It follows, in particular, if there exists x∘∈ℝdx_ ^d such that B¯(x∘,r0)⊂conv⁡xi:1≤i≤n1. B(x_ ,r_0) \x_i:1≤ i≤ n_1\. Indeed, maximizing and minimizing a linear functional over the convex hull and then over the enclosed ball give a directional width of at least 2r02r_0. The auxiliary estimates and the proofs of Theorems 5.1 and 5.2 are given in Appendix E. Their common key step is to approximate all feature columns simultaneously in a common low-dimensional trial space and then invoke the min–max characterization of singular values; the spectral-accuracy estimates of Section 3 make the resulting residual exponentially or super-exponentially small. Accordingly, within the regularity hierarchy covered by Theorem 3.2, greater smoothness of the activation, as expressed by stronger Fourier regularity of the associated weighted feature family, leads to faster singular-value decay. This reveals an intrinsic tradeoff: the spectral approximation power of RFM is accompanied by severe exponential ill-conditioning, which presents a major obstacle to stable high-precision solution of the resulting least-squares systems. Numerical experiments further suggest that singular values may decay more slowly as the dimension d increases, with rank deficiency most pronounced in one dimension and partially mitigated in higher dimensions [10]. This trend is qualitatively consistent with our bounds, whose decay exponents scale with M1/dM^1/d; for fixed M, this scale decreases as d grows. Localization by a partition of unity or a compatible domain decomposition can mitigate rapid singular-value decay: [46, Theorem 3.7] gives two-sided global-to-local singular-value bounds in one dimension, while numerical evidence supports the benefit of localization and local feature filtering [10, 75]. Complementary remedies include overlapping Schwarz preconditioners and randomized sketching-based right preconditioners, both supported by analysis and numerical experiments [68, 74]. 6. Conclusion We establish a multidimensional approximation theory for RFM in the interpolation scale of the associated kernel integral operator and apply it to general second-order elliptic PDEs and eigenvalue problems. We prove high-probability convergence rates ranging from super-exponential to algebraic, depending on the regularity of the target, under both regularity-adapted sampling and uniform sampling on growing frequency windows. On a single target-independent event, one sampled space approximates an entire source ball and, for each target, one norm-independent coefficient vector defines an approximant that attains spectral accuracy simultaneously in all admissible error norms. The abstract RFM solver estimates then transfer these approximation bounds to convergence estimates for strong- and weak-form RFM discretizations. Additionally, we demonstrate super-exponential singular-value decay for RFMtxs generated by Fourier features and exponential decay for those generated by tanh features, together with corresponding condition-number lower bounds. The analysis identifies spectral approximation as the common mechanism behind high accuracy and severe ill-conditioning, and extends the one-dimensional Fourier analysis of [46] to a multidimensional, operator-theoretic framework. A standard RF expansion employs basis functions of the form hj(x)=η⁡(wj⊤x+bj)h_j(x)=η(w_j x+b_j). While the explicit approximation results in Section 3 focus on trigonometric functions, the abstract estimate in Section 2 applies to any feature representation for which the kernel interpolation spaces, source conditions, and effective dimensions can be controlled. Extending spectral convergence to other activation families therefore reduces to establishing these three ingredients. The singular-value analysis in Section 5 treats each feature column as a target to be approximated in a common low-dimensional space. Hence, the same mechanism extends to bounded feature families whose derivatives required by the PDE operator admit uniform spectral approximation; the result for bounded tanh features provides one concrete analytic example. References [1] R. A. Adams and J. J. F. Fournier (2003) Sobolev spaces. Second edition, Pure and Applied Mathematics, Vol. 140, Academic Press, Amsterdam. Cited by: §1.3. [2] E. Artin (1964) The Gamma function. Athena Series: Selected Topics in Mathematics, Holt, Rinehart and Winston, New York. Cited by: Appendix C. [3] F. Bach (2017) On the equivalence between kernel quadrature rules and random feature expansions. J. Mach. Learn. Res. 18 (21), p. 1–38. Cited by: §1.2, §1, Definition 2.2. [4] A. H. Barnett (2022) How exponentially ill-conditioned are contiguous submatrices of the Fourier matrix?. SIAM Rev. 64 (1), p. 105–131. External Links: Document Cited by: §1.2. [5] A. Berlinet and C. Thomas-Agnan (2004) Reproducing kernel Hilbert spaces in probability and statistics. Springer, New York, NY. External Links: Document Cited by: §B.1, §B.1, §B.1, §B.4, §2.1. [6] D. Boffi (2010) Finite element approximation of eigenvalue problems. Acta Numer. 19, p. 1–120. External Links: Document Cited by: §4.3. [7] J. Céa (1964) Approximation variationnelle des problèmes aux limites. Ann. Inst. Fourier (Grenoble) 14 (2), p. 345–444. External Links: Document Cited by: §4.2. [8] J. Chen, X. Chi, W. E, and Z. Yang (2022) Bridging traditional and machine learning-based algorithms for solving PDEs: the random feature method. J. Mach. Learn. 1 (3), p. 268–298. External Links: Document Cited by: §1.2, §1. [9] J. Chen, W. E, and Y. Luo (2023) The random feature method for time-dependent problems. East Asian J. Appl. Math. 13 (3), p. 435–463. External Links: Document Cited by: §1.2, §1. [10] J. Chen, W. E, and Y. Sun (2024) Optimization of random feature method in the high-precision regime. Commun. Appl. Math. Comput. 6 (2), p. 1490–1517. External Links: Document Cited by: §1.2, §1, §5, §5. [11] Y. Chen and Y. Yang (2021) Fast statistical leverage score approximation in kernel ridge regression. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 130, Virtual, p. 2935–2943. Cited by: §1.2, Definition 2.2. [12] Z. Chen, H. Schaeffer, and R. Ward (2022) Concentration of random feature matrices in high-dimensions. In Proceedings of Mathematical and Scientific Machine Learning, Proceedings of Machine Learning Research, Vol. 190, Beijing, China, p. 287–302. Cited by: §1.2. [13] Z. Chen and H. Schaeffer (2024) Conditioning of random Fourier feature matrices: double descent and generalization error. Inf. Inference 13 (2), p. iaad054. External Links: Document Cited by: §1.2. [14] H. O. Cordes (1987) Spectral theory of linear differential operators and comparison algebras. London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge. External Links: Document Cited by: Lemma A.3, Appendix A. [15] F. Dai and Y. Xu (2011) Polynomial approximation in Sobolev spaces on the unit sphere and the unit ball. J. Approx. Theory 163 (10), p. 1400–1418. External Links: Document Cited by: §1.2. [16] T. De Ryck, S. Lanthaler, and S. Mishra (2021) On the approximation of functions by tanh neural networks. Neural Netw. 143, p. 732–750. External Links: Document Cited by: §1.2. [17] T. De Ryck, S. Mishra, Y. Shang, and F. Wang (2025) Approximation theory and applications of randomized neural networks for solving high-dimensional PDEs. Note: arXiv:2501.12145 External Links: 2501.12145, Document Cited by: §1.2. [18] S. Dong and Z. Li (2021) Local extreme learning machines and domain decomposition for solving linear and nonlinear partial differential equations. Comput. Methods Appl. Mech. Engrg. 387, p. 114129. External Links: Document Cited by: §1. [19] W. E, C. Ma, L. Wu, and S. Wojtowytsch (2020) Towards a mathematical understanding of neural network-based machine learning: what we know and what we don’t. CSIAM Trans. Appl. Math. 1 (4), p. 561–615. External Links: Document Cited by: §1.2. [20] W. E and Q. Wang (2018) Exponential convergence of the deep neural network approximation for analytic functions. Sci. China Math. 61 (10), p. 1733–1740. External Links: Document Cited by: §1.2. [21] G. Fabiani (2025) Random projection neural networks of best approximation: convergence theory and practical applications. SIAM J. Math. Data Sci. 7 (2), p. 385–409. External Links: Document Cited by: §1.2. [22] C. L. Fefferman, K. W. Hajduk, and J. C. Robinson (2022) Simultaneous approximation in Lebesgue and Sobolev norms via eigenspaces. Proc. Lond. Math. Soc. 125 (4), p. 759–777. External Links: Document Cited by: §1.2. [23] M. Feischl and C. Schwab (2020) Exponential convergence in H1H^1 of hphp-FEM for Gevrey regularity with isotropic singularities. Numer. Math. 144 (2), p. 323–346. External Links: Document Cited by: §1.2. [24] Z. Fu and Y. Wang (2026) Optimal sobolev approximation by deterministic and random shallow sigmoidal networks. Note: arXiv:2608.19797v2 External Links: 2608.19797v2, Document Cited by: §1.2. [25] C. Gallicchio and S. Scardapane (2020) Deep randomized neural networks. In Recent Trends in Learning From Data, L. Oneto, N. Navarin, A. Sperduti, and D. Anguita (Eds.), Studies in Computational Intelligence, Vol. 896, p. 43–68. External Links: Document Cited by: §1.2. [26] G. Geymonat (1965) Sui problemi ai limiti per i sistemi lineari ellittici. Ann. Mat. Pura Appl. 69 (1), p. 207–284. External Links: Document Cited by: §4.1. [27] L. Gonon, L. Grigoryeva, and J. Ortega (2023) Approximation bounds for random neural networks and reservoir systems. Ann. Appl. Probab. 33 (1), p. 28–69. External Links: Document Cited by: §1.2. [28] L. Gonon (2023) Random feature neural networks learn Black-Scholes type PDEs without curse of dimensionality. J. Mach. Learn. Res. 24 (189), p. 1–51. Cited by: §1.2, §1.2, §1. [29] P. Grisvard (2011) Elliptic problems in nonsmooth domains. Classics in Applied Mathematics, Society for Industrial and Applied Mathematics, Philadelphia, PA. External Links: ISBN 978-1-61197-202-3, Document Cited by: §4.1. [30] W. Gui and I. Babuška (1986) The h, p and h-p versions of the finite element method in one dimension. part i: the error analysis of the h- and h-p versions. Numer. Math. 49 (6), p. 613–657. External Links: Document Cited by: §1.2. [31] B. Guo and I. Babuška (1986) The h-p version of the finite element method. part 1: the basic approximation results. Comput. Mech. 1 (1), p. 21–41. External Links: Document Cited by: §1.2. [32] L. Hörmander (2003) The analysis of linear partial differential operators i: distribution theory and fourier analysis. 2 edition, Classics in Mathematics, Springer, Berlin, Heidelberg. External Links: Document Cited by: Appendix B. [33] G. Huang, L. Chen, and C. Siew (2006) Universal approximation using incremental constructive feedforward networks with random hidden nodes. IEEE Trans. Neural Netw. 17 (4), p. 879–892. External Links: Document Cited by: §1.2. [34] G. Huang, Q. Zhu, and C. Siew (2006) Extreme learning machine: theory and applications. Neurocomputing 70 (1–3), p. 489–501. External Links: Document Cited by: §1.2. [35] A. Kammonen, J. Kiessling, P. Plecháč, M. Sandberg, and A. Szepessy (2020) Adaptive random Fourier features with Metropolis sampling. Found. Data Sci. 2 (3), p. 309–332. External Links: Document Cited by: §1.2, Definition 2.2. [36] D. Kim and J. Song (2025) Trace regularity pinns: enforcing H12(∂Ω)H 12(∂ ) for boundary data. Note: arXiv:2510.16817 External Links: 2510.16817, Document Cited by: §4.1. [37] Z. Li (2020) On the properties of random feature methods. DPhil thesis, University of Oxford. External Links: Document Cited by: Definition 2.2. [38] J. Linghu, H. Dong, and Y. Wang (2026) A structure-adaptive random feature method for high-dimensional elliptic PDEs. Note: arXiv:2607.19786 External Links: 2607.19786, Document Cited by: §1.2. [39] J.-L. Lions and E. Magenes (1972) Non-homogeneous boundary value problems and applications. Grundlehren der mathematischen Wissenschaften, Vol. 1, Springer-Verlag, Berlin, Heidelberg. External Links: Document Cited by: §D.1, §D.1. [40] F. Liu, X. Huang, Y. Chen, J. Yang, and J. A. K. Suykens (2020) Random Fourier features via fast surrogate leverage weighted sampling. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 34, p. 4844–4851. External Links: Document Cited by: §1.2, Definition 2.2. [41] Y. Liu, J. Liu, and S. Wang (2021) Effective distributed learning with random features: improved bounds and algorithms. In International Conference on Learning Representations, Cited by: Definition 2.2. [42] J. Long, X. Peng, and L. Wu (2024) Optimal rates and saturation for noiseless kernel ridge regression. Note: arXiv:2402.15718v2 External Links: 2402.15718, Document Cited by: §2.1, §2.2, §2.2. [43] A. Meir and A. Sharma (1966) Simultaneous approximation of a function and its derivatives. SIAM J. Numer. Anal. 3 (4), p. 553–563. External Links: Document Cited by: §1.2. [44] J. M. Melenk (2002) hphp-finite element methods for singular perturbations. Lecture Notes in Mathematics, Vol. 1796, Springer, Berlin. External Links: Document Cited by: §1.2. [45] H. N. Mhaskar (1996) Neural networks for optimal approximation of smooth and analytic functions. Neural Comput. 8 (1), p. 164–177. External Links: Document Cited by: §1.2. [46] P. Ming and H. Yu (2025) Spectral convergence of random feature method in one dimension. Note: arXiv:2507.07371v2 External Links: 2507.07371v2, Document Cited by: §B.6, §1.1, §1.2, §5, §6. [47] S. Minsker (2017) On some extensions of Bernstein’s inequality for self-adjoint operators. Stat. Probab. Lett. 127, p. 111–119. External Links: Document Cited by: Proposition A.4, Appendix A. [48] H. Montanelli, H. Yang, and Q. Du (2021) Deep ReLU networks overcome the curse of dimensionality for generalized bandlimited functions. J. Comput. Math. 39 (6), p. 801–815. External Links: Document Cited by: §1.2. [49] J. Müller and M. Zeinhofer (2022) Notes on exact boundary values in residual minimisation. In Proceedings of Mathematical and Scientific Machine Learning, Proceedings of Machine Learning Research, Vol. 190, Beijing, China, p. 231–240. Cited by: §4.1. [50] R. M. Neal (1996) Priors for infinite networks. In Bayesian Learning for Neural Networks, Lecture Notes in Statistics, Vol. 118, p. 29–53. External Links: Document Cited by: §1.2. [51] N. H. Nelsen and A. M. Stuart (2021) The random feature model for input-output maps between Banach spaces. SIAM J. Sci. Comput. 43 (5), p. A3212–A3243. External Links: Document Cited by: §1.2. [52] N. H. Nelsen and A. M. Stuart (2024) Operator learning using random features: a tool for scientific computing. SIAM Rev. 66 (3), p. 535–571. External Links: Document Cited by: §1.2. [53] A. Neufeld, P. Schmocker, and S. Wu (2025) Full error analysis of the random deep splitting method for nonlinear parabolic PDEs and PIDEs. Commun. Nonlinear Sci. Numer. Simul. 143, p. 108556. External Links: Document Cited by: §1.2. [54] F. Nicola and L. Rodino (2010) Global pseudo-differential calculus on euclidean spaces. Pseudo-Differential Operators: Theory and Applications, Vol. 4, Birkhäuser, Basel. External Links: Document Cited by: §3.4, §3.4. [55] H. Ogawa (1988) An operator pseudo-inversion lemma. SIAM J. Appl. Math. 48 (6), p. 1527–1531. External Links: Document Cited by: Appendix A. [56] A. Osipov, V. Rokhlin, and H. Xiao (2013) Prolate spheroidal wave functions of order zero: mathematical tools for bandlimited approximation. Applied Mathematical Sciences, Vol. 187, Springer, New York. External Links: Document Cited by: §B.4. [57] A. Osipov (2013) Certain inequalities involving prolate spheroidal wave functions and associated quantities. Appl. Comput. Harmon. Anal. 35 (3), p. 359–393. External Links: Document Cited by: §B.4. [58] A. Osipov (2013) Certain upper bounds on the eigenvalues associated with prolate spheroidal wave functions. Appl. Comput. Harmon. Anal. 35 (2), p. 309–340. External Links: Document Cited by: §B.4. [59] V. I. Paulsen and M. Raghupathi (2016) An introduction to the theory of reproducing kernel hilbert spaces. Cambridge Studies in Advanced Mathematics, Vol. 152, Cambridge University Press, Cambridge. External Links: Document Cited by: §2.1, §2.1. [60] J. Peetre (1964) On an interpolation theorem of Foiaş and Lions. Acta Sci. Math. (Szeged) 25 (3–4), p. 255–261. Cited by: §B.2. [61] A. Rahimi and B. Recht (2007) Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, Vol. 20, p. 1177–1184. Cited by: §1.2, §1, §3.1. [62] A. Rahimi and B. Recht (2008) Uniform approximation of functions with random bases. In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, p. 555–561. External Links: Document Cited by: §1.2. [63] M. Reed and B. Simon (1975) I: Fourier analysis, self-adjointness. Methods of Modern Mathematical Physics, Vol. 2, Academic Press, New York. Cited by: §B.2. [64] L. Rodino (1993) Linear partial differential operators in gevrey spaces. World Scientific, Singapore. External Links: Document Cited by: §B.2, §3.4. [65] A. Rudi, D. Calandriello, L. Carratino, and L. Rosasco (2018) On fast leverage score sampling and optimal learning. In Advances in Neural Information Processing Systems, Vol. 31, Montréal, Canada, p. 5677–5687. Cited by: §1.2, Definition 2.2. [66] A. Rudi and L. Rosasco (2017) Generalization properties of learning with random features. In Advances in Neural Information Processing Systems, Vol. 30, p. 3215–3225. Cited by: §1.2, §1. [67] V. S. Rychkov (1999) On restrictions and extensions of the Besov and Triebel–Lizorkin spaces with respect to Lipschitz domains. J. Lond. Math. Soc. 60 (1), p. 237–257. External Links: Document Cited by: §B.2. [68] Y. Shang, A. Heinlein, S. Mishra, and F. Wang (2025) Overlapping Schwarz preconditioners for randomized neural networks with domain decomposition. Comput. Methods Appl. Mech. Engrg. 442, p. 118011. External Links: Document Cited by: §5. [69] B. Simon (2005) Trace ideals and their applications. American Mathematical Society, Providence, RI. External Links: Document Cited by: §2.1. [70] W. Song, X. Chi, Z. Yang, W. Cheng, and J. Chen (2026) Discontinuity-capturing random feature method for interface problems. Comput. Methods Appl. Mech. Engrg. 453, p. 118841. External Links: Document Cited by: §1.2. [71] I. Steinwart and C. Scovel (2012) Mercer’s theorem on general domains: on the interaction between measures, kernels, and RKHSs. Constr. Approx. 35 (3), p. 363–417. External Links: Document Cited by: §2.1, §2.1, Proposition 2.1. [72] J. Sun, S. Dong, and F. Wang (2024) Local randomized neural networks with discontinuous Galerkin methods for partial differential equations. J. Comput. Appl. Math. 445, p. 115830. External Links: Document Cited by: §1. [73] Y. Sun, A. Gilbert, and A. Tewari (2019) On the approximation properties of random ReLU features. Note: arXiv:1810.04374v3 External Links: 1810.04374, Document Cited by: §1.2. [74] L. Tan and J. Chen (2026) High-precision randomized preconditioned iterative methods for the random feature method. J. Comput. Appl. Math. 481, p. 117255. External Links: Document Cited by: §1.2, §5. [75] J. W. van Beek, V. Dolean, and B. Moseley (2026) Local feature filtering for scalable and well-conditioned domain-decomposed random feature methods. Comput. Methods Appl. Mech. Engrg. 449, p. 118583. External Links: Document Cited by: §5. [76] H. Wendland (2004) Scattered data approximation. Cambridge Monographs on Applied and Computational Mathematics, Vol. 17, Cambridge University Press, Cambridge. External Links: Document Cited by: §B.2, Proposition B.3, Proposition B.6. [77] H. Widom (1963) Asymptotic behavior of the eigenvalues of certain integral equations. Trans. Amer. Math. Soc. 109, p. 278–295. External Links: Document Cited by: §B.1, §B.1, §B.1. [78] H. Widom (1964) Asymptotic behavior of the eigenvalues of certain integral equations. I. Arch. Rational Mech. Anal. 17, p. 215–229. External Links: Document Cited by: §B.1, §B.1, §B.1, §B.1, §B.1, §B.1, §B.1. [79] C. K. I. Williams (1996) Computing with infinite networks. In Advances in Neural Information Processing Systems, Vol. 9, Cambridge, MA, p. 295–301. Cited by: §1.2. [80] H. Zhou, Z. Fu, Y. Wang, and X. Feng (2026) A discrete-time random feature method for nonlinear evolution equations with implicit–explicit Runge–Kutta time stepping. Note: arXiv:2604.25502 External Links: 2604.25502, Document Cited by: §1.2. [81] Q. Zhou, C. Chen, T. Luo, and Y. Xiang (2025) SSBE-pinn: a sobolev boundary scheme boosting stability and accuracy in elliptic/parabolic pde learning. Note: Accepted for publication in Communications in Computational Physics; arXiv:2508.10322v2 External Links: 2508.10322, Document Cited by: §4.1. Appendix A Proofs for approximation in interpolation spaces This appendix proves the abstract estimate in Section 2. We first transform the control of ℰ⁡(N,s,θ,p)E(N,s,θ,p) and |∗|| β^*| into bounding the norms of certain random operators. Denote Φ~=Σ−θ2Φ = ^- θ2 and Φ~∗=Φ∗Σ−θ2 ^*= ^* ^- θ2, where the adjoint operator Φ∗:L2(,dρ)→ℂN ^*:L^2(X,dρ) ^N, (Φ∗f)j=q(vj)−1/2⟨f,ϕ(⋅,vj)⟩L2(,dρ),1≤j≤N. ( ^*f )_j=q(v_j)^-1/2 f,φ(·,v_j) _L^2(X,dρ), 1≤ j≤ N. Since ‖u−Φ‖ℋθ=‖Σ−θ2(u−Φ)‖L2 \|u- β \|_H^θ= \| ^- θ2(u- β) \|_L^2, (2.4) has a unique solution from the usual normal equations and the matrix inversion lemma for operators[55] (A.1) ∗=(Φ~∗Φ~+λNI)−1Φ~∗Σ−θ2u=N−1Φ~∗(N−1Φ~Φ~∗+λI)−1Σ−θ2u. β^*= ( ^* +λ NI )^-1 ^* ^- θ2u=N^-1 ^* (N^-1 ^*+λ I )^-1 ^- θ2u. Denote the empirical integral operator Σ^=N−1ΦΦ∗ =N^-1 ^*, which is characterized by Σ^=1N∑j=1Nq(vj)−1ϕ(⋅,vj)⊗L2ϕ⁡(⋅,vj). = 1N _j=1^Nq(v_j)^-1φ(·,v_j) _L^2φ(·,v_j). Recall the expectation representation (2.2) for Σ , which indicates Σ=⁡(Σ^) =E( ). Similarly, denote the empirical operator Σ~=N−1Φ~Φ~∗=Σ−θ2Σ^Σ−θ2 =N^-1 ^*= ^- θ2 ^- θ2. Lemma A.1 (Resolvent reduction for ridge error and coefficient norm). The uniform approximation error ℰE and the solution vector ∗ β^* satisfy ℰ⁡(N,s,θ,p)≤λ⁡‖Σθ−p2(Σ~+λI)−1Σs−θ2‖, (N,s,θ,p)≤λ \| θ-p2( +λ I)^-1 s-θ2 \|, |∗|≤N−12‖(Σ~+λI)−12Σs−θ2‖. | β^*|≤ N^- 12 \|( +λ I)^- 12 s-θ2 \|. Proof of Lemma A.1. With the solution (A.1), we have Φ∗ β^* =Σθ2Σ~(Σ~+λI)−1Σ−θ2u. = θ2 ( +λ I)^-1 ^- θ2u. Since u∈ℋsu ^s and s≥θs≥θ, we have u=Σθ2Σ−θ2u= θ2 ^- θ2u. Hence, Φ∗−u β^*-u =Σθ2[Σ~(Σ~+λI)−1−I]Σ−θ2u = θ2 [ ( +λ I)^-1-I ] ^- θ2u =−λΣθ2(Σ~+λI)−1Σ−θ2u. =-λ θ2( +λ I)^-1 ^- θ2u. Taking the ℋpH^p-norm gives ‖u−Φ∗‖ℋp \|u- β^* \|_H^p ≤λ⁡‖Σθ−p2(Σ~+λI)−1Σs−θ2‖‖Σ−s2u‖L2. ≤λ \| θ-p2( +λ I)^-1 s-θ2 \| \| ^- s2u \|_L^2. This gives the first estimate since ‖Σ−s2u‖L2=‖u‖ℋs≤1 \| ^- s2u \|_L^2=\|u\|_H^s≤ 1. For the coefficient vector, we compute |∗|2 | β^* |^2 =N−1⟨Σ~(Σ~+λI)−1Σ−θ2u,(Σ~+λI)−1Σ−θ2u⟩ =N^-1 ( +λ I)^-1 ^- θ2u,( +λ I)^-1 ^- θ2u ≤N−1(‖Σ~12(Σ~+λI)−12‖‖(Σ~+λI)−12Σs−θ2‖‖Σ−s2u‖L2)2. ≤ N^-1 ( \| 12( +λ I)^- 12 \| \|( +λ I)^- 12 s-θ2 \| \| ^- s2u \|_L^2 )^2. The second estimate follows from ‖Σ~12(Σ~+λI)−12‖≤1 \| 12( +λ I)^- 12 \|≤ 1 and ‖u‖ℋs≤1\|u\|_H^s≤ 1, which completes the proof. ∎ Next, we study the concentration properties of the empirical operators and prepare tools for the subsequent control of the operator norms in Lemma A.1. Lemma A.2 (Preconditioned empirical concentration and resolvent comparison). Let N∈ℕ+N _+, 0<γ≤1−θ≤10<γ≤ 1-θ≤ 1, and 0<δ<10<δ<1. If the admissibility condition (2.7) holds, then (A.2) ‖r⁡(Σ)(Σ^−Σ)r(Σ)‖≤1516. \|r( )( - )r( ) \|≤ 1516. with probability at least 1−δ1-δ. On the same event, for every a∈[0,1/2]a∈[0,1/2], ‖(Σ1−θ+λI)a(Σ~+λI)−a‖≤16a. \|( ^1-θ+λ I)^a( +λ I)^-a \|≤ 16^a. To prove Lemma A.2, we use the Cordes inequality [14] and Minsker’s Bernstein inequality for self-adjoint operators [47]. Cordes’ inequality yields the fractional resolvent comparison, whereas Minsker’s inequality provides an intrinsic-dimension tail bound for r(Σ)(Σ^−Σ)r(Σ)r( )( - )r( ), with the ambient dimension replaced by the effective rank of the variance operator. Lemma A.3 (Cordes inequality [14]). Given two bounded, self-adjoint and positive operators A and B, we have ‖ArBr‖≤‖AB‖r \|A^rB^r \|≤\|AB\|^r for all r∈[0,1]r∈[0,1]. Proposition A.4 (Bernstein inequality for self-adjoint operators [47, Theorem 3.1 and Section 3.2]). Let ℋH be a separable Hilbert space, and let Xii=1n\X_i\_i=1^n be independent self-adjoint Hilbert–Schmidt random operators on ℋH such that Xi=0EX_i=0 for 1≤i≤n1≤ i≤ n and ‖∑i=1nXi2‖≤σ2 \| _i=1^nEX_i^2 \|≤σ^2. Assume that ‖Xi‖≤U \|X_i \|≤ U almost surely for all 1≤i≤n1≤ i≤ n and some positive U∈ℝU . Then, for any t≥16(U+U2+36σ2)t≥ 16 (U+ U^2+36σ^2 ), ℙ⁡(‖∑i=1nXi‖>t)≤14tr⁡(∑i=1nXi2)σ2exp⁡(−t2/2σ2+tU/3)P ( \| _i=1^nX_i \|>t )≤ 14 tr ( _i=1^nEX_i^2 )σ^2 (- t^2/2σ^2+tU/3 ) . Proof of Lemma A.2. First, we write r(Σ)(Σ^−Σ)r(Σ)r( )( - )r( ) as the sum of independent random self-adjoint operators. Denote ϕj=r⁡(Σ)ϕ(⋅,vj) _j=r( )φ(·,v_j) and Xj X_j =1Nq(vj)ϕj⊗ϕj−1NΣr2(Σ). = 1Nq(v_j) _j _j- 1N r^2( ). Then, r⁡(Σ)(Σ^−Σ)r(Σ)=∑j=1NXjr( )( - )r( )= _j=1^NX_j, Xj=0EX_j=0 and ‖Xj‖ \|X_j\| ≤1Nmax⁡(τ-esssupv∈⁡ℓλ(v,θ,γ)q⁡(v),‖Σr2(Σ)‖)=dmax(q,λ)N, ≤ 1N ( *τ-ess\,sup_v _λ(v;θ,γ)q(v),\| r^2( )\| )= d_ (q,λ)N, where we used ‖Σr2(Σ)‖≤tr⁡(Σr2(Σ))≤dmax(q,λ)\| r^2( )\| ( r^2( ) )≤ d_ (q,λ) in the equality. To control Xj2EX_j^2, we observe Xj2 _j^2 ⪯1N2[1q(vj)2‖ϕj‖L22ϕj⊗ϕj] 1N^2E [ 1q(v_j)^2\| _j\|_L^2^2 _j _j ] ⪯dmax(q,λ)N2[1q⁡(vj)ϕj⊗ϕj]=dmax(q,λ)N2Σr2(Σ). d_ (q,λ)N^2E [ 1q(v_j) _j _j ]= d_ (q,λ)N^2 r^2( ). Using 0⪯Σr2(Σ)⪯I0 r^2( ) I, we obtain ‖∑j=1NXj2‖≤dmax(q,λ)N‖Σr2(Σ)‖≤dmax(q,λ)N, \| _j=1^NEX_j^2 \|≤ d_ (q,λ)N\| r^2( )\|≤ d_ (q,λ)N, tr⁡(∑j=1NXj2)≤dmax(q,λ)Ntr⁡(Σr2(Σ))≤dmax(q,λ)d(λ)N. ( _j=1^NEX_j^2 )≤ d_ (q,λ)Ntr( r^2( ))≤ d_ (q,λ)d(λ)N. To apply Proposition A.4, we set t=15/16t=15/16 and check 16(dmax(q,λ)N+dmax2(q,λ)N2+36dmax(q,λ)N)<23≤t, 16 ( d_ (q,λ)N+ d_ ^2(q,λ)N^2+36 d_ (q,λ)N )< 23≤ t, where we used dmax(q,λ)/N≤1/3d_ (q,λ)/N≤ 1/3. Then, by Proposition A.4, ℙ⁡(‖r⁡(Σ)(Σ^−Σ)r(Σ)‖>1516)≤14d(λ)exp⁡(−75N224dmax(q,λ))≤δ, ( \|r( )( - )r( ) \|> 1516 )≤ 14d(λ) (- 75N224d_ (q,λ) )≤δ, which gives the estimate (A.2). For the second estimate, since (A.2) implies Σ−Σ^⪯1516r(Σ)−2 - 1516r( )^-2, we have Σ^+λΣθ +λ ^θ ⪰116(Σ+λΣθ)+1516[Σ+λΣθ−r(Σ)−2] 116 ( +λ ^θ )+ 1516 [ +λ ^θ-r( )^-2 ] ⪰116(Σ+λΣθ), 116 ( +λ ^θ ), where the last line follows from the fact that, for all x≥0x≥ 0, (x1−θ+λ)γ1−θx1−γ≤(x1−θ+λ)xθ, (x^1-θ+λ ) γ1-θx^1-γ≤ (x^1-θ+λ )x^θ, and x+λxθ−r(x)−2≥0x+λ x^θ-r(x)^-2≥ 0. Hence, Σ~+λI⪰(Σ1−θ+λI)/16 +λ I ( ^1-θ+λ I)/16 and ‖(Σ1−θ+λI)12(Σ~+λI)−12‖2 \|( ^1-θ+λ I) 12( +λ I)^- 12 \|^2 =‖(Σ~+λI)−12(Σ1−θ+λI)(Σ~+λI)−12‖≤16. = \|( +λ I)^- 12( ^1-θ+λ I)( +λ I)^- 12 \|≤ 16. Therefore, we have proved the second estimate for a=1/2a=1/2. Applying Lemma A.3 with A=(Σ1−θ+λI)12A=( ^1-θ+λ I) 12, B=(Σ~+λI)−12B=( +λ I)^- 12 and r=2ar=2a, we obtain ‖(Σ1−θ+λI)a(Σ~+λI)−a‖≤‖(Σ1−θ+λI)12(Σ~+λI)−12‖2a≤16a \|( ^1-θ+λ I)^a( +λ I)^-a \|≤ \|( ^1-θ+λ I) 12( +λ I)^- 12 \|^2a≤ 16^a for every a∈[0,1/2]a∈[0,1/2], which proves the second estimate and completes the proof. ∎ Now, we are ready to prove Theorem 2.3. Proof of Theorem 2.3. The concentration estimate is applied below at an arbitrary admissible penalty level η>0η>0 satisfying (2.7) with λ=ηλ=η. The quantity ςN _N is used only as the associated critical penalty level. When the infimum defining ςN _N is not attained, estimates involving ςN _N are obtained by applying the argument at admissible levels above ςN _N and passing to the limit. (1) By Lemma A.1, since Σ~ is a positive self-adjoint operator and s−p¯≤1−(2θ−1)s- p≤ 1-(2θ-1), we decompose ℰ⁡(N,s,θ,p) (N,s,θ,p) ≤λ⁡‖Σp¯−p2‖‖Σθ−p¯2(Σ~+λI)−θ−p¯2(1−θ)‖‖(Σ~+λI)−1+s−p¯2(1−θ)‖‖(Σ~+λI)−s−θ2(1−θ)Σs−θ2‖ ≤λ \| p-p2 \| \| θ- p2( +λ I)^- θ- p2(1-θ) \| \|( +λ I)^-1+ s- p2(1-θ) \| \|( +λ I)^- s-θ2(1-θ) s-θ2 \| (A.3) ≤λs−p¯2(1−θ)‖Σ‖p¯−p2‖Σθ−p¯2(Σ~+λI)−θ−p¯2(1−θ)‖‖(Σ~+λI)−s−θ2(1−θ)Σs−θ2‖. ≤λ s- p2(1-θ) \| \| p-p2 \| θ- p2( +λ I)^- θ- p2(1-θ) \| \|( +λ I)^- s-θ2(1-θ) s-θ2 \|. Note that p¯≤θ≤s p≤θ≤ s. Since θ<1θ<1, the choice γ=1−θγ=1-θ is positive. Thus, for any admissible penalty level η for (N,δ,q,θ,1−θ)(N,δ,q,θ,1-θ), Lemma A.2 with γ=1−θγ=1-θ and a=1/2a=1/2 gives, with probability at least 1−δ1-δ, ‖Σ1−θ2(Σ~+λI)−12‖ \| 1-θ2( +λ I)^- 12 \| ≤‖Σ1−θ2(Σ1−θ+ηI)−12‖‖(Σ1−θ+ηI)12(Σ~+ηI)−12‖‖(Σ~+ηI)12(Σ~+λI)−12‖ ≤ \| 1-θ2( ^1-θ+η I)^- 12 \| \|( ^1-θ+η I) 12( +η I)^- 12 \| \|( +η I) 12( +λ I)^- 12 \| ≤4max⁡(1,η/λ). ≤ 4 (1, η/λ). Similarly, we obtain ‖(Σ~+λI)−12Σ1−θ2‖≤4max⁡(1,η/λ) \|( +λ I)^- 12 1-θ2 \|≤ 4 (1, η/λ). It then follows from Lemma A.3 that ‖Σθ−p¯2(Σ~+λI)−θ−p¯2(1−θ)‖≤(16max⁡(1,η/λ))θ−p¯2(1−θ), \| θ- p2( +λ I)^- θ- p2(1-θ) \|≤(16 (1,η/λ)) θ- p2(1-θ), ‖(Σ~+λI)−s−θ2(1−θ)Σs−θ2‖≤(16max⁡(1,η/λ))s−θ2(1−θ). \|( +λ I)^- s-θ2(1-θ) s-θ2 \|≤(16 (1,η/λ)) s-θ2(1-θ). Substituting the above bounds into (A.3) yields the estimate for ℰE in (1) with ςN _N replaced by η. For every ε>0 >0, choose an admissible η≤ςN+εη≤ _N+ . Since the right-hand side is continuous and nondecreasing in η, the same estimate holds with ςN+ε _N+ in place of η with probability at least 1−δ1-δ. Letting ε↓0 0 and using continuity of probability from above gives the stated estimate. Additionally, by Lemma A.1 and the second inequality above, |∗| | β^*| ≤N−12‖(Σ~+λI)s−12(1−θ)‖‖(Σ~+λI)−s−θ2(1−θ)Σs−θ2‖ ≤ N^- 12 \|( +λ I) s-12(1-θ) \| \|( +λ I)^- s-θ2(1-θ) s-θ2 \| ≤N−12λs−12(1−θ)(16max⁡(1,η/λ))s−θ2(1−θ), ≤ N^- 12λ s-12(1-θ)(16 (1,η/λ)) s-θ2(1-θ), The same limiting argument with η≤ςN+εη≤ _N+ proves the estimate for |∗|| β^*|. (2) By Lemma A.1 and A−1−B−1=A−1(B−A)B−1A^-1-B^-1=A^-1(B-A)B^-1, we obtain ℰ⁡(N,s,θ,p) (N,s,θ,p) ≤λ⁡‖Σθ−p2(Σ1−θ+λI)−1Σs−θ2‖+λ⁡‖Σθ−p2[(Σ1−θ+λI)−1−(Σ~+λI)−1]Σs−θ2‖ ≤λ \| θ-p2( ^1-θ+λ I)^-1 s-θ2 \|+λ \| θ-p2 [( ^1-θ+λ I)^-1-( +λ I)^-1 ] s-θ2 \| (A.4) ≤λ⁡‖Σs−p2(Σ1−θ+λI)−1‖+λ⁡‖Σθ−p2(Σ1−θ+λI)−1(Σ~−Σ1−θ)(Σ~+λI)−1Σs−θ2‖, ≤λ \| s-p2( ^1-θ+λ I)^-1 \|+λ \| θ-p2( ^1-θ+λ I)^-1( - ^1-θ)( +λ I)^-1 s-θ2 \|, where the first term is bounded by λ⁡‖Σs−p2(Σ1−θ+λI)−s−p2(1−θ)‖‖(Σ1−θ+λI)−1+s−p2(1−θ)‖≤λs−p2(1−θ).λ \| s-p2( ^1-θ+λ I)^- s-p2(1-θ) \| \|( ^1-θ+λ I)^-1+ s-p2(1-θ) \|≤λ s-p2(1-θ). Since θ≤p<1θ≤ p<1, we have 0<1−p≤1−θ0<1-p≤ 1-θ, so the concentration estimate applies with γ=1−pγ=1-p. Let r⁡(x)r(x) be defined in (2.5) with this choice of γ. Then, the second term in (A.4) is bounded by λ⁡‖(Σ1−θ+λI)2θ−p−12(1−θ)‖‖r⁡(Σ)(Σ^−Σ)r(Σ)‖‖Σp−θ2(Σ1−θ+λI)1−p2(1−θ)(Σ~+λI)−1Σs−θ2‖ λ \|( ^1-θ+λ I) 2θ-p-12(1-θ) \| \|r( )( - )r( ) \| \| p-θ2( ^1-θ+λ I) 1-p2(1-θ)( +λ I)^-1 s-θ2 \| ≤1516λ1−p2(1−θ)‖Σp−θ2(Σ1−θ+λI)θ−p2(1−θ)‖‖(Σ1−θ+λI)12(Σ~+λI)−1Σs−θ2‖ ≤ 1516λ 1-p2(1-θ) \| p-θ2( ^1-θ+λ I) θ-p2(1-θ) \| \|( ^1-θ+λ I) 12( +λ I)^-1 s-θ2 \| ≤1516λ1−p2(1−θ)‖(Σ1−θ+λI)12(Σ~+λI)−12‖‖(Σ~+λI)s−12(1−θ)‖‖(Σ~+λI)θ−s2(1−θ)(Σ1−θ+λI)s−θ2(1−θ)‖ ≤ 1516λ 1-p2(1-θ) \|( ^1-θ+λ I) 12( +λ I)^- 12 \| \|( +λ I) s-12(1-θ) \| \|( +λ I) θ-s2(1-θ)( ^1-θ+λ I) s-θ2(1-θ) \| ≤15λs−p2(1−θ), ≤ 15λ s-p2(1-θ), where we used the first claim of Lemma A.2 in the first inequality and the second claim of Lemma A.2 in the last inequality. The bound for |∗|| β^*| follows in the same way as in (1), using the admissibility of λ with γ=1−pγ=1-p. This completes the proof. ∎ Appendix B Proofs for uniform approximation by random Fourier features This appendix supplies the Fourier-specific ingredients used to derive the uniform approximation results in Section 3. The argument has three layers. We first show that the relevant kernel integral operators are injective, so the positive spectral subspace is all of L2(Ω)L^2( ). Subsection B.1 then bounds the effective dimension in the four frequency-decay regimes, while Subsection B.2 identifies the target and error spaces with the appropriate kernel interpolation spaces. These ingredients are assembled in Subsection B.3 to prove the regularity-adapted approximation theorem. The remaining subsections adapt the same strategy to growing uniform frequency supports and prove Proposition 3.3 and Theorem 3.4. Injectivity of the kernel integral operator. The following proof justifies working on the full space L2(Ω)L^2( ) for all frequency measures used in Section 3. Proof of Lemma 3.1. Since τs _s is the symmetrized measure of τ, the kernels defined by (3.2) using τ and τs _s coincide. Consequently, we have k⁡(x,y) k(x,y) =∫ℝdeiw⊤(x−y)dτs(w). = _R^de^iw (x-y)\,d _s(w). For any f∈L2(Ω)f∈ L^2( ), let F:=fΩF:=f1_ denote its zero extension outside Ω . The boundedness of Ω ensures that F∈L1(ℝd)∩L2(ℝd)F∈ L^1(R^d)∩ L^2(R^d). Applying Fubini’s theorem yields ⟨Σf,f⟩L2(Ω) f,f _L^2( ) =∫Ω∫Ωk⁡(x,y)f(y)f⁡(x)¯yx = _ _ k(x,y)f(y) f(x)\,dy\,dx =∫ℝd(∫Ωf⁡(y)e−iw⊤ydy)(∫Ωf⁡(x)e−iw⊤xdx)¯dτs(w) = _R^d ( _ f(y)e^-iw y\,dy ) ( _ f(x)e^-iw x\,dx )\,d _s(w) =∫ℝd|∫Ωf⁡(x)e−iw⊤xdx|2dτs(w). = _R^d | _ f(x)e^-iw x\,dx |^2\,d _s(w). Now assume Σf=0 f=0. Then ⟨Σf,f⟩L2(Ω)=0 f,f _L^2( )=0, and hence ∫Ωf⁡(x)e−iw⊤xx=0,for τs-a.e. w. _ f(x)e^-iw x\,dx=0, _s-a.e. w. The function w↦∫Ωf⁡(x)e−iw⊤xxw _ f(x)e^-iw x\,dx is continuous on ℝdR^d. Therefore it vanishes on supp⁡τssupp _s. Since supp⁡τssupp _s contains a nonempty open set, the Fourier transform of F vanishes on a nonempty open subset of ℝdR^d. Since F has compact support, the Paley–Wiener–Schwartz theorem [32, Theorem 7.3.1] implies that its Fourier transform extends to an entire function on ℂdC^d. By the identity theorem for real-analytic functions, the Fourier transform of F vanishes identically on ℝdR^d. The injectivity of the Fourier transform then implies F=0F=0 almost everywhere. Hence f=0f=0 in L2(Ω)L^2( ). Thus ker⁡Σ=0 =\0\, which completes the proof. ∎ With the spectral subspace identified, we next estimate its effective dimension and then relate the resulting interpolation scale to the target and error spaces. B.1. Effective-dimension estimates for translation-invariant kernels This subsection proves the spectral estimates used in Proposition B.2 and hence in Theorem 3.2. We first state a Fourier-multiplier comparison lemma and the resulting four-regime effective-dimension bound. We then prove the comparison lemma and apply it, together with the eigenvalue asymptotics of [77, 78], in each decay regime. We use the complete elliptic integral of the first kind (r):=∫0π/2(1−r2sin2θ)−1/2dθ,0≤r<1, K(r):= _0^π/2 (1-r^2 ^2θ )^-1/2dθ, 0≤ r<1, and set Υ⁡(x):=x (x):=x^x for x>0x>0. Comparison and effective-dimension statements. To formulate the operator comparisons used below, consider an integral operator (B.1) Tf(x)=∫ℝd1Ω(x)k(x−y)1Ω(y)f(y)y,Tf(x)= _R^d1_ (x)k(x-y)1_ (y)f(y)dy, where k∈L1(ℝd)k∈ L^1(R^d) has a nonnegative Fourier transform K⁡(ξ)=∫ℝdk⁡(x)e−ıξ⊤xx.K(ξ)= _R^dk(x)e^- ξ xdx. The following monotonicity lemma allows us to compare the eigenvalues of translation-invariant integral operators through their Fourier multipliers. Lemma B.1. Let Tjj=12\T_j\_j=1^2 be integral operators of the form (B.1) with kernels kjj=12\k_j\_j=1^2. Assume that kj(x)=(2π)−d∫ℝdKj(ξ)eıξ⊤xξ,k_j(x)=(2π)^-d _R^dK_j(ξ)e ξ xdξ, and that 0≤K2(ξ)≤K1(ξ)0≤ K_2(ξ)≤ K_1(ξ) almost everywhere. Then 0⪯T2⪯T10 T_2 T_1. Proposition B.2. Let Σ be the integral operator on L2(Ω)L^2( ) associated with the translation-invariant kernel in (3.2). Let 0<λ0<λ, 0<γ≤1−θ≤10<γ≤ 1-θ≤ 1, and d⁡(λ,θ,γ):=tr⁡[(Σ1−θ+λI)−γ1−θΣγ].d(λ;θ,γ):=tr [ ( ^1-θ+λ I )^- γ1-θ ^γ ]. (1) Let sγ>d/2sγ>d/2 and suppose that, for some 0<cτ≤Cτ<∞0<c_τ≤ C_τ<∞, cτ(1+|w|2)−s≤dτdw(w)≤Cτ(1+|w|2)−sfor a.e. w∈ℝd.c_τ(1+|w|^2)^-s≤ dτdw(w)≤ C_τ(1+|w|^2)^-s a.e. w ^d. Then, there exist constants c1>0c_1>0 and M0>0M_0>0, depending on d,s,θ,γ,Ω,cτd,s,θ,γ, ,c_τ, and CτC_τ, such that for λ=c1(|Ω|/M)2s(1−θ)/dλ=c_1(| |/M)^2s(1-θ)/d, d⁡(λ)≤Md(λ)≤ M whenever M≥M0M≥ M_0. (2) Let R,κ>0R,κ>0, s≥1s≥ 1, Ω=(−R,R)d =(-R,R)^d and dτ∝e−2κ|w|1/sdwdτ e^-2κ|w|^1/sdw. Then, for any (B.2) 0<κs<(1−θ)κ22/(sd)sd2−1/(2s)R1/s, for s>1,(1−θ)(sech⁡πRdκ−1)21/dd(tanh⁡πRdκ−1), for s=1,0< _s< cases (1-θ)κ2^2/(sd)sd^2-1/(2s)R^1/s,& for s>1,\\ (1-θ) K(sechπ R dκ^-1)2^1/dd K( π R dκ^-1),& for s=1,\\ cases there exists a constant c2c_2 depending on κ,d,s,γ,Rκ,d,s,γ,R such that, for λ=c2exp⁡(−κsM1/(sd)),λ=c_2 (- _sM^1/(sd) ), one has d⁡(λ)≤Md(λ)≤ M for all sufficiently large M. (3) Let R,κ>0R,κ>0, s>1s>1, Ω=(−R,R)d =(-R,R)^d, and dτ∝e−2κ|w|sdwdτ e^-2κ|w|^sdw. For any 0<κ¯(s)<2−2/s0< κ(s)<2-2/s, there exists a constant c3c_3 depending on κ,κ¯,d,s,γ,Rκ, κ,d,s,γ,R such that, for λ=c3Υ[(M/2)1/de⁡(κ¯−1γ−1+3/2)]−(1−θ)κ¯d,λ=c_3 [ (M/2)^1/de( κ^-1γ^-1+3/2) ]^-(1-θ) κd, one has d⁡(λ)≤Md(λ)≤ M for all sufficiently large M. (4) Let R,S>0R,S>0, Ω=(−R,R)d =(-R,R)^d, and dτ∝1(−S,S)d(w)dwdτ 1_(-S,S)^d(w)dw. For any 0<κ¯<20< κ<2, there exists a constant CBanC_Ban depending only on SRSR such that, for λ=(π/S)(1−θ)dCBan1−θΥ[(M/2)1/de⁡(κ¯−1γ−1+3/2)]−(1−θ)κ¯d,λ=(π/S)^(1-θ)dC_Ban^1-θ [ (M/2)^1/de( κ^-1γ^-1+3/2) ]^-(1-θ) κd, one has d⁡(λ)≤Md(λ)≤ M for all sufficiently large M. Proofs of the spectral estimates. If λjj≥1\ _j\_j≥ 1 are the positive eigenvalues of Σ , then d⁡(λ,θ,γ)=tr⁡[(Σ1−θ+λI)−γ1−θΣγ]=∑j=1∞λjγ(λj1−θ+λ)γ1−θ.d(λ;θ,γ)=tr [ ( ^1-θ+λ I )^- γ1-θ ^γ ]= _j=1^∞ _j^γ ( _j^1-θ+λ ) γ1-θ. The eigenvalue decay estimates below are based on [77, 78]. Proof of Lemma B.1. For every f∈L2(ℝd)f∈ L^2(R^d), a direct calculation gives ⟨Tjf,f⟩L2(ℝd) T_jf,f _L^2(R^d) =∫ℝd∫ℝd1Ω(x)kj(x−y)1Ω(y)f(y)f⁡(x)¯yx = _R^d _R^d1_ (x)k_j(x-y)1_ (y)f(y) f(x)dydx =(2π)−d∫ℝdKj(ξ)|∫ℝd1Ω(x)f(x)e−ıξ⊤xdx|2dξ. =(2π)^-d _R^dK_j(ξ) | _R^d1_ (x)f(x)e^- ξ xdx |^2dξ. Hence 0≤⟨T2f,f⟩L2(ℝd)≤⟨T1f,f⟩L2(ℝd)0≤ T_2f,f _L^2(R^d)≤ T_1f,f _L^2(R^d) for every f∈L2(ℝd)f∈ L^2(R^d), which proves the claim and completes the proof. ∎ Proof of Proposition B.2. The inequality (at+bt)/2≤(a+b)t≤at+bt(a^t+b^t)/2≤(a+b)^t≤ a^t+b^t for a,b>0a,b>0 and 0≤t≤10≤ t≤ 1 gives (B.3) ∑j=1∞λjγλjγ+λγ1−θ≤d⁡(λ,θ,γ)≤∑j=1∞2λjγλjγ+λγ1−θ. _j=1^∞ _j^γ _j^γ+λ γ1-θ≤ d(λ;θ,γ)≤ _j=1^∞ 2 _j^γ _j^γ+λ γ1-θ. It remains to estimate the eigenvalues and the resulting series in the four cases of the proposition. Case (1): polynomial decay. Let Σs _s be the integral operator corresponding to the Fourier multiplier (1+|w|2)−s(1+|w|^2)^-s. The upper comparison assumption on dτdτ and Lemma B.1 give 0⪯Σ⪯CτΣs,λj(Σ)≤Cτλj(Σs).0 C_τ _s, _j( )≤ C_τ _j( _s). By [77, Theorem I], the nonincreasing function equimeasurable with 1Ω(x)(1+|w|2)−s1_ (x)(1+|w|^2)^-s on ℝd×ℝdR^d×R^d is ϕ0(t)=[(t|Ω||B1(0)|)2/d+1]−s, _0(t)= [ ( t| ||B_1(0)| )^2/d+1 ]^-s, and hence λj(Σs)≲d,s,Ωj−2s/d _j( _s) _d,s, j^-2s/d for all sufficiently large j. Enlarging the constant to cover the finitely many remaining eigenvalues yields λj(Σ)≲d,s,Ω,Cτj−2s/d(j∈ℕ+). _j( ) _d,s, ,C_τj^-2s/d (j _+). Substituting this estimate into (B.3) and applying Lemma C.1 yield d(λ)≲d,s,θ,γ,Ω,Cτλ−d2s(1−θ),d(λ) _d,s,θ,γ, ,C_τλ^- d2s(1-θ), which implies the desired bound after choosing c1c_1 and M0M_0 sufficiently large in terms of the parameters specified in the proposition. Case (2): subexponential and exponential decay. For any R>0R>0, the eigenvalues of the operator in (B.1) are unchanged if 1Ω(⋅)1_ (·) is replaced by 1Ω(R⋅)1_ (R·) and k⁡(⋅)k(·) by Rdk(R⋅)R^dk(R·). We only need to consider the operator in (B.1) with Ω=(−1,1)d =(-1,1)^d and kernel k~(x)=Cκ,d,s−1∫ℝde−2κR−1/s|w|1/s+ıw⊤xdw. k(x)=C_κ,d,s^-1 _R^de^-2κ R^-1/s|w|^1/s+ w xdw. It follows from Hölder’s inequality that d1/(2s)−1∑p=1d|wp|1/s≤|w|1/s.d^1/(2s)-1 _p=1^d|w_p|^1/s≤|w|^1/s. To control λj(Σ) _j( ), Lemma B.1 reduces the problem to the operator TGevT_Gev of the form (B.1) with Ω=(−1,1)d =(-1,1)^d and kernel kGev(x) k_Gev(x) =Cκ,d,s−1∏p=1d∫ℝexp(−κR−1/sd1/(2s)−1|wp|1/s+ıwpxp)dwp. =C_κ,d,s^-1 _p=1^d _R (-κ R^-1/sd^1/(2s)-1|w_p|^1/s+ w_px_p )dw_p. Denote by TGev(p)T_Gev^(p) the one-dimensional integral operators of the form (B.1) on (−1,1)(-1,1) with kernel kGev(p)(xp):=∫ℝexp(−κR−1/sd1/(2s)−1|wp|1/s+ıwpxp)dwp.k_Gev^(p)(x_p):= _R (-κ R^-1/sd^1/(2s)-1|w_p|^1/s+ w_px_p )dw_p. Then, the eigenvalues of TGevT_Gev are [5] Cκ,d,s−1∏p=1dλjp(TGev(p)),j1,j2,…,jd∈ℕ+.C_κ,d,s^-1 _p=1^d _j_p(T_Gev^(p)), j_1,j_2,…,j_d _+. For s>1s>1, [78, Theorem I] gives limj→∞λj(TGev(p))2πexp(−κR−1/sd1/(2s)−1[πj/2+o(j)]1/s)=1. _j→∞ _j(T_Gev^(p))2π (-κ R^-1/sd^1/(2s)-1[π j/2+o(j)]^1/s )=1. Thus, for κ~<κd(πd2R)1/s, κ< κd ( π d2R )^1/s, there exists a constant CGevC_Gev such that λj(TGev(p))≤CGev1/de−κ~j1/s _j(T_Gev^(p))≤ C_Gev^1/de^- κj^1/s for all j. For s=1s=1, [78, Theorem I] gives limj→∞ln⁡λj(TGev(p))jπ=−⁡(sech⁡πRdκ−1)⁡(tanh⁡πRdκ−1). _j→∞ _j(T_Gev^(p))jπ=- K(sechπ R dκ^-1) K( π R dκ^-1). Hence, for κ~<π⁡(sech⁡πRdκ−1)⁡(tanh⁡πRdκ−1), κ<π K(sechπ R dκ^-1) K( π R dκ^-1), there exists a constant CGevC_Gev such that λj(TGev(p))≤CGev1/de−κ~j _j(T_Gev^(p))≤ C_Gev^1/de^- κj for all j. By (B.3), d⁡(λ,θ,γ) d(λ;θ,γ) ≤∑j∈ℕ+d2Cκ,d,s−γCGevγe−κ~γ∑p=1djp1/sCκ,d,s−γCGevγe−κ~γ∑p=1djp1/s+λγ1−θ ≤ _j _+^d 2C_κ,d,s^-γC_Gev^γe^- κγ _p=1^dj_p^1/sC_κ,d,s^-γC_Gev^γe^- κγ _p=1^dj_p^1/s+λ γ1-θ ≤∑j∈ℕ+d2e−κ~γ|j|11/se−κ~γ|j|11/s+Cκ,d,sγCGev−γλγ1−θ, ≤ _j _+^d 2e^- κγ|j|_1^1/se^- κγ|j|_1^1/s+C_κ,d,s^γC_Gev^-γλ γ1-θ, where we used ∑p=1djp1/s≥|j|11/s _p=1^dj_p^1/s≥|j|_1^1/s. Lemma C.2 yields d(λ;θ,γ)≤2(2+1d=1)[sdκ~−1ln(Cκ,d,s−1CGevλ−11−θ)]sd.d(λ;θ,γ)≤ 2(2+1_\d=1\) [sd κ^-1 (C_κ,d,s^-1C_Gevλ^- 11-θ) ]^sd. Consequently, d⁡(λ)≤Md(λ)≤ M is guaranteed by λ=Cκ,d,sθ−1CGev1−θexp⁡(−(1−θ)κ~M1/(sd)[2(2+1d=1)]1/(sd)sd),λ=C_κ,d,s^θ-1C_Gev^1-θ (- (1-θ) κM^1/(sd) [2(2+1_\d=1\) ]^1/(sd)sd ), which implies the desired bound in (2). Case (3): super-exponential decay. As in Case (2), scaling reduces the problem to (B.1) on (−1,1)d(-1,1)^d with kernel k~(x)=Cκ,d,s−1∫ℝde−2κR−s|w|s+ıw⊤xw. k(x)=C_κ,d,s^-1 _R^de^-2κ R^-s|w|^s+ w xdw. Hölder’s inequality gives min⁡(1,ds/2−1)∑p=1d|wp|s≤|w|s. (1,d^s/2-1) _p=1^d|w_p|^s≤|w|^s. Lemma B.1 reduces the estimate to TSupT_Sup with kernel kSup(x)=Cκ,d,s−1∏p=1d∫ℝexp⁡(−κmin⁡(1,ds/2−1)R−s|wp|s+iwpxp)dwp.k_Sup(x)=C_κ,d,s^-1 _p=1^d _R (-κ (1,d^s/2-1)R^-s|w_p|^s+iw_px_p )dw_p. Let TSup(p)T_Sup^(p) be the corresponding one-dimensional operator. The eigenvalues of TSupT_Sup are [5] Cκ,d,s−1∏p=1dλjp(TSup(p)),j1,j2,…,jd∈ℕ+.C_κ,d,s^-1 _p=1^d _j_p(T_Sup^(p)), j_1,j_2,…,j_d _+. By [78, Corollary 1], limj→∞ln⁡λj(TSup(p))jln⁡j=−(2−2/s). _j→∞ _j(T_Sup^(p))j j=-(2-2/s). Thus, for any 0<κ¯(s)<2−2/s0< κ(s)<2-2/s, there exists a constant CSup=CSup(κ,κ¯,d,s,R)C_Sup=C_Sup(κ, κ,d,s,R) such that λj(TSup(p))≤CSup1/de−κ¯jln⁡j _j(T_Sup^(p))≤ C_Sup^1/de^- κj j for all j∈ℕ+j _+. It follows from (B.3) that d⁡(λ,θ,γ) d(λ;θ,γ) ≤∑j∈ℕ+d2Cκ,d,s−γCSupγe−κ¯γ∑p=1djplnjpCκ,d,s−γCSupγe−κ¯γ∑p=1djplnjp+λγ1−θ ≤ _j _+^d 2C_κ,d,s^-γC_Sup^γe^- κγ _p=1^dj_p j_pC_κ,d,s^-γC_Sup^γe^- κγ _p=1^dj_p j_p+λ γ1-θ ≤∑j∈ℕ+d2e−κ¯γ∑p=1djplnjpe−κ¯γ∑p=1djplnjp+Cκ,d,sγCSup−γλγ1−θ. ≤ _j _+^d 2e^- κγ _p=1^dj_p j_pe^- κγ _p=1^dj_p j_p+C_κ,d,s^γC_Sup^-γλ γ1-θ. By Lemma C.3, let M~≥d M≥ d satisfy Cκ,d,sγCSup−γλγ1−θ=(M~/d)−κ¯γM~.C_κ,d,s^γC_Sup^-γλ γ1-θ= ( M/d )^- κγ M. Then d⁡(λ)≤2(κ¯−1γ−1+3/2)d(eM~/d)d.d(λ)≤ 2( κ^-1γ^-1+3/2)^d (e M/d )^d. Consequently, (B.4) λ=Cκ,d,sθ−1CSup1−θΥ[e−1(κ¯−1γ−1+3/2)−1(M/2)1/d]−(1−θ)κ¯dλ=C_κ,d,s^θ-1C_Sup^1-θ [e^-1( κ^-1γ^-1+3/2)^-1(M/2)^1/d ]^-(1-θ) κd guarantees d⁡(λ)≤Md(λ)≤ M. Case (4): bandlimited features. Scaling reduces the problem to (B.1) on (−1,1)d(-1,1)^d with kernel k~η(x)=(2S)−d∫(−SR,SR)deıw⊤xw. k_η(x)=(2S)^-d _(-SR,SR)^de w xdw. The comparison operator TBanT_Ban has the same kernel. As in [78], let λj(γ) _j(γ) be the eigenvalues of the one-dimensional operators on (−1,1)(-1,1) with kernel (2π)−1∫(−γ,γ)eiwxw=sin⁡(γx)πx.(2π)^-1 _(-γ,γ)e^iwxdw= (γ x)π x. The eigenvalues of TBanT_Ban are [5] πdS−d∏p=1dλjp(SR),j1,j2,…,jd∈ℕ+.π^dS^-d _p=1^d _j_p(SR), j_1,j_2,…,j_d _+. For fixed SRSR, [78, Corollary 2] gives limj→∞ln⁡λj(SR)jln⁡j=−2. _j→∞ _j(SR)j j=-2. Thus, for every 0<κ¯<20< κ<2, there exists CBanC_Ban such that λj(SR)≤CBan1/de−κ¯jln⁡j _j(SR)≤ C_Ban^1/de^- κj j for all j∈ℕ+j _+. By (B.3), d⁡(λ,θ,γ) d(λ;θ,γ) ≤∑j∈ℕ+d2(π/S)dγCBanγe−κ¯γ∑p=1djplnjp(π/S)dγCBanγe−κ¯γ∑p=1djplnjp+λγ1−θ ≤ _j _+^d 2(π/S)^dγC_Ban^γe^- κγ _p=1^dj_p j_p(π/S)^dγC_Ban^γe^- κγ _p=1^dj_p j_p+λ γ1-θ ≤∑j∈ℕ+d2e−κ¯γ∑p=1djplnjpe−κ¯γ∑p=1djplnjp+(S/π)dγCBan−γλγ1−θ. ≤ _j _+^d 2e^- κγ _p=1^dj_p j_pe^- κγ _p=1^dj_p j_p+(S/π)^dγC_Ban^-γλ γ1-θ. Let M~≥d M≥ d satisfy (S/π)dγCBan−γλγ1−θ=(M~/d)−κ¯γM~.(S/π)^dγC_Ban^-γλ γ1-θ= ( M/d )^- κγ M. Lemma C.3 gives d⁡(λ)≤2(κ¯−1γ−1+3/2)d(eM~/d)d.d(λ)≤ 2( κ^-1γ^-1+3/2)^d(e M/d)^d. Therefore, λ=(π/S)(1−θ)dCBan1−θΥ[e−1(κ¯−1γ−1+3/2)−1(M/2)1/d]−(1−θ)κ¯dλ=(π/S)^(1-θ)dC_Ban^1-θ [e^-1( κ^-1γ^-1+3/2)^-1(M/2)^1/d ]^-(1-θ) κd guarantees d⁡(λ)≤Md(λ)≤ M, which completes the proof. ∎ The effective-dimension bounds determine admissible penalty scales. To apply the abstract estimate, it remains to place the target classes in the source interpolation spaces and to embed the error interpolation spaces into the norms appearing in Theorem 3.2. B.2. Fourier descriptions and interpolation-space embeddings This subsection provides the two deterministic space identifications needed by the uniform approximation theorem. We first recall the whole-space Fourier description of translation-invariant RKHSs and the corresponding weighted L2L^2 interpolation identity. These facts yield the embedding of the weighted Fourier target classes into the kernel interpolation scale. We then identify or embed that scale into the Sobolev norms used to measure the approximation error. The subsection closes by connecting the weighted Fourier assumptions to the spatial Gevrey and analytic conditions in Assumption 3.5. Whole-space Fourier descriptions. Let w be a positive measurable weight function. Define weighted space Lw2(ℝd)L^2_w(R^d) as the space of all measurable functions for which ‖f‖Lw2(ℝd)=‖wf‖L2(ℝd)<∞\|f\|_L^2_w(R^d)=\|wf\|_L^2(R^d)<∞. The following proposition shows that the RKHS associated with certain translation invariant kernels on ℝdR^d may be characterized as weighted L2L^2 spaces in Fourier space. Proposition B.3 ([76, Theorem 10.12]). Suppose that k∈C⁡(ℝd)∩L1(ℝd)k∈ C(R^d)∩ L^1(R^d) is a real-valued positive definite function. Define :=f∈L2(ℝd)∩C⁡(ℝd):f^/k^∈L2(ℝd)G:= \f∈ L^2(R^d)∩ C(R^d): f/ k∈ L^2(R^d) \ and equip this space with the bilinear form ⟨f,g⟩:=(2π)−d/2⟨f^/k^,g^/k^⟩L2(ℝd)=(2π)−d/2∫ℝdf^(w)g^(w)¯k^(w)dw f,g _G:=(2π)^-d/2 f/ k, g/ k _L^2(R^d)=(2π)^-d/2 _R^d f(w) g(w) k(w)dw . Then G is a real Hilbert space with inner product ⟨⋅,⋅⟩ ·,· _G and reproducing kernel k(⋅−⋅)k(·-·). Hence G is the RKHS associated with k on ℝdR^d, i.e., =ℋk(ℝd)G=H_k(R^d), and both inner products coincide. In particular, every f∈ℋk(ℝd)f _k(R^d) can be recovered from its Fourier transform f^∈L1(ℝd)∩L2(ℝd) f∈ L^1(R^d)∩ L^2(R^d). Proposition B.4 (Bandlimited RKHS characterization). Let QS=(−S,S)dQ_S=(-S,S)^d, and let kSk_S be defined by kS^=(2π)−d/2bS1QS,S,bS>0. k_S=(2π)^-d/2b_S1_Q_S, S,b_S>0. Then ℋkS(ℝd)=PWS:=F∈L2(ℝd):suppF^⊂QS¯,∥F∥ℋkS(ℝd)=bS−1/2∥F∥L2(ℝd).H_k_S(R^d)=PW_S:=\F∈ L^2(R^d):supp F⊂ Q_S\, \|F\|_H_k_S(R^d)=b_S^-1/2\|F\|_L^2(R^d). Proof. Equip PWSPW_S with the inner product ⟨F,G⟩PWS=bS−1⟨F,G⟩L2 F,G _PW_S=b_S^-1 F,G _L^2. Since F^∈L1(QS) F∈ L^1(Q_S), Fourier inversion and Plancherel’s identity give, for every F∈PWSF∈ PW_S, ⟨F,kS(⋅−x)⟩PWS=(2π)−d/2∫QSF^(w)eıw⊤xdw=F(x). F,k_S(·-x) _PW_S=(2π)^-d/2 _Q_S F(w)e w xdw=F(x). Thus PWSPW_S is an RKHS with reproducing kernel kS(⋅−⋅)k_S(·-·). The uniqueness of the RKHS proves the claim. ∎ We recall a result from [60] stating the interpolation relationship between weighted L2L^2 spaces. Proposition B.5. Let w1w_1, w2w_2 be positive measurable functions. Then, for 0<θ<10<θ<1, (Lw12(ℝd),Lw22(ℝd))θ,2=Lw2(ℝd),w=w11−θw2θ.(L^2_w_1(R^d),L^2_w_2(R^d))_θ,2=L^2_w(R^d), w=w_1^1-θw_2^θ. We recall extension and restriction theorems for RKHSs associated with the same kernel. Proposition B.6 ([76, Theorem 10.46 and Theorem 10.47]). Let Ω1⊆Ω2⊆ℝd _1 _2 ^d and k be a positive definite kernel on Ω2 _2. Then, (1) Each function f∈ℋk(Ω1)f _k( _1) has a natural extension to a function Ef∈ℋk(Ω2)Ef _k( _2). Furthermore, ‖Ef‖ℋk(Ω2)=‖f‖ℋk(Ω1)\|Ef\|_H_k( _2)=\|f\|_H_k( _1). (2) The restriction f|Ω1f|_ _1 of any function f∈ℋk(Ω2)f _k( _2) is contained in ℋk(Ω1)H_k( _1) with ‖f|Ω1‖ℋk(Ω1)≤‖f‖ℋk(Ω2)\|f|_ _1\|_H_k( _1)≤\|f\|_H_k( _2). Target classes in the kernel interpolation scale. Proposition B.7 (Fourier source classes in the kernel interpolation scale). Let R>0R>0, x0∈ℝdx_0 ^d, QR=x0+(−R,R)dQ_R=x_0+(-R,R)^d, a>0a>0, 0<κ≤κ¯0<κ≤ κ, and σ=κ/κ¯σ=κ/ κ. Let kκ¯,ak_ κ,a be the kernel induced by dτκ¯,a(w)∝e−2κ¯|w|adw.d _ κ,a(w) e^-2 κ|w|^adw. Then ℱκ,a(QR)↪ℋkκ¯,aσ(QR),∥u∥ℋkκ¯,aσ(QR)≲κ,κ¯,d,a∥u∥κ,a.F_κ,a(Q_R) _k_ κ,a^σ(Q_R), \|u\|_H_k_ κ,a^σ(Q_R) _κ, κ,d,a\|u\|_κ,a. Proof. Let ℛQRR_Q_R denote restriction from ℝdR^d to QRQ_R. By Proposition B.3, the whole-space RKHS of kκ¯,ak_ κ,a has Fourier norm equivalent to ‖eκ¯|⋅|aU^‖L2(ℝd). \|e κ|·|^a U \|_L^2(R^d). If 0<σ<10<σ<1, the weighted L2L^2 interpolation identity above gives (L2(ℝd),ℋkκ¯,a(ℝd))σ,2=U:eκ|⋅|aU^∈L2(ℝd), (L^2(R^d),H_k_ κ,a(R^d) )_σ,2= \U:e^κ|·|^a U∈ L^2(R^d) \, with equivalent norms. The map ℛQRR_Q_R is contractive from L2(ℝd)L^2(R^d) to L2(QR)L^2(Q_R) and, by Proposition B.6, from ℋkκ¯,a(ℝd)H_k_ κ,a(R^d) to ℋkκ¯,a(QR)H_k_ κ,a(Q_R). Interpolating these two restriction estimates and using Proposition 2.1 yields ∥ℛQRU∥ℋkκ¯,aσ(QR)≲κ,κ¯,d,a‖eκ|⋅|aU^‖L2(ℝd).\|R_Q_RU\|_H_k_ κ,a^σ(Q_R) _κ, κ,d,a \|e^κ|·|^a U \|_L^2(R^d). Taking the infimum over all admissible whole-space extensions U of u proves the claim when 0<σ<10<σ<1. If σ=1σ=1, then κ=κ¯κ= κ and ℋkκ¯,aσ=ℋkκ¯,aH_k_ κ,a^σ=H_k_ κ,a. The Fourier characterization and the contractive restriction in Proposition B.6 give ∥ℛQRU∥ℋkκ¯,a1(QR)≲κ¯,d,a‖eκ¯|⋅|aU^‖L2(ℝd).\|R_Q_RU\|_H_k_ κ,a^1(Q_R) _ κ,d,a \|e κ|·|^a U \|_L^2(R^d). Taking the infimum over admissible extensions proves the endpoint and completes the proof. ∎ Kernel interpolation spaces and error norms. The following proposition relates kernel interpolation spaces to Sobolev spaces on bounded domains. Proposition B.8. (1) Suppose k∈L1(ℝd)k∈ L^1(R^d) and k^≃(1+|⋅|2)−s k (1+|·|^2)^-s with s>d/2s>d/2. Then, for 0≤ν≤s0≤ν≤ s, ℋkν/s(Ω)=Hν(Ω)H_k^ν/s( )=H^ν( ) with ∥⋅∥ℋkν/s(Ω)≃d,s,Ω∥⋅∥Hν(Ω)\|·\|_H_k^ν/s( ) _d,s, \|·\|_H^ν( ). (2) Suppose k∈L1(ℝd)k∈ L^1(R^d) and k^≃e−2κ|⋅|s k e^-2κ|·|^s with κ,s>0κ,s>0. Let t≥0t≥ 0, 1≤p≤∞1≤ p≤∞, and 0<θ≤10<θ≤ 1. Fix ℓ≥t ≥ t if p=2p=2, and fix any ℓ>t+d/2 >t+d/2 otherwise. Then every f∈ℋkθ(Ω)f _k^θ( ) is smooth and ∥f∥Wt,p(Ω)≲d,κ,s,t,p,ℓ,θ,Ω∥f∥ℋkθ(Ω).\|f\|_W^t,p( ) _d,κ,s,t,p, ,θ, \|f\|_H_k^θ( ). (3) Let k=kSk=k_S be the bandlimited kernel in Proposition B.4. Let t,p,θt,p,θ, and ℓ be as in (2). Then every f∈ℋkθ(Ω)f _k^θ( ) is smooth and ∥f∥Wt,p(Ω)≲d,t,p,ℓ,θ,ΩbSθ/2(1+dS2)ℓ/2∥f∥ℋkθ(Ω).\|f\|_W^t,p( ) _d,t,p, ,θ, b_S^θ/2(1+dS^2) /2\|f\|_H_k^θ( ). Proof. (1) The case ν=0ν=0 is immediate. The case ν=sν=s follows as in [76, Corollary 10.48]. We extend the argument to fractional Sobolev spaces. By Proposition B.6 and Proposition B.3, every f∈ℋk(Ω)f _k( ) has an extension Ef∈ℋk(ℝd)=Hs(ℝd)Ef _k(R^d)=H^s(R^d) and (B.5) ∥f∥Hs(Ω)≤∥Ef∥Hs(ℝd)≲d,s∥Ef∥ℋk(ℝd)≲d,s∥f∥ℋk(Ω).\|f\|_H^s( )≤\|Ef\|_H^s(R^d) _d,s\|Ef\|_H_k(R^d) _d,s\|f\|_H_k( ). On the other hand, by [67], every f∈Hs(Ω)f∈ H^s( ) has an extension E~f∈Hs(ℝd)=ℋk(ℝd) Ef∈ H^s(R^d)=H_k(R^d) satisfying ∥E~f∥Hs(ℝd)≲d,s,Ω∥f∥Hs(Ω)\| Ef\|_H^s(R^d) _d,s, \|f\|_H^s( ). Thus, E~f∈ℋk(ℝd) Ef _k(R^d) and (B.6) ∥f∥ℋk(Ω)≤∥E~f∥ℋk(ℝd)≲d,s∥E~f∥Hs(ℝd)≲d,s,Ω∥f∥Hs(Ω).\|f\|_H_k( )≤\| Ef\|_H_k(R^d) _d,s\| Ef\|_H^s(R^d) _d,s, \|f\|_H^s( ). For 0<ν<s0<ν<s, Proposition 2.1 gives ℋkν/s(Ω)=(L2(Ω),ℋk(Ω))ν/s,2.H^ν/s_k( )=(L^2( ),H_k( ))_ν/s,2. Moreover, Hν(Ω)=(L2(Ω),Hs(Ω))ν/s,2H^ν( )=(L^2( ),H^s( ))_ν/s,2 with equivalent norms. The real interpolation theorem for bounded linear operators, together with (B.5) and (B.6), yields the desired estimate. (2) Fix t,p,θt,p,θ, and ℓ as in the statement. Propositions B.6 and B.3 give, for every f∈ℋk(Ω)f _k( ), ∥f∥Hℓ/θ(Ω)≲d,κ,s,ℓ,θ∥f∥ℋk(Ω),\|f\|_H /θ( ) _d,κ,s, ,θ\|f\|_H_k( ), because the exponential Fourier weight dominates (1+|⋅|2)ℓ/(2θ)(1+|·|^2) /(2θ). For 0<θ<10<θ<1, Proposition 2.1, the identity Hℓ=(L2,Hℓ/θ)θ,2H =(L^2,H /θ)_θ,2 on Ω , and the real interpolation theorem imply ∥f∥Hℓ(Ω)≲d,κ,s,ℓ,θ,Ω∥f∥ℋkθ(Ω).\|f\|_H ( ) _d,κ,s, ,θ, \|f\|_H_k^θ( ). The same estimate follows directly from the endpoint bound when θ=1θ=1. Finally, Hℓ(Ω)↪Wt,p(Ω)H ( ) W^t,p( ) by the choice of ℓ . Since t is arbitrary, every f∈ℋkθ(Ω)f _k^θ( ) is smooth. This proves (2). (3) The argument is the same, but Proposition B.4 gives ‖Ef‖L2(ℝd)=bS1/2‖Ef‖ℋk(ℝd)\|Ef\|_L^2(R^d)=b_S^1/2\|Ef\|_H_k(R^d) for the minimum-norm bandlimited extension EfEf. Hence ‖f‖Hℓ/θ(Ω)≤bS1/2(1+dS2)ℓ/(2θ)‖f‖ℋk(Ω).\|f\|_H /θ( )≤ b_S^1/2(1+dS^2) /(2θ)\|f\|_H_k( ). Interpolating as in (2) yields ∥f∥Hℓ(Ω)≲d,ℓ,θ,ΩbSθ/2(1+dS2)ℓ/2∥f∥ℋkθ(Ω).\|f\|_H ( ) _d, ,θ, b_S^θ/2(1+dS^2) /2\|f\|_H_k^θ( ). The Sobolev embedding Hℓ(Ω)↪Wt,p(Ω)H ( ) W^t,p( ) proves (3), including smoothness, and completes the proof. ∎ Spatial regularity and Fourier decay. We finally verify the implications used to interpret the Fourier source conditions in terms of standard smoothness classes. Proof of Lemma 3.6. Suppose first that Assumption 3.5(b) holds, and let u~∈Gs(Ω′) u∈ G^s( ) be an extension of u. Choose χ∈G0s(Ω′)χ∈ G_0^s( ) such that χ=1χ=1 on a neighborhood of Ω¯ , and extend U:=χu~U:=χ u by zero to ℝdR^d. Then U∈G0s(ℝd)U∈ G_0^s(R^d) and U|Ω=uU|_ =u. By the Fourier characterization of compactly supported Gevrey functions [64, Theorem 1.6.1], there exist C,c>0C,c>0 such that |U^(w)|≤Cexp⁡(−c|w|1/s),w∈ℝd.| U(w)|≤ C (-c|w|^1/s), w ^d. Consequently, for every 0<κ<c0<κ<c, eκ|⋅|1/sU^∈L2(ℝd)e^κ|·|^1/s U∈ L^2(R^d), and hence ‖u‖κ,1/s<∞\|u\|_κ,1/s<∞. If Assumption 3.5(c) holds, the Paley–Wiener type result [63, Theorem IX.13] gives eκ|⋅|u^∈L2(ℝd)for every 0<κ<ρ.e^κ|·| u∈ L^2(R^d) every 0<κ<ρ. Taking U=uU=u in the definition of ‖u‖κ,1\|u\|_κ,1 proves ‖u‖κ,1<∞\|u\|_κ,1<∞ and completes the proof. ∎ B.3. Proof of the uniform approximation theorem Proof of Theorem 3.2. We first prove a probabilistic implication which will be used repeatedly. Fix ϱ∈ph,cx ∈\ph,cx\ and 0≤θ<10≤θ<1, set γ=1−θγ=1-θ, and assume that the chosen value of λ satisfies (B.7) d⁡(λ,θ,γ)≤M.d(λ;θ,γ)≤ M. Both feature representations induce the same kernel integral operator Σ and hence the same effective dimension d⁡(λ,θ,γ)d(λ;θ,γ). By Definition 2.2 and (2.6), the optimal density qλ,ϱ∗=qλ,ϱ∗(⋅,θ,γ)q^*_λ, =q^*_λ, (·;θ,γ) associated with the chosen representation satisfies dmax(qλ,ϱ∗,λ,θ,γ)=d⁡(λ,θ,γ)≤Md_ (q^*_λ, ,λ;θ,γ)=d(λ;θ,γ)≤ M. Since M≥eδ/14M≥ eδ/14, one has 14M/δ≥e14M/δ≥ e and therefore ln⁡(14M/δ)≥1 (14M/δ)≥ 1. Moreover, (B.7) implies ln⁡14d(λ,θ,γ)δ≤ln⁡14Mδ. 14d(λ;θ,γ)δ≤ 14Mδ. Consequently, N N ≥3Mln⁡(14M/δ) ≥ 3M (14M/δ) ≥3dmax(qλ,ϱ∗,λ,θ,γ)max⁡ln⁡14d(λ,θ,γ)δ,1. ≥ 3d_ (q^*_λ, ,λ;θ,γ) \ 14d(λ;θ,γ)δ,1 \. Thus the sufficient sampling condition (2.7) holds at this value of λ. By the definition of the critical penalty ςN(δ,qλ,ϱ∗,θ,γ) _N(δ,q^*_λ, ,θ,γ), this gives (B.8) ςN(δ,qλ,ϱ∗,θ,1−θ)≤λ. _N(δ,q^*_λ, ,θ,1-θ)≤λ. The event supplied by Theorem 2.3 has probability at least 1−δ1-δ, depends only on the sampled features, and is uniform over the unit ball of ℋkσH_k^σ. On this event, let f∈ℋkσf _k^σ, θ≤σ≤1θ≤σ≤ 1, and let ζ satisfy 0≤ζ≤θ0≤ζ≤θ and 2θ−1≤ζ2θ-1≤ζ. Then p¯=max⁡ζ,2θ−1=ζ p= \ζ,2θ-1\=ζ in Theorem 2.3(1). Combining that theorem with (B.8) and using homogeneity gives, simultaneously for all f∈ℋkσf _k^σ, (B.9) ‖f−Φϱ∗‖ℋkζ \|f- _ β^*\|_H_k^ζ ≤16λσ−ζ2(1−θ)‖f‖ℋkσ, ≤ 16λ σ-ζ2(1-θ)\|f\|_H_k^σ, |∗| | β^*| ≤16N−1/2λσ−12(1−θ)∥f∥ℋkσ. ≤ 16N^-1/2λ σ-12(1-θ)\|f\|_H_k^σ. The RF function produced by ∗ β^* has the representation-independent form Φϱ∗(x)=∑j=1Nβj∗qλ,ϱ∗(vjϱ)−1/2ϕϱ(x,vjϱ). _ β^*(x)= _j=1^N _j^*q^*_λ, (v_j )^-1/2 _ (x,v_j ). Set αjϱ=qλ,ϱ∗(vjϱ)−1/2βj∗ _j =q^*_λ, (v_j )^-1/2 _j^*, 1≤j≤N1≤ j≤ N. Therefore (B.10) |αϱ|ℓ2(qλ,ϱ∗)2=∑j=1Nqλ,ϱ∗(vjϱ)|αjϱ|2=∑j=1N|βj∗|2=|∗|2.|α |_ ^2(q^*_λ, )^2= _j=1^Nq^*_λ, (v_j )| _j |^2= _j=1^N| _j^*|^2=| β^*|^2. For the complex-exponential representation and a real-valued target, taking the real part gives (3.3). Since the real-part map is contractive and |αjcx|2=|aj|2+|bj|2| _j^cx|^2=|a_j|^2+|b_j|^2, both estimates in (B.9) and the coefficient identity above remain valid for this real cosine–sine realization. We now prove the four cases. For a fixed target u and representation ϱ , abbreviate uNϱu_N and αϱ(u)α (u) by uNu_N and α, respectively. Proof of (1). For dτ≃(1+|w|2)−s¯dwdτ (1+|w|^2)^- sdw, the kernel in (3.2) satisfies k^≂(1+|⋅|2)−s¯ k (1+|·|^2)^- s. Put θ=νs¯,γ=1−νs¯,σ=s¯,ζ=ts¯.θ= ν s, γ=1- ν s, σ= s s, ζ= t s. The assumptions imply 0≤θ≤σ≤10≤θ≤σ≤ 1, 0≤ζ≤θ0≤ζ≤θ, 2θ−1≤ζ2θ-1≤ζ, and s¯(1−θ)=s¯−ν>d/2 s(1-θ)= s-ν>d/2. Proposition B.2(1) therefore gives (B.7) for λ=c1M−2(s¯−ν)/dλ=c_1M^-2( s-ν)/d, after the fixed factor involving |Ω|| | is absorbed into c1c_1. By Proposition B.8(1), ∥f∥ℋkr/s¯(Ω)≃d,s¯,r,Ω∥f∥Hr(Ω),0≤r≤s¯.\|f\|_H_k^r/ s( ) _d, s,r, \|f\|_H^r( ), 0≤ r≤ s. Applying (B.9) and this equivalence at r=sr=s and r=tr=t yields ∥u−uN∥Ht(Ω)≲d,s¯,s,ν,t,ΩM−(s−t)/d∥u∥Hs(Ω).\|u-u_N\|_H^t( ) _d, s,s,ν,t, M^-(s-t)/d\|u\|_H^s( ). Similarly, (B.10) and the coefficient estimate in (B.9) give |α|ℓ2(qλ,ϱ∗)≲d,s¯,s,ν,ΩN−1/2M(s¯−s)/d∥u∥Hs(Ω).|α|_ ^2(q^*_λ, ) _d, s,s,ν, N^-1/2M^( s-s)/d\|u\|_H^s( ). Taking the supremum over Hs(Ω)B_H^s( ) proves (1). Common preparation for (2)–(4). Since Ω⊂Ω~ ⊂ , (B.11) ‖g‖Wt,p(Ω)≤‖g‖Wt,p(Ω~),t≥0,1≤p≤∞.\|g\|_W^t,p( )≤\|g\|_W^t,p( ), t≥ 0, 1≤ p≤∞. Translation invariance shows that the kernel integral operator on Ω~ is unitarily equivalent to the corresponding operator on (−R,R)d(-R,R)^d. Hence Proposition B.2 applies on Ω~ . For every 0<ζ≤10<ζ≤ 1, Proposition B.8(2) gives, for the exponential kernels in (2) and (3), (B.12) ∥g∥Wt,p(Ω~)≲d,t,p,ζ,R∥g∥ℋkζ(Ω~),t≥0,1≤p≤∞.\|g\|_W^t,p( ) _d,t,p,ζ,R\|g\|_H_k^ζ( ), t≥ 0, 1≤ p≤∞. For the bandlimited kernel in (4), part (3) of the same proposition gives (B.13) ∥g∥Wt,p(Ω~)≲d,t,p,ζ,R(πS)dζ/2(1+dS2)(2t+d+1)/4∥g∥ℋkζ(Ω~).\|g\|_W^t,p( ) _d,t,p,ζ,R ( πS )^dζ/2(1+dS^2)^(2t+d+1)/4\|g\|_H_k^ζ( ). The sampling event, the coefficients, and uNu_N in (B.9) are independent of t and p. Since (B.11)– (B.13) are deterministic, the estimates below hold simultaneously for all t≥0t≥ 0 and 1≤p≤∞1≤ p≤∞. Proof of (2). Put σ=κ/κ¯σ=κ/ κ and set θ=σ2,γ=1−σ2,ζ=σ4.θ= σ2, γ=1- σ2, ζ= σ4. Then 0<ζ≤θ<σ≤10<ζ≤θ<σ≤ 1 and 2θ−1<ζ2θ-1<ζ. Choose an admissible whole-space extension U of u such that ∥eκ|⋅|1/sU^∥L2(ℝd)≤2∥u∥κ,1/s,\|e^κ|·|^1/s U\|_L^2(R^d)≤ 2\|u\|_κ,1/s, and put f:=U|Ω~f:=U|_ . Proposition B.7 gives (B.14) ∥f∥ℋkσ(Ω~)≲κ,κ¯,d,s∥u∥κ,1/s.\|f\|_H_k^σ( ) _κ, κ,d,s\|u\|_κ,1/s. Let b2b_2 be the right-hand side of (B.2) with θ=σ/2θ=σ/2 and decay parameter κ¯ κ, and set aλ:=b2/2a_λ:=b_2/2. Proposition B.2(2) then gives (B.7) for λ=cλexp⁡(−aλM1/(sd))λ=c_λ (-a_λM^1/(sd)) and all sufficiently large M. Applying (B.9) to f, followed by (B.11), (B.12), and (B.14), we obtain ∥u−uN∥Wt,p(Ω)≲κ,κ¯,d,s,t,p,R∥u∥κ,1/sexp(−aeM1/(sd)),\|u-u_N\|_W^t,p( ) _κ, κ,d,s,t,p,R\|u\|_κ,1/s (-a_eM^1/(sd)), where ae:=(σ−ζ)aλ/[2(1−θ)]>0a_e:=(σ-ζ)a_λ/[2(1-θ)]>0. The coefficient estimate and (B.10) similarly give |α|ℓ2(qλ,ϱ∗)≲κ,κ¯,d,s,R∥u∥κ,1/sN−1/2exp(acM1/(sd)),|α|_ ^2(q^*_λ, ) _κ, κ,d,s,R\|u\|_κ,1/sN^-1/2 (a_cM^1/(sd)), where ac:=(1−σ)aλ/[2(1−θ)]≥0a_c:=(1-σ)a_λ/[2(1-θ)]≥ 0. Taking the supremum over ℱκ,1/s(Ω)B_F_κ,1/s( ) proves (2). Proof of (3). Keep the indices σ,θ,γ,ζσ,θ,γ,ζ from (2). Choose an admissible extension U satisfying ∥eκ|⋅|sU^∥L2(ℝd)≤2∥u∥κ,s,\|e^κ|·|^s U\|_L^2(R^d)≤ 2\|u\|_κ,s, and set f:=U|Ω~f:=U|_ . Proposition B.7 implies (B.15) ∥f∥ℋkσ(Ω~)≲κ,κ¯,d,s∥u∥κ,s.\|f\|_H_k^σ( ) _κ, κ,d,s\|u\|_κ,s. Fix ξs:=1−1/s∈(0,2−2/s) _s:=1-1/s∈(0,2-2/s) and put AM:=(M/2)1/de⁡(ξs−1γ−1+3/2).A_M:= (M/2)^1/de( _s^-1γ^-1+3/2). Proposition B.2(3) provides c3>0c_3>0 such that λ0:=c3Υ(AM)−(1−θ)ξsdsatisfiesd⁡(λ0,θ,γ)≤M _0:=c_3 (A_M)^-(1-θ) _sd d( _0;θ,γ)≤ M for all sufficiently large M. Set b3:=2−1/de⁡(ξs−1γ−1+3/2),aλ:=12γξsb3.b_3:= 2^-1/de ( _s^-1γ^-1+3/2 ), a_λ:= 12γ _sb_3. Then AM=b3M1/dA_M=b_3M^1/d and (1−θ)ξsdAMln⁡AM=γξsb3M1/d(ln⁡M+dln⁡b3)≥aλM1/dln⁡M(1-θ) _sdA_M A_M=γ _sb_3M^1/d ( M+d b_3 )≥ a_λM^1/d M for all sufficiently large M. Consequently, λ:=c3exp⁡(−aλM1/dln⁡M)≥λ0λ:=c_3 (-a_λM^1/d M)≥ _0 for all sufficiently large M. The effective dimension is nonincreasing in λ, so (B.7) holds for this value of λ. The same restriction and embedding argument as in (2) yields ∥u−uN∥Wt,p(Ω)≲κ,κ¯,d,s,t,p,R∥u∥κ,sexp(−aeM1/dlnM),\|u-u_N\|_W^t,p( ) _κ, κ,d,s,t,p,R\|u\|_κ,s (-a_eM^1/d M), where ae:=(σ−ζ)aλ/[2(1−θ)]>0a_e:=(σ-ζ)a_λ/[2(1-θ)]>0. Moreover, |α|ℓ2(qλ,ϱ∗)≲κ,κ¯,d,s,R∥u∥κ,sN−1/2exp(acM1/dlnM),|α|_ ^2(q^*_λ, ) _κ, κ,d,s,R\|u\|_κ,sN^-1/2 (a_cM^1/d M), where ac:=(1−σ)aλ/[2(1−θ)]≥0a_c:=(1-σ)a_λ/[2(1-θ)]≥ 0. Taking the supremum over ℱκ,s(Ω)B_F_κ,s( ) proves (3). Proof of (4). Choose U∈L2(ℝd)U∈ L^2(R^d) such that U|Ω=uU|_ =u, supp⁡U^⊂[−S,S]dsupp U⊂[-S,S]^d, and ‖U‖L2(ℝd)≤2‖u‖ℬS(Ω)\|U\|_L^2(R^d)≤ 2\|u\|_B_S( ). Put f:=U|Ω~f:=U|_ . The Fourier characterization of the bandlimited RKHS gives (B.16) ∥f∥ℋk(Ω~)≲d,S∥U∥L2(ℝd).\|f\|_H_k( ) _d,S\|U\|_L^2(R^d). Set θ=γ=1/2θ=γ=1/2, σ=1σ=1, and ζ=1/4ζ=1/4. Fix ξ=1ξ=1 and put AM:=(M/2)1/de⁡(ξ−1γ−1+3/2).A_M:= (M/2)^1/de(ξ^-1γ^-1+3/2). Proposition B.2(4) provides a constant c4>0c_4>0 such that λ0:=c4Υ(AM)−(1−θ)ξd _0:=c_4 (A_M)^-(1-θ)ξ d satisfies d⁡(λ0,θ,γ)≤Md( _0;θ,γ)≤ M for all sufficiently large M. Here AM=b4M1/d,b4:=2−1/de⁡(2+3/2)=21−1/d7e.A_M=b_4M^1/d, b_4:= 2^-1/de(2+3/2)= 2^1-1/d7e. Set aλ:=b4/4=21−1/d/(28e)a_λ:=b_4/4=2^1-1/d/(28e). Since (1−θ)ξdAMln⁡AM=b42M1/d(ln⁡M+dln⁡b4)≥aλM1/dln⁡M(1-θ)ξ dA_M A_M= b_42M^1/d ( M+d b_4 )≥ a_λM^1/d M for all sufficiently large M. Thus λ:=c4exp⁡(−aλM1/dln⁡M)≥λ0λ:=c_4 (-a_λM^1/d M)≥ _0, and (B.7) holds. Using (B.9), (B.11), (B.13), and (B.16), we obtain ∥u−uN∥Wt,p(Ω)≲d,t,p,S,R∥u∥ℬS(Ω)exp(−aeM1/dlnM),ae:=34aλ.\|u-u_N\|_W^t,p( ) _d,t,p,S,R\|u\|_B_S( ) (-a_eM^1/d M), a_e:= 34a_λ. Since σ=1σ=1, the coefficient estimate contains no power of λ: |α|ℓ2(qλ,ϱ∗)≲d,S,R∥u∥ℬS(Ω)N−1/2.|α|_ ^2(q^*_λ, ) _d,S,R\|u\|_B_S( )N^-1/2. Taking the supremum over ℬS(Ω)B_B_S( ) proves (4) and completes the proof. ∎ B.4. Effective dimension for growing uniform supports Lemma B.9 (A non-asymptotic effective-dimension bound for growing bandwidth). Let 0<a<10<a<1 and R,S>0R,S>0, put c=SRc=SR, and define dτS(w)=(2S)−d1QS(w)dwd _S(w)=(2S)^-d1_Q_S(w)dw. Let ΣS _S be the integral operator on L2(QR)L^2(Q_R) generated by the kernel associated with τS _S. There is a constant Ca,d≥1C_a,d≥ 1, independent of S, R, and J, with the following property: for every integer J≥max⁡2c,2J≥ \2c,2\, the parameter λJ,S _J,S defined by (3.4) satisfies d⁡(λJ,S,1−a,a)≤2Jdd( _J,S;1-a,a)≤ 2J^d. Proof. Let μn(c) _n(c), n≥0n≥ 0, be the decreasing eigenvalues of the one-dimensional time-frequency concentration operator (Qcf)(x)=∫−11sin⁡(c⁡(x−y))π⁡(x−y)f(y)y.(Q_cf)(x)= _-1^1 (c(x-y))π(x-y)f(y)dy. If λn(c) _n(c) is the corresponding eigenvalue of the finite Fourier transform, then μn(c)=c2π|λn(c)|2 _n(c)= c2π| _n(c)|^2. This relation is recorded in [57, Equation (9)]. The explicit prolate spheroidal wave-function estimate in [58, Theorem 4], also stated in [56, Theorem 3.20], is |λn(c)|≤πcn(n!)2(2n)!Γ(n+3/2).| _n(c)|≤ π\,c^n(n!)^2(2n)!\, (n+3/2). For n≥1n≥ 1, Γ⁡(n+3/2)=π2∏k=1n(k+12)≥π2n!,(2n)!=n!∏k=1n(n+k)≥(n!)n. (n+3/2)= π2 _k=1^n (k+ 12 )≥ π2n!, (2n)!=n! _k=1^n(n+k)≥(n!)n^n. Consequently, (B.17) |λn(c)|≤2(cn)n,μn(c)≤2cπ(cn)2n.| _n(c)|≤ 2 ( cn )^n, _n(c)≤ 2cπ ( cn )^2n. Let q=c/J≤1/2q=c/J≤ 1/2. From (B.17), for n≥Jn≥ J, μn(c)a≤Ca(1+c)aq2an _n(c)^a≤ C_a(1+c)^aq^2an. Therefore (B.18) TJ:=∑n=J∞μn(c)a≤Ca(1+c)aq2aJ.T_J:= _n=J^∞ _n(c)^a≤ C_a(1+c)^aq^2aJ. Since 0<μn(c)<10< _n(c)<1 and the second term below is controlled by (B.18), (B.19) Ac:=∑n=0∞μn(c)a≤J+TJ≤CaJ.A_c:= _n=0^∞ _n(c)^a≤ J+T_J≤ C_aJ. By the product-kernel construction [5, Theorem 13], ΣS _S is the d-fold tensor product of the corresponding one-dimensional integral operator. Hence, its eigenvalues are Λ=(πS)d∏ℓ=1dμnℓ(c),∈ℕ0d. _ n= ( πS )^d _ =1^d _n_ (c), n _0^d. Let ℐJ=0,…,J−1dI_J=\0,…,J-1\^d. A union bound together with (B.18) and (B.19) gives ∑∉ℐJ∏ℓ=1dμnℓ(c)a≤dTJAcd−1≤Ca,d′Jd−1(1+c)aq2aJ. _ n _J _ =1^d _n_ (c)^a≤ dT_JA_c^d-1≤ C _a,dJ^d-1(1+c)^aq^2aJ. Since x/(x+λ)≤min⁡1,x/λx/(x+λ)≤ \1,x/λ\, d⁡(λJ,S,1−a,a) d( _J,S;1-a,a) =∑∈ℕ0dΛaΛa+λJ,S = _ n _0^d _ n^a _ n^a+ _J,S ≤Jd+(πS)daλJ,S−1∑∉ℐJ∏ℓ=1dμnℓ(c)a≤2Jd. ≤ J^d+ ( πS )^da _J,S^-1 _ n _J _ =1^d _n_ (c)^a≤ 2J^d. Choosing Ca,d≥Ca,d′C_a,d≥ C _a,d in (3.4) completes the proof. ∎ B.5. Proof of the growing-bandwidth leverage estimate Proof of Proposition 3.3. Applying (2.3) with τ=τSτ= _S gives ‖U|QR‖ℋkS(QR)≤(S/π)d/2‖U‖L2(ℝd).\|U|_Q_R\|_H_k_S(Q_R)≤(S/π)^d/2\|U\|_L^2(R^d). Since k^S=(2π)−d/2(π/S)d1(−S,S)d k_S=(2π)^-d/2(π/S)^d1_(-S,S)^d, Proposition B.8(3), applied on QRQ_R with bS=(π/S)db_S=(π/S)^d and then restricted to Ω , using the Sobolev order t+(d+1)/2t+(d+1)/2, gives (B.20) ‖f|Ω‖Wt,p(Ω)≤Cd,t,p,a,R(π/S)d⁡(1−a)/2(1+dS2)(2t+d+1)/4‖f‖ℋkS1−a(QR).\|f|_ \|_W^t,p( )≤ C_d,t,p,a,R(π/S)^d(1-a)/2(1+dS^2)^(2t+d+1)/4\|f\|_H_k_S^1-a(Q_R). Lemma B.9 gives d⁡(λJ,S,1−a,a)≤2Jdd( _J,S;1-a,a)≤ 2J^d. Leverage-score sampling gives dmax(qλJ,S,ϱ∗(⋅,1−a,a),λJ,S,1−a,a)=d⁡(λJ,S,1−a,a)d_ (q^*_ _J,S, (\,·\,;1-a,a), _J,S;1-a,a) =d( _J,S;1-a,a). Hence (3.5) makes λJ,S _J,S admissible in the sense of (2.7); hence the associated critical penalty satisfies ςN≤λJ,S _N≤ _J,S. Applying Theorem 2.3(1) with source index 11 and regression and error indices 1−a1-a, and then using homogeneity, gives ‖U−uN,Sϱ‖ℋkS1−a(QR)≤16λJ,S1/2‖U|QR‖ℋkS(QR).\|U-u_N,S \|_H_k_S^1-a(Q_R)≤ 16 _J,S^1/2\|U|_Q_R\|_H_k_S(Q_R). Combining this estimate with (B.20) and using a+(1−a)=1a+(1-a)=1 cancels all powers (π/S)da/2(π/S)^da/2, (π/S)d⁡(1−a)/2(π/S)^d(1-a)/2, and (S/π)d/2(S/π)^d/2. This proves (3.6). For each fixed ϱ , the sampling event and uN,Sϱu_N,S are independent of t and p, so the estimate holds simultaneously for all the stated error norms. The coefficient bound follows from the coefficient estimate in the same theorem and |αϱ|ℓ2(qλJ,S,ϱ∗(⋅,1−a,a))=|∗||α |_ ^2(q^*_ _J,S, (\,·\,;1-a,a))=| β^*|; the power of λJ,S _J,S is zero because the source index is s=1s=1. This completes the proof. ∎ B.6. Proof of the growing uniform reference measure theorem Proof of Theorem 3.4. Representation-wise sampling event. Fix ϱ∈ph,cx ∈\ph,cx\ throughout the proof. Fix a=1/2a=1/2 in Lemma B.9 and Proposition 3.3. For each case, set S=SJS=S_J. In (1) and (2), SJR/J≤1/4S_JR/J≤ 1/4. In (3), SJRJ≤14J−(s−1)/s(logJ)1/s⟶0. S_JRJ≤ 14J^-(s-1)/s( J)^1/s 0. Thus J≥max⁡2SJR,2J≥ \2S_JR,2\ for all sufficiently large J, and Proposition 3.3 applies. Let JϱA_J be its sampling event. By the uniformity in Theorem 2.3 and homogeneity, JϱA_J depends only on the sampled features, and (3.6) holds on JϱA_J for every V∈L2(ℝd)V∈ L^2(R^d) satisfying supp⁡V^⊂QSJ¯supp V⊂ Q_S_J. In each case, uN,Jϱu_N,J is obtained by applying that proposition to the bandlimited target constructed below. Sobolev targets. Apply [46, Theorem D.1] on Ω with ε=SJ−1 =S_J^-1. Using the fixed construction in its proof, choose a single approximant VJV_J, independent of t and p. For SJ≥1S_J≥ 1, that theorem gives supp⁡V^J⊂BSJ⊂QSJ¯supp V_J⊂ B_S_J⊂ Q_S_J and, with βp:=d(1/p−1/2)+ _p:=d(1/p-1/2)_+, (B.21) ‖u−VJ‖Wt,p(Ω) \|u-V_J\|_W^t,p( ) ≤CSJ−(s−t)‖u‖Ws,p(Ω), ≤ CS_J^-(s-t)\|u\|_W^s,p( ), ‖VJ‖L2(ℝd) \|V_J\|_L^2(R^d) ≤CSJβp‖u‖Ws,p(Ω), ≤ CS_J _p\|u\|_W^s,p( ), for all 1≤p≤∞1≤ p≤∞ such that u∈Ws,p(Ω)u∈ W^s,p( ) and 0≤t≤s0≤ t≤ s. Since SJ=J/(4R∗)S_J=J/(4R_*) and SJR/J≤1/4S_JR/J≤ 1/4, Proposition 3.3 and (B.21) imply ‖u−uN,Jϱ‖Wt,p(Ω) \|u-u_N,J \|_W^t,p( ) ≤‖u−VJ‖Wt,p(Ω)+‖VJ−uN,Jϱ‖Wt,p(Ω) ≤\|u-V_J\|_W^t,p( )+\|V_J-u_N,J \|_W^t,p( ) ≤C‖u‖Ws,p(Ω)[J−(s−t)+Jt+d/2+βp+a/24−aJ]. ≤ C\|u\|_W^s,p( ) [J^-(s-t)+J^t+d/2+ _p+a/24^-aJ ]. The quantity Js+d/2+βp+a/24−aJ^s+d/2+ _p+a/24^-aJ is bounded for J≥1J≥ 1; hence the second term is bounded by a constant times J−(s−t)J^-(s-t). Since u∈Ws,p(Ω)u _W^s,p( ), this proves (1). Fourier-regular targets. Put q=1/sq=1/s in (2) and q=sq=s in (3). By the definition of the quotient norm, choose an extension U∈L2(ℝd)U∈ L^2(R^d), independent of t,pt,p, such that U|Ω=u,∥eκ0|⋅|qU^∥2≤2∥u∥κ0,q.U|_ =u, \|e _0|·|^q U\|_2≤ 2\|u\|_ _0,q. For S>0S>0, define U^S=1QSU U_S=1_Q_S U. With ℓ=t+(d+1)/2 =t+(d+1)/2 and κ=κ0/2κ= _0/2, Sobolev embedding, Plancherel’s identity, and the definition of USU_S give (B.22) ‖u−US‖Wt,p(Ω) \|u-U_S\|_W^t,p( ) ≤C‖U−US‖Hℓ(ℝd) ≤ C\|U-U_S\|_H (R^d) ≤Csupw∉QS(1+|w|2)ℓ/2e−κ0|w|q∥eκ0|⋅|qU^∥2 ≤ C _w∉ Q_S(1+|w|^2) /2e^- _0|w|^q\|e _0|·|^q U\|_2 ≤C‖u‖κ0,qe−κSq. ≤ C\|u\|_ _0,qe^-κ S^q. The last inequality follows because (1+|w|2)ℓ/2e−(κ0−κ)|w|q(1+|w|^2) /2e^-( _0-κ)|w|^q is bounded and |w|≥S|w|≥ S outside QSQ_S. Moreover, ‖US‖L2(ℝd)≤‖U‖L2(ℝd)≤2‖u‖κ0,q.\|U_S\|_L^2(R^d)≤\|U\|_L^2(R^d)≤ 2\|u\|_ _0,q. We apply Proposition 3.3 to USJU_S_J and use ‖u−uN,Jϱ‖Wt,p(Ω)≤‖u−USJ‖Wt,p(Ω)+‖USJ−uN,Jϱ‖Wt,p(Ω).\|u-u_N,J \|_W^t,p( )≤\|u-U_S_J\|_W^t,p( )+\|U_S_J-u_N,J \|_W^t,p( ). In (2), SJ=J/(4R∗)S_J=J/(4R_*). Equation (B.22) and (3.6) give, respectively, C‖u‖κ0,1/se−cJ1/sandC‖u‖κ0,1/sJA4−aJ,C\|u\|_ _0,1/se^-cJ^1/s C\|u\|_ _0,1/sJ^A4^-aJ, for some A=A⁡(d,t,p,a)≥0A=A(d,t,p,a)≥ 0. Since JA4−aJ≤Ce−cJ1/sJ^A4^-aJ≤ Ce^-cJ^1/s for s≥1s≥ 1 and u∈ℱκ0,1/s(Ω)u _F_ _0,1/s( ), assertion (2) follows, including the endpoint s=1s=1. In (3), SJ=(Jlog⁡J)1/s/(4R∗)S_J=(J J)^1/s/(4R_*), and (B.22) is bounded by C‖u‖κ0,se−cJlog⁡JC\|u\|_ _0,se^-cJ J. Furthermore, log⁡(JSJR)≥log⁡4+s−1slogJ−1sloglog⁡J≥s−12slogJ ( JS_JR )≥ 4+ s-1s J- 1s J≥ s-12s J for all sufficiently large J. Therefore, (SJRJ)aJ≤exp⁡(−a⁡(s−1)2sJlog⁡J). ( S_JRJ )^aJ≤ (- a(s-1)2sJ J ). The other factors in (3.6) grow at most algebraically in J and log⁡J J and are absorbed by reducing the exponential constant. Since u∈ℱκ0,s(Ω)u _F_ _0,s( ), this proves (3). The extension U, its truncations, JϱA_J , and uN,Jϱu_N,J are independent of t,pt,p, which proves the stated simultaneity in (2) and (3). Conversion to N. To justify the stated sample-size choice, set L=N/log⁡(N/δ)L=N/ (N/δ) and choose J=⌊c0L1/d⌋J= c_0L^1/d , where c0d≤1/12c_0^d≤ 1/12. For all sufficiently large N, one has log⁡(28Jd/δ)≤2log⁡(N/δ), (28J^d/δ)≤ 2 (N/δ), because Jd≤NJ^d≤ N and N/δ≥28N/δ≥ 28 in this regime, and hence 6Jdlog⁡(28Jd/δ)≤12c0dN≤N.6J^d (28J^d/δ)≤ 12c_0^dN≤ N. Thus (3.5) holds. Also, once c0L1/d≥2c_0L^1/d≥ 2, (c0/2)L1/d≤J≤c0L1/d(c_0/2)L^1/d≤ J≤ c_0L^1/d. Hence J≍L1/dJ L^1/d and log⁡J≍log⁡L J L, and substitution in the three J-rates gives (3.11), which completes the proof. ∎ Appendix C Technical Lemmas We prove the following technical lemma to control the summation series. Lemma C.1. For arbitrary C,λ>0C,λ>0, s>1s>1, it holds ∑j=1∞Cj−sCj−s+λ≤2s−1s−1(C/λ)1/s. _j=1^∞ Cj^-sCj^-s+λ≤ 2s-1s-1(C/λ)^1/s. Proof. Note that Cj−sCj−s+λ≤min⁡(1,Cj−s/λ) Cj^-sCj^-s+λ≤ (1,Cj^-s/λ) . For λ≤Cλ≤ C, a direct calculation yields ∑j=1∞Cj−sCj−s+λ _j=1^∞ Cj^-sCj^-s+λ ≤⌈(C/λ)1/s⌉+Cλ∫(C/λ)1/s∞t−st ≤ (C/λ)^1/s + Cλ _(C/λ)^1/s^∞t^-sdt =⌈(C/λ)1/s⌉+1s−1(C/λ)1/s = (C/λ)^1/s + 1s-1(C/λ)^1/s ≤2s−1s−1(C/λ)1/s. ≤ 2s-1s-1(C/λ)^1/s. For λ>Cλ>C, ∑j=1∞Cj−sCj−s+λ _j=1^∞ Cj^-sCj^-s+λ ≤Cλ∑j=1∞j−s≤sC(s−1)λ, ≤ Cλ _j=1^∞j^-s≤ sC(s-1)λ, which completes the proof. ∎ We prove the following technical lemma to control the summation series. Lemma C.2. For any κ~>0 κ>0, s≥1s≥ 1 and 0<λ≤e−max⁡(κ~,1)0<λ≤ e^- ( κ,1), it holds ∑j∈ℕ+de−κ~|j|11/se−κ~|j|11/s+λ _j _+^d e^- κ|j|_1^1/se^- κ|j|_1^1/s+λ ≤(2+1d=1)[sdκ~−1ln(1/λ)]sd. ≤(2+1_\d=1\) [sd κ^-1 (1/λ) ]^sd. Proof. First, we denote r=κ~−slns⁡(1/λ)≥1r= κ^-s ^s(1/λ)≥ 1 and divide the summation into two parts I=∑|j|1≤r+1e−κ~|j|11/se−κ~|j|11/s+λ,I=∑|j|1>r+1e−κ~|j|11/se−κ~|j|11/s+λ. = _|j|_1≤ r+1 e^- κ|j|_1^1/se^- κ|j|_1^1/s+λ, = _|j|_1>r+1 e^- κ|j|_1^1/se^- κ|j|_1^1/s+λ. Since each summand is less than 11, we have (C.1) I≤(⌊r⌋+1d)≤(1+1d≤2)Γ(d+1)−1rd.I≤ pmatrix r +1\\ d pmatrix≤(1+1_\d≤ 2\) (d+1)^-1r^d. To bound II, note that the number of j∈ℕ+dj _+^d for which |j|1=T|j|_1=T is (T−1d−1)≤Γ(d)−1(T−1)d−1. pmatrixT-1\\ d-1 pmatrix≤ (d)^-1(T-1)^d-1. Then, with the above estimate, II is bounded by λ−1∑T=⌊r⌋+2∞∑|j|1=Te−κ~|j|11/s≤λ−1Γ(d)−1∑T=⌊r⌋+2∞Td−1e−κ~T1/s. λ^-1 _T= r +2^∞ _|j|_1=Te^- κ|j|_1^1/s≤λ^-1 (d)^-1 _T= r +2^∞T^d-1e^- κT^1/s. Denote h⁡(T):=Td−1e−κ~T1/sh(T):=T^d-1e^- κT^1/s for T>0T>0. We shall use the integral of h to control the above summation. For d=1d=1, since h⁡(T)h(T) is a positive decreasing function of T, (C.2) ∑T=⌊r⌋+2∞h⁡(T) _T= r +2^∞h(T) ≤∫r∞h⁡(T)dT. ≤ _r^∞h(T)dT. For d≥2d≥ 2, as T increases, h⁡(T)h(T) increases and then decreases, attaining its maximum at T∗=[s⁡(d−1)/κ~]sT^*=[s(d-1)/ κ]^s. If κ~≥s⁡(d−1) κ≥ s(d-1), then T∗≤1T^*≤ 1 and (C.2) holds. Otherwise, κ~<s⁡(d−1) κ<s(d-1), h⁡(T)≤∫T+1h⁡(t)th(T)≤ _T^T+1h(t)dt for T≤T∗−1T≤ T^*-1, and h⁡(T)≤∫T−1Th⁡(t)th(T)≤ _T-1^Th(t)dt for T≥T∗+1T≥ T^*+1. There are one or two integers in (T∗−1,T∗+1)(T^*-1,T^*+1). If there is one, its function value does not exceed h⁡(T∗)h(T^*). If there are two, denoted by T1<T2T_1<T_2, then min(h(T1),h(T2))≤∫T1T2h(t)dt,max(h(T1),h(T2))≤h(T∗) (h(T_1),h(T_2))≤ _T_1^T_2h(t)dt, (h(T_1),h(T_2))≤ h(T^*) . Therefore, (C.3) ∑T=⌊r⌋+2∞h⁡(T) _T= r +2^∞h(T) ≤∫r∞h(T)dT+h(T∗)1⌊r⌋+1≤T∗. ≤ _r^∞h(T)dT+h(T^*)1_\ r +1≤ T^*\. The second term on the right-hand side above vanishes unless r<T∗r<T^*. To control it with the first term, we employ the concavity of h. In fact, h′(T)=[(κ~sT1/s)2−(2d−3+1s)κ~sT1/s+(d−1)(d−2)]Td−3e−κ~T1/s, h (T)= [ ( κsT^1/s )^2- (2d-3+ 1s ) κsT^1/s+(d-1)(d-2) ]T^d-3e^- κT^1/s, and h⁡(T)h(T) is concave on [T∗,Tc][T^*,T_c], where TcT_c satisfies κ~sTc1/s κsT_c^1/s =12[(2d−3+1s)+(2d−3+1s)2−4(d−1)(d−2)] = 12 [ (2d-3+ 1s )+ (2d-3+ 1s )^2-4(d-1)(d-2) ] ≥d−1+1s. ≥ d-1+ 1s. Denote Ta=(s/κ~)s(d−1+1/s)sT_a=(s/ κ)^s(d-1+1/s)^s with Ta∈(T∗,Tc]T_a∈(T^*,T_c]. Since s≥1s≥ 1 and κ~<s⁡(d−1) κ<s(d-1), the length of [T∗,Ta][T^*,T_a] is at least (sκ~)s[(d−1+1s)s−(d−1)s] ( s κ )^s [ (d-1+ 1s )^s-(d-1)^s ] ≥(sκ~)s(d−1)s−1≥sκ~, ≥ ( s κ )^s(d-1)^s-1≥ s κ, and h⁡(Ta)≥h⁡(T∗)/eh(T_a)≥ h(T^*)/e. Then, the concavity of h on [T∗,Tc][T^*,T_c] ensures 12(Ta−T∗)(h⁡(T∗)+h⁡(Ta)) 12(T_a-T^*) (h(T^*)+h(T_a) ) ≤∫T∗Tah⁡(T)dT, ≤ _T^*^T_ah(T)dT, which gives that for r≤T∗r≤ T^*, (C.4) h⁡(T∗) h(T^*) ≤2eκ~(e+1)s∫T∗Tah⁡(T)T ≤ 2e κ(e+1)s _T^*^T_ah(T)dT ≤2eκ~(e+1)s∫r∞h⁡(T)dT. ≤ 2e κ(e+1)s _r^∞h(T)dT. It remains to estimate the integral of h. For a≥1a≥ 1, the substitution t=u+at=u+a gives ∫a∞tb−1e−tt _a^∞t^b-1e^-tdt ≤e−a∫0∞[ab−1+(b−1)ab−2u]e−uu ≤ e^-a _0^∞ [a^b-1+(b-1)a^b-2u ]e^-udu ≤be−aab−1, ≤ be^-aa^b-1, 1≤b≤2, 1≤ b≤ 2, ∫a∞tb−1e−tt _a^∞t^b-1e^-tdt ≤2b−2e−a∫0∞(ub−1+ab−1)e−uu ≤ 2^b-2e^-a _0^∞ (u^b-1+a^b-1 )e^-udu ≤2b−2e−a(Γ⁡(b)+1)ab−1, ≤ 2^b-2e^-a( (b)+1)a^b-1, b≥2. b≥ 2. With the above facts and the variable substitution t=κ~T1/st= κT^1/s, we obtain (C.5) ∫r∞h⁡(T)T _r^∞h(T)dT ≤sκ~−sd∫κ~r1/s∞tsd−1e−tdt, ≤ s κ^-sd _ κr^1/s^∞t^sd-1e^-tdt, ≤[s1sd<2+2sd−2(Γ(sd)+1)1sd≥2]sλκ~−1rd−1/s, ≤[s1_\sd<2\+2^sd-2( (sd)+1)1_\sd≥ 2\]sλ κ^-1r^d-1/s, where κ~r1/s=ln⁡(1/λ)≥1 κr^1/s= (1/λ)≥ 1. Plugging this into (C.2) yields for d=1d=1, I ≤[s1s<2+2s−2(Γ(s)+1)1s≥2]sr, ≤[s1_\s<2\+2^s-2( (s)+1)1_\s≥ 2\]sr, and then a combination with (C.1) gives ∑j∈ℕ+de−κ~|j|11/se−κ~|j|11/s+λ _j _+^d e^- κ|j|_1^1/se^- κ|j|_1^1/s+λ ≤[2+s21s<2+2s−2s(Γ(s)+1)1s≥2]r≤3ssr, ≤[2+s^21_\s<2\+2^s-2s( (s)+1)1_\s≥ 2\]r≤ 3s^sr, where we used elementary facts 2+s2≤3s2+s^2≤ 3s^s and for s≥2s≥ 2, 2s−2s(Γ⁡(s)+1)+2 2^s-2s( (s)+1)+2 ≤2s−3/2πs+1/2e−s+1/24+(2s−2s+2)≤3s ≤ 2^s-3/2 πs^s+1/2e^-s+1/24+(2^s-2s+2)≤ 3s^s where the last inequality follows from (C.6). Similarly, for d≥2d≥ 2, a combination of (C.3), (C.4) and (C.5) yields ∑T=⌊r⌋+2∞h⁡(T) _T= r +2^∞h(T) ≤[1+2eκ~(e+1)s]∫r∞h⁡(T)T ≤ [1+ 2e κ(e+1)s ] _r^∞h(T)dT ≤[1+2eκ~(e+1)s]2sd−2(Γ⁡(sd)+1)sλκ~−1rd−1/s ≤ [1+ 2e κ(e+1)s ]2^sd-2( (sd)+1)sλ κ^-1r^d-1/s ≤2sd−2(s+2e+1)(Γ⁡(sd)+1)λrd ≤ 2^sd-2 (s+ 2ee+1 )( (sd)+1)λ r^d ≤2sd−2(s+32)(Γ⁡(sd)+1)λrd, ≤ 2^sd-2 (s+ 32 )( (sd)+1)λ r^d, and then with (C.1), we get ∑j∈ℕ+de−κ~|j|11/se−κ~|j|11/s+λ≤[2sd−2(s+32)Γ⁡(sd)+1Γ⁡(d)+1Γ⁡(d)]rd. _j _+^d e^- κ|j|_1^1/se^- κ|j|_1^1/s+λ≤ [2^sd-2 (s+ 32 ) (sd)+1 (d)+ 1 (d) ]r^d. Note that Γ⁡(sd)+1≥2 (sd)+1≥ 2. To simplify the prefactor before rdr^d, we employ the fact (C.6) 2πx−1/2e−x≤Γ⁡(x)≤2πx−1/2e−x+1/(12x) 2πx^x-1/2e^-x≤ (x)≤ 2πx^x-1/2e^-x+1/(12x) from [2, Chapter 3] and calculate 2sd−1(s+2)Γ⁡(sd)Γ⁡(d) 2^sd-1(s+2) (sd) (d) ≤2sd−1(s+2)(sd)sd−1/2e−sd+1/24d−1/2e−d ≤ 2^sd-1(s+2) (sd)^sd-1/2e^-sd+1/24d^d-1/2e^-d ≤e1/24(s+2)2s(2sde)sd(ed)d ≤ e^1/24(s+2)2 s ( 2sde )^sd ( ed )^d ≤2s(2/e)2(s−1)(sd)sd≤2(sd)sd. ≤ 2 s(2/e)^2(s-1)(sd)^sd≤ 2(sd)^sd. Recalling that r=κ~−slns⁡(1/λ)r= κ^-s ^s(1/λ) gives the claimed estimate and completes the proof. ∎ We prove the following technical lemma to control the summation series. Lemma C.3. Let 0<κ~<20< κ<2 and 0<λ≤10<λ≤ 1. Choose M≥dM≥ d such that λ=(M/d)−κ~Mλ= (M/d )^- κM. Then, ∑j∈ℕ+de−κ~∑p=1djplnjpe−κ~∑p=1djplnjp+λ≤(1κ~+32)d(eMd)d. _j _+^d e^- κ _p=1^dj_p j_pe^- κ _p=1^dj_p j_p+λ≤ ( 1 κ+ 32 )^d ( eMd )^d. Proof. Since xln⁡x x is convex, Jensen’s inequality gives 1d∑p=1djpln⁡jp≥|j|1dln⁡|j|1d 1d _p=1^dj_p j_p≥ |j|_1d |j|_1d , which implies ∑j∈ℕ+de−κ~∑p=1djplnjpe−κ~∑p=1djplnjp+λ _j _+^d e^- κ _p=1^dj_p j_pe^- κ _p=1^dj_p j_p+λ ≤∑j∈ℕ+de−κ~|j|1ln⁡(|j|1/d)e−κ~|j|1ln⁡(|j|1/d)+λ. ≤ _j _+^d e^- κ|j|_1 (|j|_1/d)e^- κ|j|_1 (|j|_1/d)+λ. Similar as in the proof of Lemma C.2, we divide the summation into two parts I :=∑|j|1≤Me−κ~|j|1ln⁡(|j|1/d)e−κ~|j|1ln⁡(|j|1/d)+λ≤(⌊M⌋d), := _|j|_1≤ M e^- κ|j|_1 (|j|_1/d)e^- κ|j|_1 (|j|_1/d)+λ≤ pmatrix M \\ d pmatrix, I :=∑|j|1>Me−κ~|j|1ln⁡(|j|1/d)e−κ~|j|1ln⁡(|j|1/d)+λ≤1λ∑T=⌊M⌋+1∞(T−1d−1)(Td)−κ~T. := _|j|_1>M e^- κ|j|_1 (|j|_1/d)e^- κ|j|_1 (|j|_1/d)+λ≤ 1λ _T= M +1^∞ pmatrixT-1\\ d-1 pmatrix ( Td )^- κT. Using Γ⁡(d+1)=dΓ(d) (d+1)=d (d) and (C.6), we bound II by M for d=1d=1 and for d≥2d≥ 2, (C.7) I ≤(M−(d−1)/2)d2πd+1/2e−d≤12πd(eMd)d. ≤ (M-(d-1)/2 )^d 2πd^d+1/2e^-d≤ 1 2π d ( eMd )^d. Since (M/d)κ~M (M/d ) κM is an increasing function of M when M≥dM≥ d, we bound II for d=1d=1 by I ≤∑T=0∞(T+⌊M⌋+1)−κ~(T+⌊M⌋+1)Mκ~M ≤ _T=0^∞ (T+ M +1 )^- κ(T+ M +1)M κM ≤∑T=0∞(T+⌊M⌋+1)−κ~T≤(1−2−κ~)−1. ≤ _T=0^∞ (T+ M +1 )^- κT≤ (1-2^- κ )^-1. Then, applying Lemma C.4, we get I≤2max⁡(κ~−1,2)I≤ 2 ( κ^-1,2) and ∑j∈ℕ+de−κ~∑p=1djplnjpe−κ~∑p=1djplnjp+λ _j _+^d e^- κ _p=1^dj_p j_pe^- κ _p=1^dj_p j_p+λ ≤[1+2max⁡(κ~−1,2)]M, ≤ [1+2 ( κ^-1,2) ]M, which implies the desired bound for d=1d=1. For d≥2d≥ 2, we employ (C.6) to lower-bound the factorial in the binomial coefficient and obtain I ≤1λ∑T=0∞(T+⌊M⌋)d−12πd−1/2e−d(T+⌊M⌋+1d)−κ~(T+⌊M⌋+1) ≤ 1λ _T=0^∞ (T+ M )^d-1 2πd^d-1/2e^-d ( T+ M +1d )^- κ(T+ M +1) ≤ed2πd∑T=0∞(T+⌊M⌋+1d)d−1−κ~T. ≤ e^d 2π d _T=0^∞ ( T+ M +1d )^d-1- κT. According to T<(d−1)/κ~T<(d-1)/ κ or T≥(d−1)/κ~T≥(d-1)/ κ, we decompose the above sum into two parts and control each with an arithmetic sequence I ≤ed2πd[∑T<(d−1)/κ~(d−1κ~d+⌊M⌋+1d)d−1−κ~T+∑T≥(d−1)/κ~(d−1κ~d+⌊M⌋+1d)d−1−κ~T] ≤ e^d 2π d [ _T<(d-1)/ κ ( d-1 κd+ M +1d )^d-1- κT+ _T≥(d-1)/ κ ( d-1 κd+ M +1d )^d-1- κT ] ≤ed2πd(1κ~+3M2d)d−1[1−(12κ~+1)−κ~]−1, ≤ e^d 2π d ( 1 κ+ 3M2d )^d-1 [1- ( 12 κ+1 )^- κ ]^-1, where we used d≤M<⌊M⌋+1≤3M/2d≤ M< M +1≤ 3M/2 in the second inequality. Then, applying Lemma C.4, we get I ≤2ed2πd(1κ~+3M2d)d−1max⁡(κ~−1,2)≤1π(1κ~+32)d(eMd)d. ≤ 2e^d 2π d ( 1 κ+ 3M2d )^d-1 ( κ^-1,2)≤ 1 π ( 1 κ+ 32 )^d ( eMd )^d. Since d≥2d≥ 2 implies (2πd)−1/2+π−1/2<1(2π d)^-1/2+π^-1/2<1, combining the above estimate with (C.7) completes the proof. ∎ Lemma C.4. For all κ~>0 κ>0, it holds that (1−2−κ~)−1≤2max⁡(κ~−1,2) (1-2^- κ )^-1≤ 2 ( κ^-1,2) and (C.8) [1−(12κ~+1)−κ~]−1≤2max⁡(κ~−1,2). [1- ( 12 κ+1 )^- κ ]^-1≤ 2 ( κ^-1,2). Proof. Note that (1−2−κ~)−1 (1-2^- κ )^-1 is monotonically decreasing, which implies (1−2−κ~)−1≤4 (1-2^- κ )^-1≤ 4 for κ~≥1/2 κ≥ 1/2. Then, the first inequality follows from κ~/2≤1−2−κ~ κ/2≤ 1-2^- κ for κ~<1/2 κ<1/2. For (C.8), the left-hand side is monotonically decreasing with respect to κ~ κ because [(12κ~+1)−κ~]′=(2κ~2κ~+1)κ~[ln⁡2κ~2κ~+1+1−2κ~2κ~+1]≤0. [ ( 12 κ+1 )^- κ ] = ( 2 κ2 κ+1 ) κ [ 2 κ2 κ+1+1- 2 κ2 κ+1 ]≤ 0. Thus, for all κ~≥1/2 κ≥ 1/2, the left-hand side is no more than (1−2−1/2)−1<4 (1-2^-1/2 )^-1<4. Then, it remains to prove κ~−1[1−(12κ~+1)−κ~]≥2(1−2−1/2)≥12,for 0<κ~≤1/2. κ^-1 [1- ( 12 κ+1 )^- κ ]≥ 2 (1-2^-1/2 )≥ 12, 0< κ≤ 1/2. The above inequality holds because the left-hand side is a decreasing function with derivative 1κ~2(2κ~2κ~+1)κ~[−κ~ln⁡(2κ~2κ~+1)−(2κ~2κ~+1)−κ~+κ~+12κ~+1]≤−1κ~(2κ~+1)(2κ~2κ~+1)κ~<0, 1 κ^2 ( 2 κ2 κ+1 ) κ [- κ ( 2 κ2 κ+1 )- ( 2 κ2 κ+1 )^- κ+ κ+12 κ+1 ]≤- 1 κ(2 κ+1) ( 2 κ2 κ+1 ) κ<0, which completes the proof. ∎ Appendix D Proofs for RFM solvers D.1. Proof of the strong-form error estimate The proof of Theorem 4.2 uses the following stability and continuity estimates. Proposition D.1. Under the assumptions of Theorem 4.2, there exists a constant C>0C>0, independent of u and uNu_N, such that infv∈V‖u−uN−v‖Hs+l+1/2(Ω)≤Cℒ⁡(uN)for all uN∈H2(Ω). _v∈ V\|u-u_N-v\|_H^s+l+1/2( )≤ C L(u_N) all u_N∈ H^2( ). Proof. By [39, Chapter 2, Theorems 5.4 and 7.4], the boundary value operator w↦(Lw,Bw)w (Lw,Bw) satisfies, for every 0<r≤20<r≤ 2, (D.1) infz∈V‖w−z‖Hr(Ω)≤Cr(‖Lw‖Ξr−2(Ω)+‖Bw‖Hr−l−1/2(∂Ω)), _z∈ V\|w-z\|_H^r( )≤ C_r (\|Lw\|_ ^r-2( )+\|Bw\|_H^r-l-1/2(∂ ) ), where CrC_r is independent of w and Ξr−2(Ω) ^r-2( ) denotes the interior data space in the notation of Lions–Magenes. For 0<r≤20<r≤ 2, the continuous embedding L2(Ω)↪Ξr−2(Ω)L^2( ) ^r-2( ) follows from [39, Chapter 2, equations (6.20) and (6.22)]. Taking r=s+l+1/2r=s+l+1/2 and w=u−uNw=u-u_N in (D.1) gives the result and completes the proof. ∎ Lemma D.2. The following estimates hold. (1) Under the assumptions of Theorem 4.2, ℒ⁡(v)≲Ω,L,B,γ∥u−v∥H2(Ω)for all v∈H2(Ω). L(v) _ ,L,B,γ\|u-v\|_H^2( ) all v∈ H^2( ). (2) Under Assumption 4.1, ∥Lv∥L∞(Ω)+∥Bv∥L∞(∂Ω)≲Ω,d,Λii=15∥v∥W2,∞(Ω)for all v∈W2,∞(Ω).\|Lv\|_L^∞( )+\|Bv\|_L^∞(∂ ) _ ,d,\ _i\_i=1^5\|v\|_W^2,∞( ) all v∈ W^2,∞( ). The first estimate follows from the definitions of ℒL, L, and B, together with the trace theorem. The second follows directly from the coefficient bounds in Assumption 4.1. Proof of Theorem 4.2. For any w∈VRFw∈ V_RF, the minimality of uRFu_RF gives ℒ⁡(uRF)≤ℒ⁡(w)L(u_RF) (w). Proposition D.1 and Lemma D.2(1) therefore yield infv∈V‖u−uRF−v‖Hs+l+1/2(Ω)≤Cℒ⁡(w)≤C‖u−w‖H2(Ω). _v∈ V\|u-u_RF-v\|_H^s+l+1/2( )≤ C L(w)≤ C\|u-w\|_H^2( ). Taking the infimum over w∈VRFw∈ V_RF proves the theorem and completes the proof. ∎ Appendix E Proofs for singular-value estimates and condition-number lower bounds This appendix collects the auxiliary estimates and the proofs of Theorems 5.1 and 5.2. Auxiliary lemmas Lemma E.1. Let s∈ℕ+s _+, 1≤p≤∞1≤ p≤∞ and Ω=(−1,1)d =(-1,1)^d. Denote ς1(x)=∏i=1d2πxisin(πxi2),and ς2(x)=e−|x|2/4 _1(x)= _i=1^d 2π x_i ( π x_i2 ), _2(x)=e^-|x|^2/4 . Then, ∥v∥Ws,p(Ω)≲d,s∥ςjv∥Ws,p(Ω)\|v\|_W^s,p( ) _d,s\| _jv\|_W^s,p( ) for all v∈Ws,p(Ω)v∈ W^s,p( ) and j=1,2j=1,2. Proof. Since sin⁡(z)/z (z)/z and z/sin⁡(z)z/ (z) are analytic on z∈ℂ:|z|≤3π/4\z :|z|≤ 3π/4\, we have ς1,1/ς1∈C∞(Ω) _1,1/ _1∈ C^∞( ). For ς2 _2, it also holds that e−|x|2/4,e|x|2/4∈C∞(Ω)e^-|x|^2/4,e^|x|^2/4∈ C^∞( ). Denote w⁡(x)=ςj(x)v(x)w(x)= _j(x)v(x). Then w∈Ws,p(Ω)w∈ W^s,p( ) because ∥w∥Ws,p(Ω)≲d,s∥ςj∥Ws,∞(Ω)∥v∥Ws,p(Ω)\|w\|_W^s,p( ) _d,s\| _j\|_W^s,∞( )\|v\|_W^s,p( ) . Since Ω is bounded, 1/ςj∈Ws,∞(Ω)1/ _j∈ W^s,∞( ) and ∥v∥Ws,p(Ω)=∥w/ςj∥Ws,p(Ω)≲d,s∥1/ςj∥Ws,∞(Ω)∥w∥Ws,p(Ω)\|v\|_W^s,p( )=\|w/ _j\|_W^s,p( ) _d,s\|1/ _j\|_W^s,∞( )\|w\|_W^s,p( ) , which completes the proof. ∎ Lemma E.2. Let ς2(x)=e−|x|2/4 _2(x)=e^-|x|^2/4, S>0S>0 and κ=min⁡(1,11π/(96dS))κ= (1,11π/(96 dS)). Then, ∥ς2tanh(k⊤⋅+v)∥κ,1≲d1+Sd, for k∈[−S,S]d and v∈ℝ. \| _2 (k ·+v)\|_κ,1 _d1+S^d, for $k∈[-S,S]^d$ and $v $. Proof. Denote u:=ς2tanh(k⊤⋅+v)u:= _2 (k ·+v). The case k=0k=0 follows directly from the Gaussian Fourier transform, so we assume k≠0k≠ 0 below. The function u has an analytic continuation to the set ζ∈ℂd:|k⊤Im⁡ζ|<π/2\ζ ^d:|k Imζ|<π/2\ as u(λ+iη)=[1−2e2(k⊤λ+v+ik⊤η)+1]e−(|λ|2−|η|2+2iλ⊤η)/4,u(λ+iη)= [1- 2e^2 (k λ+v+ik η )+1 ]e^- (|λ|^2-|η|^2+2iλ η )/4, for λ,η∈ℝdλ,η ^d and |k⊤η|<π/2|k η|<π/2. For each such η, u⁡(λ+iη)u(λ+iη) is in ′(ℝd) S (R^d) as a function of λ. By Cauchy’s theorem, we can shift the region of integration in Fourier transform so that (E.1) u^(ξ)=(2π)−d/2∫ℝdu(λ+iη)e−iξ⊤(λ+iη)dλ. u(ξ)=(2π)^-d/2 _R^du(λ+iη)e^-iξ (λ+iη)dλ. For |k⊤η|≤11π/24|k η|≤ 11π/24, note that |tanh⁡(k⊤λ+v+ik⊤η)| | (k λ+v+ik η) | =|e4(k⊤λ+v)−1+2ie2(k⊤λ+v)sin⁡(2k⊤η)e4(k⊤λ+v)+1+2e2(k⊤λ+v)cos⁡(2k⊤η)| = | e^4(k λ+v)-1+2ie^2(k λ+v) (2k η)e^4(k λ+v)+1+2e^2(k λ+v) (2k η) | ≤e4(k⊤λ+v)+1e4(k⊤λ+v)+1+2e2(k⊤λ+v)cos⁡(2k⊤η) ≤ e^4(k λ+v)+1e^4(k λ+v)+1+2e^2(k λ+v) (2k η) ≤1−cos⁡(11π/12)1+cos⁡(11π/12)≤30. ≤ 1- (11π/12)1+ (11π/12)≤ 30. Then, we take η=−2ξη=-2ξ for |ξ|≤11π48|k||ξ|≤ 11π48|k| and η=−11πξ24|k||ξ|η=- 11πξ24|k||ξ| otherwise in (E.1), which gives |u^(ξ)| | u(ξ)| ≤30⋅2d/2e−|ξ|2,|ξ|≤11π48|k|,e(11π48|k|)2−11π|ξ|24|k|,|ξ|≥11π48|k|. ≤ 30· 2^d/2 \ array[]le^-|ξ|^2,&|ξ|≤ 11π48|k|,\\ e ( 11π48|k| )^2- 11π|ξ|24|k|,&|ξ|≥ 11π48|k|. array . Since κ=min⁡(1,11π/(96dS))κ= (1,11π/(96 dS)), we have κ≤11π/(96|k|)κ≤ 11π/(96|k|). By direct calculation, ‖u‖κ,12 \|u\|_κ,1^2 ≲∫011π48|k|d⁡rd−1e−2r2+2κrr+∫11π48|k|∞rd−1e2(11π48|k|)2−11πr12|k|+2κrr _d _0 11π48|k|r^d-1e^-2r^2+2κ rdr+ _ 11π48|k|^∞r^d-1e^2 ( 11π48|k| )^2- 11π r12|k|+2κ rdr ≲∫0∞d⁡e−2r2+(2κ+1)rr+e−(11π48|k|)2∫0∞(r+11π48|k|)d−1e−11π16|k|rr _d _0^∞e^-2r^2+(2κ+1)rdr+e^- ( 11π48|k| )^2 _0^∞ (r+ 11π48|k| )^d-1e^- 11π16|k|rdr ≲de(2κ+1)2/8+1+|k|d, _de^(2κ+1)^2/8+1+|k|^d, which completes the proof. ∎ Lemma E.3 (Low-frequency Taylor approximation for Fourier features). For every T≥2T≥ 2 and 0<|k|<(2d)−10<|k|<(2 d)^-1, the polynomial PT(k,x):=∑ℓ=0T(ık⊤x)ℓ!P_T(k,x):= _ =0^T ( k x) ! satisfies ‖eık⊤(⋅)−PT(k,⋅)‖W2,∞([−1,1]d)≲d|k|22−(T−1)(T−1)!. \|e k (·)-P_T(k,·) \|_W^2,∞([-1,1]^d) _d|k|^2 2^-(T-1)(T-1)!. The same estimate holds for the real and imaginary parts. Proof. Let α be a multi-index with r:=|α|≤2r:=|α|≤ 2. Since ∂αPT(k,x)=(ık)αPT−r(k,x)∂^αP_T(k,x)=( k)^αP_T-r(k,x), the exponential-series remainder gives |∂α(eık⊤x−PT(k,x))|≤|k|re|k⊤x||k⊤x|T−r+1(T−r+1)!. |∂^α (e k x-P_T(k,x) ) |≤|k|^re^|k x| |k x|^T-r+1(T-r+1)!. For x∈[−1,1]dx∈[-1,1]^d and |k|<(2d)−1|k|<(2 d)^-1, one has |k⊤x|≤d|k|<1/2|k x|≤ d\,|k|<1/2. Consequently, |k|re|k⊤x||k⊤x|T−r+1(T−r+1)!≤d(2−r)/2e1/2|k|2(d|k|)T−1(T−1)!≲d|k|22−(T−1)(T−1)!.|k|^re^|k x| |k x|^T-r+1(T-r+1)!≤ d^(2-r)/2e^1/2|k|^2 ( d\,|k|)^T-1(T-1)! _d|k|^2 2^-(T-1)(T-1)!. Taking the maximum over |α|≤2|α|≤ 2 proves the asserted bound. Taking real or imaginary parts cannot increase the norm, which completes the proof. ∎ Lemma E.4 (Low-frequency Taylor approximation for tanh features). Set ρT:=4/(7d)∈(0,1) _T:=4/(7 d)∈(0,1). For every T≥2T≥ 2, 0<|k|<ρT0<|k|< _T, and |v|≤dS|v|≤ dS, the polynomial PT,k,v(x):=∑ℓ=0Ttanh(ℓ)⁡(v)ℓ!(k⊤x)ℓP_T,k,v(x):= _ =0^T ^( )(v) !(k x) satisfies (E.2) ‖tanh(k⊤⋅+v)−PT,k,v‖W2,∞([−1,1]d)≲d,S|k|2(|k|2ρT)T−1. \| (k ·+v)-P_T,k,v \|_W^2,∞([-1,1]^d) _d,S|k|^2 ( |k|2 _T )^T-1. Proof. For v∈[−dS,dS]v∈[-dS,dS], the function w↦tanh⁡(v+w)w (v+w) is analytic in |w|<π/2|w|<π/2. Cauchy’s estimate on the circle |w|=4/3|w|=4/3 gives |tanh(ℓ)⁡(v)|ℓ!≲d,S(34)ℓ. | ^( )(v)| ! _d,S ( 34 ) . Since supℓ≥0(1+ℓ)2(6/7)ℓ<∞ _ ≥ 0(1+ )^2(6/7) <∞, we have |tanh(ℓ)⁡(v)|ℓ!ℓr≲d,S(78)ℓ,ℓ≥r,0≤r≤2. | ^( )(v)| !\, ^r _d,S ( 78 ) , ≥ r, 0≤ r≤ 2. Let α be a multi-index with r:=|α|≤2r:=|α|≤ 2 and put s:=7d|k|/8=|k|/(2ρT)<1/2s:=7 d\,|k|/8=|k|/(2 _T)<1/2. Termwise differentiation of the Taylor series and |k⊤x|≤d|k||k x|≤ d\,|k| yield, uniformly for x∈[−1,1]dx∈[-1,1]^d, |∂α(tanh⁡(k⊤x+v)−PT,k,v(x))| |∂^α ( (k x+v)-P_T,k,v(x) ) | ≲d,S|k|r∑ℓ=T+1∞sℓ−r _d,S|k|^r _ =T+1^∞s -r ≲d,S|k|rsT+1−r _d,S|k|^rs^T+1-r ≲d,S|k|2sT−1. _d,S|k|^2s^T-1. The implicit constant in the last step is uniform for 0≤r≤20≤ r≤ 2 because s/|k|=(2ρT)−1s/|k|=(2 _T)^-1. Taking the maximum over |α|≤2|α|≤ 2 proves (E.2) and completes the proof. ∎ Proof of Theorem 5.1 Proof. Put K:=m−1K:=m-1. The hypothesis on m gives K≥3Mln⁡(15M)K≥ 3M (15M). Note that σm()≤‖F/m _m( )≤\| \|_F/ m always holds for any matrix and m. We shall prove the upper bound on σm _m for m≥3m≥ 3. By the minimax principle, σm=mindim⁡H=2N−m+1⁡max∈H||||, _m= _dimH=2N-m+1 _ β∈ H | β|| β|, where H is a linear subspace of ℝ2NR^2N. To control σm _m, it suffices to find a (2N−m+1)(2N-m+1)-dimensional linear subspace on which ||| β| is small relative to ||| β|. We reduce this problem to mutual approximation of the features ψj _j in W2,∞(Ω)W^2,∞( ), thereby minimizing the dependence on the collocation points, domain, and differential equation. By Lemma D.2 and the trace theorem, we obtain |β|2 | β|^2 ≤n1‖∑j=12NβjLψj‖L∞(Ω)2+n2‖∑j=12NβjBψj‖L∞(∂Ω)2 ≤ n_1 \| _j=1^2N _jL _j \|_L^∞( )^2+n_2 \| _j=1^2N _jB _j \|_L^∞(∂ )^2 ≲Ω,d,Λii=15n1‖∑j=12Nβjψj‖W2,∞(Ω)2+n2‖∑j=12Nβjψj‖W1,∞(∂Ω)2 _ ,d,\ _i\_i=1^5n_1 \| _j=1^2N _j _j \|_W^2,∞( )^2+n_2 \| _j=1^2N _j _j \|_W^1,∞(∂ )^2 ≲Ω,d,Λii=15n‖∑j=12Nβjψj‖W2,∞(Ω)2. _ ,d,\ _i\_i=1^5n \| _j=1^2N _j _j \|_W^2,∞( )^2. Denote Ω~=(−1,1)d =(-1,1)^d. Then, it follows from Ω⊂Ω~ ⊂ and Lemma E.1 that |β| | β| ≲Ω,d,Λii=15n‖∑j=12Nβjςψj‖W2,∞(Ω~), _ ,d,\ _i\_i=1^5 n \| _j=1^2N _j _j \|_W^2,∞( ), where ς can be 11, ς1 _1 or ς2 _2 as in Lemma E.1. For each j, suppose φj _j is an approximation of ςψj _j in some linear subspace of dimension at most m−1m-1. Then there exists a (2N−m+1)(2N-m+1)-dimensional subspace H⊂ℝ2NH ^2N such that ∑j=12Nβjφj(x)=0,for any β∈H. _j=1^2N _j _j(x)=0, any β∈ H. Using the above relation, the triangle inequality, and the Cauchy–Schwarz inequality, we obtain ‖∑j=12Nβjςψj‖W2,∞(Ω~) \| _j=1^2N _j _j \|_W^2,∞( ) =‖∑j=12Nβj(ςψj−φj)‖W2,∞(Ω~) = \| _j=1^2N _j ( _j- _j ) \|_W^2,∞( ) ≤|β|(∑j=12N‖ςψj−φj‖W2,∞(Ω~)2)1/2, ≤|β| ( _j=1^2N \| _j- _j \|_W^2,∞( )^2 )^1/2, and therefore (E.3) σm≲Ω,d,Λii=15n(∑j=12N‖ςψj−φj‖W2,∞(Ω~)2)1/2. _m _ ,d,\ _i\_i=1^5 n ( _j=1^2N \| _j- _j \|_W^2,∞( )^2 )^1/2. So far, we have reduced bounding σm _m to the approximation to ςψj _j by φj _j. We shall choose appropriate ς and φj _j in each case. It remains to construct the approximants φj _j. Fix δ0∈(14/15,1) _0∈(14/15,1). Since 14/δ0<1514/ _0<15, the assumed lower bound on K implies the sampling condition in Theorem 3.2 with N=KN=K and δ=δ0δ= _0. For Fourier features, take ς=ς1 = _1 and set SF:=S+π/2S_F:=S+π/2. Direct calculation gives (ς1cos(k⊤⋅))∧(ξ)=(2/π)d/22(1|ξ+k|∞<π2+1|ξ−k|∞<π2), ( _1 (k ·) ) (ξ)= (2/π)^d/22 (1_|ξ+k|_∞< π2+1_|ξ-k|_∞< π2 ), (ς1sin(k⊤⋅))∧(ξ)=(2/π)d/22i(1|ξ+k|∞<π2−1|ξ−k|∞<π2). ( _1 (k ·) ) (ξ)= (2/π)^d/22i (1_|ξ+k|_∞< π2-1_|ξ-k|_∞< π2 ). Hence both functions are supported in QSF¯ Q_S_F in frequency and have L2(ℝd)L^2(R^d) norms bounded by a constant depending only on d. Put aλ,F:=21−1/d28e,aF:=34aλ,F=3⋅21−1/d112e.a_λ,F:= 2^1-1/d28e, a_F:= 34a_λ,F= 3· 2^1-1/d112e. Apply Theorem 3.2(4) on Ω~ using the randomly shifted cosine representation and taking t=2t=2 and p=∞p=∞. With λF=cλ,Fexp⁡(−aλ,FM1/dln⁡M) _F=c_λ,F (-a_λ,FM^1/d M ), the theorem supplies one set of K sampled frequency–phase pairs and, simultaneously for all 2N2N target functions, approximants φj _j in the resulting K-dimensional real trial space such that ∥ς1ψj−φj∥W2,∞(Ω~)≲d,Sexp(−aFM1/dlnM),1≤j≤2N.\| _1 _j- _j\|_W^2,∞( ) _d,S (-a_FM^1/d M ), 1≤ j≤ 2N. The event has probability at least 1−δ0>01- _0>0 and is uniform over the target ball. Since the features and targets are real, taking the real parts of the coefficients does not increase either the approximation error or the coefficient norm. We therefore fix one realization for which these estimates hold. Since K=m−1K=m-1, substituting these estimates into (E.3) proves (5.1). For tanh features, take ς=ς2 = _2 and put κT:=min⁡1,11π96dS. _T:= \1, 11π96 d\,S \. Lemma E.2 yields, uniformly for kj∈[−S,S]dk_j∈[-S,S]^d and vj∈ℝv_j , ∥ς2ψj∥κT,1≲d1+Sd\| _2 _j\|_ _T,1 _d1+S^d. Apply Theorem 3.2(2) with the randomly shifted cosine representation, s=1s=1, and κ=κ¯=κTκ= κ= _T, taking t=2t=2 and p=∞p=∞. Thus σ=1σ=1 and θ=1/2θ=1/2. Since κT _T depends only on d and S, and since the application domain Ω~=(−1,1)d =(-1,1)^d is fixed, the theorem yields a constant aT=aT(d,S)>0a_T=a_T(d,S)>0. The same uniform-event argument supplies approximants in a common K-dimensional real trial space satisfying ∥ς2ψj−φj∥W2,∞(Ω~)≲d,Sexp(−aTM1/d),1≤j≤2N.\| _2 _j- _j\|_W^2,∞( ) _d,S (-a_TM^1/d ), 1≤ j≤ 2N. Substitution into (E.3) proves (5.2) and completes the proof. ∎ Proof of Theorem 5.2 Proof. If σ2N=0 _2N=0, the conclusion follows from the stated convention. Assume henceforth that σ2N>0 _2N>0. Theorem 5.1 applies with m=2Nm=2N because 2N−1≥3Mln⁡(15M)2N-1≥ 3M (15M). Thus (5.1) and (5.2), with m=2Nm=2N, apply in the Fourier and tanh cases, respectively. We first prove part (1). For 1≤i≤n11≤ i≤ n_1, ellipticity gives −kj⊤A(xi)kj≥a¯|kj|2-k_j A(x_i)k_j≥ a|k_j|^2. Direct differentiation and cancellation of the cross terms in each cosine–sine pair give (E.4) |Lcos(kj⊤⋅)(xi)|2+|Lsin(kj⊤⋅)(xi)|2=(−kj⊤A(xi)kj+c(xi))2+(b(xi)⊤kj)2,1≤i≤n1, |L (k_j ·)(x_i)|^2+|L (k_j ·)(x_i)|^2= (-k_j A(x_i)k_j+c(x_i) )^2+ (b(x_i) k_j )^2, 1≤ i≤ n_1, |Bcos(kj⊤⋅)(xi)|2+|Bsin(kj⊤⋅)(xi)|2=g12(xi)((xi)⊤kj)2+g22(xi),n1<i≤n. |B (k_j ·)(x_i)|^2+|B (k_j ·)(x_i)|^2=g_1^2(x_i) (n(x_i) k_j )^2+g_2^2(x_i), n_1<i≤ n. Set ℋ:=j:|kj|≥(2d)−1H:=\j:|k_j|≥(2 d)^-1\ and ℒ:=j:|kj|<(2d)−1L:=\j:|k_j|<(2 d)^-1\. Suppose first that |ℋ|≥N/2|H|≥ N/2. Summing the two identities in (E.4) and using c≥0c≥ 0 yields ‖F2 \| \|_F^2 ≥|ℋ|n1a¯216d2+Nn1C2+Nn2G2 ≥ |H|n_1 a^216d^2+Nn_1C^2+Nn_2G^2 ≳dN(n1a¯2+n1C2+n2G2). _dN (n_1 a^2+n_1C^2+n_2G^2 ). Since σ1≥‖F/2N _1≥\| \|_F/ 2N, σ1≳dn1a¯+n1C+n2G. _1 _d n_1\, a+ n_1C+ n_2G. Combining this estimate with (5.1) proves part (1) in this case. It remains to consider |ℒ|>N/2|L|>N/2. If kj=0k_j=0 for some j∈ℒj , the associated sine column is zero, contrary to σ2N>0 _2N>0. Hence every low frequency is nonzero. Put ρ∗:=maxj∈ℒ⁡|kj|∈(0,(2d)−1) _*:= _j |k_j|∈ (0,(2 d)^-1 ) and choose j∗j_* attaining the maximum. By (E.4), ‖⋅,j∗‖22+‖⋅,j∗+N‖22≥n1a¯2ρ∗4+n1C2+n2G2.\| _·,j_*\|_2^2+\| _·,j_*+N\|_2^2≥ n_1 a^2 _*^4+n_1C^2+n_2G^2. Thus at least one of these columns has norm at least the square root of the right-hand side divided by 2 2, and therefore (E.5) σ1≳n1a¯ρ∗2+n1C+n2G. _1 n_1\, a\, _*^2+ n_1C+ n_2G. We next construct a vector that provides an upper bound for σ2N _2N. Let (E.6) T:=⌊d4eM1/d⌋,DT:=dimT(ℝd)=(T+d),T:= d4eM^1/d , D_T:= _T(R^d)= T+dd, where T(ℝd)P_T(R^d) is the space of real polynomials of total degree at most T. For all sufficiently large M, one has d≤dM1/d/(4e)d≤ dM^1/d/(4e), and hence DT≤(e⁡(T+d)/d)d≤2−dM≤M<N<2|ℒ|D_T≤(e(T+d)/d)^d≤ 2^-dM≤ M<N<2|L|. The coefficient bounds and the trace estimate used in the proof of Theorem 5.1 give, for every f∈W2,∞((−1,1)d)f∈ W^2,∞((-1,1)^d), (E.7) |(L~f(xi))i=1n|≲Ω,d,Λii=15n∥f∥W2,∞((−1,1)d). | ( Lf(x_i) )_i=1^n | _ ,d,\ _i\_i=1^5 n\,\|f\|_W^2,∞((-1,1)^d). For j∈ℒj , set pj,c:=|kj|−2Re⁡PT(kj,⋅),pj,s:=|kj|−2Im⁡PT(kj,⋅).p_j,c:=|k_j|^-2ReP_T(k_j,·), p_j,s:=|k_j|^-2ImP_T(k_j,·). The 2|ℒ|2|L| vectors (L~pj,c(xi))i=1n( Lp_j,c(x_i))_i=1^n and (L~pj,s(xi))i=1n( Lp_j,s(x_i))_i=1^n span a subspace of ℝnR^n of dimension at most DT<2|ℒ|D_T<2|L|. Hence there exists γ=(γj,c,γj,s)j∈ℒ∈ℝ2|ℒ|γ=( _j,c, _j,s)_j ^2|L| with |γ|=1|γ|=1 such that (E.8) ∑j∈ℒ[γj,c(L~pj,c(xi))i=1n+γj,s(L~pj,s(xi))i=1n]=0. _j [ _j,c( Lp_j,c(x_i))_i=1^n+ _j,s( Lp_j,s(x_i))_i=1^n ]=0. Define β∈ℝ2Nβ ^2N by βj:=γj,c/|kj|2 _j:= _j,c/|k_j|^2 and βj+N:=γj,s/|kj|2 _j+N:= _j,s/|k_j|^2 for j∈ℒj , and set all remaining components equal to zero. Then (E.9) |β|2=∑j∈ℒ|γj,c|2+|γj,s|2|kj|4≥ρ∗−4.|β|^2= _j | _j,c|^2+| _j,s|^2|k_j|^4≥ _*^-4. Using (E.8), Lemma E.3, (E.7), and Cauchy–Schwarz, we obtain |β| | β| =|(L~∑j∈ℒ[γj,ccos(kj⊤⋅)−RePT(kj,⋅)|kj|2+γj,ssin(kj⊤⋅)−ImPT(kj,⋅)|kj|2](xi))i=1n| = | ( L\! \ _j [ _j,c (k_j ·)-ReP_T(k_j,·)|k_j|^2+ _j,s (k_j ·)-ImP_T(k_j,·)|k_j|^2 ] \(x_i) )_i=1^n | ≲Ω,d,Λii=15n2−(T−1)(T−1)!∑j∈ℒ(|γj,c|+|γj,s|) _ ,d,\ _i\_i=1^5 n\, 2^-(T-1)(T-1)! _j (| _j,c|+| _j,s|) ≲Ω,d,Λii=15nN2−(T−1)(T−1)!. _ ,d,\ _i\_i=1^5 nN\, 2^-(T-1)(T-1)!. Together with (E.9), this gives (E.10) σ2N≤|β||β|≲Ω,d,Λii=15ρ∗2nN2−(T−1)(T−1)!. _2N≤ | β||β| _ ,d,\ _i\_i=1^5 _*^2 nN\, 2^-(T-1)(T-1)!. Combining (E.5) and (E.10), and using ρ∗<1 _*<1, yields (E.11) σ1σ2N≳Ω,d,Λii=15n1a¯+n1C+n2GnN 2T−1(T−1)!. _1 _2N _ ,d,\ _i\_i=1^5 n_1\, a+ n_1C+ n_2G nN\,2^T-1(T-1)!. It remains to compare the factorial decay with the explicit rate constant aFa_F. The elementary bound (T−1)!≥((T−1)/e)T−1(T-1)!≥((T-1)/e)^T-1 gives ln⁡(2T−1(T−1)!)≥(T−1)ln⁡(2(T−1)e). (2^T-1(T-1)! )≥(T-1) ( 2(T-1)e ). For all sufficiently large M, one has T−1≥3d16eM1/d,ln⁡(2(T−1)e)≥34dln⁡M.T-1≥ 3d16eM^1/d, ( 2(T-1)e )≥ 34d M. It follows that ln⁡(2T−1(T−1)!)≥964eM1/dln⁡M. (2^T-1(T-1)! )≥ 964eM^1/d M. Since aF=3⋅21−1/d112e≤356e<964e,a_F= 3· 2^1-1/d112e≤ 356e< 964e, we have 2T−1(T−1)!≥exp⁡(aFM1/dln⁡M)2^T-1(T-1)!≥ (a_FM^1/d M) for all sufficiently large M. Substitution into (E.11) proves part (1) in the low-frequency case. We now prove part (2). The argument first converts Assumption (5.3) into a lower bound for individual columns. For any k≠0k≠ 0 and v∈ℝv , the choice θ=k/|k|θ=k/|k| gives (E.12) max1≤i≤n1⁡|k⊤xi+v| _1≤ i≤ n_1|k x_i+v| ≥12(max1≤i≤n1⁡(k⊤xi+v)−min1≤i≤n1⁡(k⊤xi+v)) ≥ 12 ( _1≤ i≤ n_1(k x_i+v)- _1≤ i≤ n_1(k x_i+v) ) ≥r0|k|. ≥ r_0|k|. Since kj∈[−S,S]dk_j∈[-S,S]^d, |vj|≤dS|v_j|≤ dS, and xi∈(−1,1)dx_i∈(-1,1)^d, all preactivations zij:=kj⊤xi+vjz_ij:=k_j x_i+v_j satisfy |zij|≤2dS|z_ij|≤ 2dS. The function |tanh′⁡z|/|z|| z|/|z|, initially defined for z≠0z≠ 0, extends continuously to z=0z=0 with value 22 and is positive on [−2dS,2dS][-2dS,2dS]. Consequently, μT:=min|z|≤2dS⁡|tanh′⁡z||z|>0, _T:= _|z|≤ 2dS | z||z|>0, where the quotient at the origin is understood by continuity. Put qij:=−kj⊤A(xi)kj≥a¯|kj|2q_ij:=-k_j A(x_i)k_j≥ a|k_j|^2. Because b≡0b≡ 0 and tanh′⁡z=−2tanh⁡zsech2z z=-2 z\,sech^2z, Lψj(xi)=(2qijsech2zij+c(xi))tanhzij.L _j(x_i)= (2q_ijsech^2z_ij+c(x_i) ) z_ij. The two terms on the right have the same sign. Hence |Lψj(xi)|≥qij|tanh′⁡zij|≥a¯|kj|2|tanh′⁡zij|.|L _j(x_i)|≥ q_ij| z_ij|≥ a|k_j|^2| z_ij|. Combining this estimate with (E.12) shows that every column satisfies (E.13) max1≤i≤n1⁡|Lψj(xi)|≥μTr0a¯|kj|3. _1≤ i≤ n_1|L _j(x_i)|≥ _Tr_0 a|k_j|^3. Let ρT:=4/(7d) _T:=4/(7 d) be as in Lemma E.4, and set ℒT:=j:|kj|<ρTL_T:=\j:|k_j|< _T\ and ℋT:=j:|kj|≥ρTH_T:=\j:|k_j|≥ _T\. By (E.12), every j∈ℋTj _T has an interior preactivation of magnitude at least r0ρTr_0 _T. We distinguish two exhaustive cases. Suppose first that |ℒT|<N|L_T|<N. Then |ℋT|>N|H_T|>N, and (E.13) yields ‖F2≥∑j∈ℋTmax1≤i≤n1⁡|Lψj(xi)|2≥NμT2r02a¯2ρT6.\| \|_F^2≥ _j _T _1≤ i≤ n_1|L _j(x_i)|^2≥ N _T^2r_0^2 a^2 _T^6. It follows that σ1≥‖F2N≥μTr0ρT32a¯. _1≥ \| \|_F 2N≥ _Tr_0 _T^3 2\, a. Together with (5.2) and a~T≤aT a_T≤ a_T, this proves (5.4) in the high-frequency case. It remains to consider |ℒT|≥N|L_T|≥ N. Let T and DTD_T be as in (E.6). The estimate DT≤MD_T≤ M proved above and the sampling condition imply DT<N−1D_T<N-1 for all sufficiently large M. If two indices in ℒTL_T had zero frequency, their features would be constant and the associated columns would be linearly dependent. A zero frequency with vj=0v_j=0 would itself give a zero column. Both alternatives contradict σ2N>0 _2N>0. Thus the set ℒT∗:=j∈ℒT:|kj|>0L_T^*:=\j _T:|k_j|>0\ has cardinality at least N−1>DTN-1>D_T. For j∈ℒT∗j _T^*, let Pj:=PT,kj,vjP_j:=P_T,k_j,v_j be the polynomial from Lemma E.4. Since all PjP_j belong to the DTD_T-dimensional space T(ℝd)P_T(R^d), there is a vector γ=(γj)j∈ℒT∗γ=( _j)_j _T^* such that |γ|=1,∑j∈ℒT∗γjPj=0.|γ|=1, _j _T^* _jP_j=0. Extend γ by zero to a vector in ℝ2NR^2N and define ργ:=maxγj≠0⁡|kj|,ρ∗:=maxj∈ℒT∗⁡|kj|. _γ:= _ _j≠ 0|k_j|, _*:= _j _T^*|k_j|. Then 0<ργ≤ρ∗<ρT0< _γ≤ _*< _T. By (E.7), Lemma E.4, and Cauchy–Schwarz, σ2N _2N ≤|γ|=|(L~∑j∈ℒT∗γj(ψj−Pj)(xi))i=1n| ≤| γ|= | ( L\! \ _j _T^* _j( _j-P_j) \(x_i) )_i=1^n | ≲Ω,d,Λii=15,Sn∑j∈ℒT∗|γj||kj|2(|kj|2ρT)T−1 _ ,d,\ _i\_i=1^5,S n _j _T^*| _j||k_j|^2 ( |k_j|2 _T )^T-1 ≲Ω,d,Λii=15,SnNργ2(ργ2ρT)T−1. _ ,d,\ _i\_i=1^5,S nN\, _γ^2 ( _γ2 _T )^T-1. On the other hand, (E.13) gives σ1≥μTr0a¯ρ∗3 _1≥ _Tr_0 a _*^3. Since ρ∗≥ργ _*≥ _γ, we conclude that σ1σ2N _1 _2N ≳Ω,d,Λii=15,S,r0a¯nNρ∗3ργ2(ργ2ρT)−(T−1) _ ,d,\ _i\_i=1^5,S,r_0 a nN _*^3 _γ^2 ( _γ2 _T )^-(T-1) ≥2ρTa¯nN(ργ2ρT)−(T−2)≥ρTa¯nN 2T−1. ≥ 2 _T a nN ( _γ2 _T )^-(T-2)≥ _T a nN\,2^T-1. Finally, T=⌊dM1/d/(4e)⌋T= dM^1/d/(4e) and a~T≤dln⁡2/(4e) a_T≤ d 2/(4e) imply 2T−1≥14exp⁡(dln⁡24eM1/d)≥14exp⁡(a~TM1/d).2^T-1≥ 14 ( d 24eM^1/d )≥ 14 ( a_TM^1/d ). This proves (5.4) in the low-frequency case and completes the proof. ∎

Instant research discovery