OctoInformBeta

OpenAI preprint, September 2026 · §3. A Hilbert kernel with chart extensions

Lemma 3.3: Five explicit inequalities for kernel distance comparison, pairwise inner products, local coordinate variation, rounded chart residuals, and pseudoinverse reconstruction

Angle and Hilbert kernel bounds with chart rounding.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Consider mapping points θ,η∈ℝm\theta, \eta \in \mathbb{R}^m through SS linear charts, each built from NN direction vectors in ℝm\mathbb{R}^m, onto grid-rounded vectors x,x′∈ℝNx, x' \in \mathbb{R}^N, and then into a real Hilbert space HH via a scale-integrated Hilbert kernel with chart extensions. In the negative-type metric construction for the Goemans-Linial relaxation of uniform sparsest cut, one needs error bounds relating the kernel distance to a multiple of ∥η−θ∥\|\eta - \theta\|, lower bounds on pairwise inner products in HH from approximate squared-distance preservation, and local L1L_1-Lipschitz bounds on the kernel within a single chart. One also needs bounds on the linear residual and the point-reconstruction error incurred when rounding θ\theta onto a chart and mapping back by its left pseudoinverse.

The Hilbert Kernel and Kernel Distance

For a real inner-product space EE, a finite index set ι\iota, a vector family g:ι→Eg \colon \iota \to E, real scalars q,ε,σ∈ℝq, \varepsilon, \sigma \in \mathbb{R}, points θ,η∈E\theta, \eta \in E, and coefficient functions α,β:ι→ℝ\alpha, \beta \colon \iota \to \mathbb{R}, the kernel pairing pσg,q,ε(θ,η,α,β)p_\sigma^{g,q,\varepsilon}(\theta,\eta,\alpha,\beta) is the real number given by (1): pσg,q,ε(θ,η,α,β)=qexp⁡(−∥η−θ∥22σ2)+εσ∑i∈ι((1+αiβi)cos⁡⟨gi,η−θ⟩σ+(αi−βi)sin⁡⟨gi,η−θ⟩σ).p_\sigma^{g,q,\varepsilon}(\theta,\eta,\alpha,\beta) = q\exp\!\left(-\frac{\|\eta-\theta\|^2}{2\sigma^2}\right) + \frac{\varepsilon}{\sigma}\sum_{i\in\iota} \biggl((1+\alpha_i\beta_i)\cos\frac{\langle g_i,\eta-\theta\rangle}{\sigma} + (\alpha_i-\beta_i)\sin\frac{\langle g_i,\eta-\theta\rangle}{\sigma}\biggr).(1)✦

Given a real inner-product space EE, a finite index set ι\iota, a vector family g:ι→Eg \colon \iota \to E, real parameters q,ε,a,b∈ℝq, \varepsilon, a, b \in \mathbb{R}, points θ,η∈E\theta, \eta \in E, and coefficient functions α,β:ι→ℝ\alpha, \beta \colon \iota \to \mathbb{R}, the Hilbert kernel Kg,q,ε,a,b(θ,η,α,β)∈ℝK_{g,q,\varepsilon,a,b}(\theta,\eta,\alpha,\beta) \in \mathbb{R} is the scale integral (2): Kg,q,ε,a,b(θ,η,α,β)=∫abpσg,q,ε(θ,η,α,β)dσ.K_{g,q,\varepsilon,a,b}(\theta,\eta,\alpha,\beta) = \int_a^b p_\sigma^{g,q,\varepsilon}(\theta,\eta,\alpha,\beta)\,d\sigma.(2)✦

Over a finite index set κ\kappa, a vector family g:κ→Eg \colon \kappa \to E in a real inner-product space EE, real parameters q,ε,a,b∈ℝq, \varepsilon, a, b \in \mathbb{R}, points θ,η∈E\theta, \eta \in E, and coefficient functions α,β:κ→ℝ\alpha, \beta \colon \kappa \to \mathbb{R}, the kernel distance Dg,q,ε,a,b(θ,η,α,β)D_{g,q,\varepsilon,a,b}(\theta,\eta,\alpha,\beta) is the real number defined by (3): Dg,q,ε,a,b(θ,η,α,β)=Kg,q,ε,a,b(θ,θ,α,α)+Kg,q,ε,a,b(η,η,β,β)−2Kg,q,ε,a,b(θ,η,α,β).D_{g,q,\varepsilon,a,b}(\theta,\eta,\alpha,\beta) = K_{g,q,\varepsilon,a,b}(\theta,\theta,\alpha,\alpha) + K_{g,q,\varepsilon,a,b}(\eta,\eta,\beta,\beta) - 2K_{g,q,\varepsilon,a,b}(\theta,\eta,\alpha,\beta).(3)✦

The profile function ψ:ℝ→ℝ\psi \colon \mathbb{R} \to \mathbb{R} is the function given by ψ(t)=1−exp⁡(−1/(2t2))\psi(t) = 1 - \exp(-1/(2t^2)) for t≠0t \neq 0 and ψ(0)=0\psi(0) = 0✦, and the profile constant c*∈ℝc^* \in \mathbb{R} is the integral c*=2∫0∞ψ(t)dtc^* = 2\int_0^\infty \psi(t)\,dt.✦

Chart Operators, Residuals, and Chart Extensions

To each family of NN vectors u=(u1,…,uN)∈ENu = (u_1, \dots, u_N) \in E^N in a real inner-product space EE, the chart operator Ju:E→ℓ2NJ_u \colon E \to \ell_2^N into NN-dimensional Euclidean space ℓ2N\ell_2^N is the continuous linear map with ii-th coordinate (Juθ)i=⟨ui,θ⟩(J_u \theta)_i = \langle u_i, \theta \rangle for 1≤i≤N1 \le i \le N.✦

When J:E→FJ \colon E \to F is a continuous linear map between real Hilbert spaces with adjoint J*:F→EJ^* \colon F \to E and a>0a > 0 is a constant satisfying a∥x∥2≤∥Jx∥2a\|x\|^2 \le \|Jx\|^2 for every x∈Ex \in E, the Gram operator J*J:E→EJ^* J \colon E \to E of JJ is the bijective continuous linear operator J*∘JJ^* \circ J✦, and the left pseudoinverse J+:F→EJ^+ \colon F \to E of JJ is the continuous linear map (J*J)−1J*(J^* J)^{-1} J^*.✦

Given real normed spaces EE and FF together with continuous linear maps J:E→FJ \colon E \to F, B:F→EB \colon F \to E, and the identity operator IFI_F on FF, the residual operator I−JB:F→FI - JB \colon F \to F of JJ and BB is the continuous linear operator on FF given by IF−J∘BI_F - J \circ B.✦

For natural numbers SS and NN, a family of vectors g=(gt,i)g = (g_{t,i}) in a real inner-product space EE (1≤t≤S1 \le t \le S, 1≤i≤N1 \le i \le N), continuous linear maps B=(Bt)t=1SB = (B_t)_{t=1}^S from ℓ2N\ell_2^N to EE, real parameters q,k,ε∈ℝq, k, \varepsilon \in \mathbb{R}, a chart index 1≤s≤S1 \le s \le S, and a point x∈ℓ2Nx \in \ell_2^N, the chart coordinate αs,xg,B,q,k,ε:{1,…,S}×{1,…,N}→ℝ\alpha_{s,x}^{g,B,q,k,\varepsilon} \colon \{1,\dots,S\} \times \{1,\dots,N\} \to \mathbb{R} is the function given by (4): αs,xg,B,q,k,ε(t,i)={kε(xi−⟨gt,i,Bsx⟩q)if t=s,0if t≠s.\alpha_{s,x}^{g,B,q,k,\varepsilon}(t, i) = \begin{cases} \dfrac{k}{\varepsilon}\left(x_i - \dfrac{\langle g_{t,i}, B_s x\rangle}{q}\right) & \text{if } t = s,\\[8pt] 0 & \text{if } t \neq s. \end{cases}(4)✦

Direction Families and Rounded Source Charts

Given NN vectors g=(g1,…,gN)g = (g_1, \dots, g_N) in a real inner-product space EE and a vector v∈Ev \in E, the empirical covariance 𝒞(g,v)∈ℝ\mathcal{C}(g,v) \in \mathbb{R} of gg at vv is the scalar 1N∑i=1N⟨v,gi⟩2\frac{1}{N}\sum_{i=1}^N \langle v, g_i \rangle^2✦, and for w∈Ew \in E, the empirical sine transform 𝒮(g,w)∈E\mathcal{S}(g,w) \in E of gg at ww is the vector 1N∑i=1Nsin⁡(⟨gi,w⟩)gi\frac{1}{N}\sum_{i=1}^N \sin(\langle g_i, w \rangle) g_i.✦

For a natural number NN, a threshold q∈ℝq \in \mathbb{R}, and a vector vv in a real inner-product space EE, the bad projection set ℬN(q,v)⊆EN\mathcal{B}_N(q, v) \subseteq E^N is the set of NN-tuples y=(y1,…,yN)∈ENy = (y_1, \dots, y_N) \in E^N such that |⟨v,yi⟩|>q|\langle v, y_i \rangle| > q for some 1≤i≤N1 \le i \le N.✦ For a natural number SS, any set XX, a subset A⊆XA \subseteq X, and an SS-tuple x=(x1,…,xS)∈XSx = (x_1, \dots, x_S) \in X^S, the number of bad samples ν(A,x)∈ℕ\nu(A, x) \in \mathbb{N} is the count |{s∈{1,…,S}:xs∈A}||\{s \in \{1, \dots, S\} : x_s \in A\}|.✦

A direction family ff in dimension m∈ℕm \in \mathbb{N} is an m3m^3-tuple g=(g1,…,gm3)g = (g_1, \dots, g_{m^3}) of m6m^6-tuples gs=(gs,1,…,gs,m6)g_s = (g_{s,1}, \dots, g_{s,m^6}) of vectors in mm-dimensional Euclidean space ℓ2m\ell_2^m satisfying five conditions: (i) m/2≤∥gs,i∥≤2m\sqrt{m}/2 \le \|g_{s,i}\| \le 2\sqrt{m} for all ss and ii; (ii) gs,a≠tgs,bg_{s,a} \neq t g_{s,b} for every ss, distinct indices a≠ba \neq b, and t∈ℝt \in \mathbb{R}; (iii) 1/2≤𝒞(gs,v)≤21/2 \le \mathcal{C}(g_s, v) \le 2 for every ss and every unit vector v∈ℓ2mv \in \ell_2^m; (iv) ∥𝒮(gs,w)−e−∥w∥2/2w∥≤2/m\|\mathcal{S}(g_s, w) - e^{-\|w\|^2/2} w\| \le 2/\sqrt{m} for every ss and every w∈ℓ2mw \in \ell_2^m with ∥w∥≤m42\|w\| \le m^{42}; and (v) ν(ℬm6(11log⁡m,v),g)≤m3/2\nu(\mathcal{B}_{m^6}(11\sqrt{\log m}, v), g) \le m^3/2 for every unit vector v∈ℓ2mv \in \ell_2^m.✦ A pivoted direction family ff in dimension mm is a direction family in dimension mm whose coordinates satisfy |(gs,i)j|>m−30|(g_{s,i})_j| > m^{-30} for all 1≤s≤m31 \le s \le m^3, 1≤i≤m61 \le i \le m^6, and 1≤j≤m1 \le j \le m.✦

For a direction family f=(g1,…,gm3)f = (g_1, \dots, g_{m^3}) of m6m^6-tuples gs=(gs,1,…,gs,m6)g_s = (g_{s,1}, \dots, g_{s,m^6}) in positive dimension mm, the normalized direction family uu consists of the vectors us,i=gs,i/m∈ℓ2mu_{s,i} = g_{s,i}/\sqrt{m} \in \ell_2^m for 1≤s≤m31 \le s \le m^3 and 1≤i≤m61 \le i \le m^6, and the chart operator of chart ss is Js=Jus:ℓ2m→ℓ2m6J_s = J_{u_s} \colon \ell_2^m \to \ell_2^{m^6} for us=(us,1,…,us,m6)u_s = (u_{s,1}, \dots, u_{s,m^6}).✦ For a natural number mm, the frame lower bound constant ℓm∈ℝ\ell_m \in \mathbb{R} is m6/(2m)m^6/(2m)✦, and for a direction family ff in positive dimension mm and chart index 1≤s≤m31 \le s \le m^3, the chart pseudoinverse Bs:ℓ2m6→ℓ2mB_s \colon \ell_2^{m^6} \to \ell_2^m is the left pseudoinverse Js+J_s^+ of JsJ_s.✦

With N∈ℕN \in \mathbb{N}, vectors u=(u1,…,uN)∈ENu = (u_1, \dots, u_N) \in E^N in a real inner-product space EE, a grid scale τ∈ℝ\tau \in \mathbb{R}, and a point θ∈E\theta \in E, the integer chart label zu,τ(θ)∈ℤNz_{u,\tau}(\theta) \in \mathbb{Z}^N is the vector with ii-th coordinate (zu,τ(θ))i=⌊⟨ui,θ⟩/τ⌋(z_{u,\tau}(\theta))_i = \lfloor \langle u_i, \theta \rangle / \tau \rfloor for 1≤i≤N1 \le i \le N✦, and the rounded chart vector Xu,τ(θ)∈ℓ2NX_{u,\tau}(\theta) \in \ell_2^N is the vector in NN-dimensional Euclidean space with ii-th coordinate τ(zu,τ(θ))i\tau\,(z_{u,\tau}(\theta))_i for 1≤i≤N1 \le i \le N.✦

The Claim

Theorem 1.

  1. Rounded distance error. Let κ\kappa be a finite index set, let g:κ→Eg \colon \kappa \to E be a vector family in a real inner-product space EE, and let real scalars q,ε,a,b,A,R,Tq, \varepsilon, a, b, A, R, T satisfy q≥0q \ge 0, ε≥0\varepsilon \ge 0, 0<a≤b0 < a \le b, and A≥0A \ge 0. For any points θ,η,θ′,η′∈E\theta, \eta, \theta', \eta' \in E and coefficient functions α,β:κ→ℝ\alpha, \beta \colon \kappa \to \mathbb{R} such that |αi|≤A|\alpha_i| \le A and |βi|≤A|\beta_i| \le A for all i∈κi \in \kappa, ∥θ−θ′∥≤R\|\theta - \theta'\| \le R, ∥η−η′∥≤R\|\eta - \eta'\| \le R, and ∥η−θ∥≤T\|\eta - \theta\| \le T, the kernel distance satisfies (5): |Dg,q,ε,a,b(θ,η,α,β)−c*q∥η′−θ′∥|≤q(2a+T2b)+4ε|κ|log⁡ba+4ε|κ|(A2+2A)log⁡ba+2c*qR.\begin{aligned} \bigl|D_{g,q,\varepsilon,a,b}(\theta,\eta,\alpha,\beta) - c^* q\|\eta'-\theta'\|\bigr| &\le q\biggl(2a + \frac{T^2}{b}\biggr) + 4\varepsilon|\kappa|\log\frac{b}{a} \\ &\quad + 4\varepsilon|\kappa|(A^2+2A)\log\frac{b}{a} + 2c^* q R. \end{aligned}(5)✦

  2. Global angle lower bound. Given an index set ι\iota, a real inner-product space HH, a real normed space EE, maps P:ι→HP \colon \iota \to H and θ:ι→E\theta \colon \iota \to E (written Pv=P(v)P_v = P(v) and θv=θ(v)\theta_v = \theta(v)), and real constants c≥0c \ge 0 and e≥0e \ge 0 such that |∥Pv−Pw∥2−c∥θv−θw∥|≤e|\|P_v - P_w\|^2 - c\|\theta_v - \theta_w\|| \le e for all v,w∈ιv, w \in \iota, every triple v,z,y∈ιv, z, y \in \iota satisfies the inner-product lower bound (6): ⟨Pv−Pz,Py−Pz⟩≥−3e2.\langle P_v - P_z,\, P_y - P_z \rangle \ge -\frac{3e}{2}.(6)✦

  3. Local profile bound. For positive integers SS and NN, let g=(gs)s=1Sg = (g_s)_{s=1}^S be a family of NN-tuples gs=(gs,1,…,gs,N)g_s = (g_{s,1}, \dots, g_{s,N}) of vectors in a real inner-product space EE, and let B=(Bs)s=1SB = (B_s)_{s=1}^S be continuous linear maps Bs:ℓ2N→EB_s \colon \ell_2^N \to E. Suppose that real scalars q,k,ε,a,b,T,R,γq, k, \varepsilon, a, b, T, R, \gamma satisfy q>0q > 0, 0≤k≤10 \le k \le 1, ε>0\varepsilon > 0, 0<a≤b0 < a \le b, T≥0T \ge 0, R≥0R \ge 0, γ≥0\gamma \ge 0, and k=q2/Nk = q^2 / N, that ∥gs,i∥≤2q\|g_{s,i}\| \le 2q for all s,is, i, that ∥Bsei∥≤4k\|B_s e_i\| \le 4k for the standard basis vectors e1,…,eNe_1, \dots, e_N of ℓ2N\ell_2^N and all s,is, i, and that ∥e−∥w∥2/2w−𝒮(gs,w)∥≤γ\|e^{-\|w\|^2/2}w - \mathcal{S}(g_s, w)\| \le \gamma for all ss and all w∈Ew \in E with ∥w∥≤2T/a\|w\| \le 2T/a. Then for the scaled vector families q−1gs=(q−1gs,i)i=1Nq^{-1}g_s = (q^{-1}g_{s,i})_{i=1}^N, any chart indices 1≤s,t≤S1 \le s, t \le S, and points x,x′,y∈ℓ2Nx, x', y \in \ell_2^N satisfying ∥Bsx∥≤T\|B_s x\| \le T, ∥Bsx′∥≤T\|B_s x'\| \le T, ∥Bty∥≤T\|B_t y\| \le T, ∥(I−Jq−1gsBs)x∥≤R\|(I - J_{q^{-1}g_s} B_s)x\| \le R, ∥(I−Jq−1gsBs)x′∥≤R\|(I - J_{q^{-1}g_s} B_s)x'\| \le R, and ∥(I−Jq−1gtBt)y∥≤R\|(I - J_{q^{-1}g_t} B_t)y\| \le R, the kernel satisfies (7): |Kg,q,ε,a,b(Bsx′,Bty,αs,x′g,B,q,k,ε,αt,yg,B,q,k,ε)−Kg,q,ε,a,b(Bsx,Bty,αs,xg,B,q,k,ε,αt,yg,B,q,k,ε)|≤[(k+qγ(4k)+εSN9kεkRε)log⁡ba+εSN(2q)(4k)(1+(kR/ε)2+2(kR/ε))a]∑i=1N|xi′−xi|.\begin{aligned} &\bigl|K_{g,q,\varepsilon,a,b}\bigl(B_s x', B_t y, \alpha_{s,x'}^{g,B,q,k,\varepsilon}, \alpha_{t,y}^{g,B,q,k,\varepsilon}\bigr) \\ &\quad - K_{g,q,\varepsilon,a,b}\bigl(B_s x, B_t y, \alpha_{s,x}^{g,B,q,k,\varepsilon}, \alpha_{t,y}^{g,B,q,k,\varepsilon}\bigr)\bigr| \\ &\le \Biggl[\biggl(k + q\gamma(4k) + \varepsilon S N \frac{9k}{\varepsilon}\frac{kR}{\varepsilon}\biggr)\log\frac{b}{a} \\ &\qquad + \frac{\varepsilon S N (2q)(4k)\bigl(1 + (kR/\varepsilon)^2 + 2(kR/\varepsilon)\bigr)}{a}\Biggr] \sum_{i=1}^N |x'_i - x_i|. \end{aligned}(7)✦

  4. Rounded residual error. For a pivoted direction family ff in positive dimension mm, a positive grid scale τ\tau, a chart index 1≤s≤m31 \le s \le m^3, and a point θ∈ℓ2m\theta \in \ell_2^m, the rounded chart vector satisfies (8): ∥Xus,τ(θ)−Js(Bs(Xus,τ(θ)))∥≤m6τ.\bigl\|X_{u_s,\tau}(\theta) - J_s\bigl(B_s(X_{u_s,\tau}(\theta))\bigr)\bigr\| \le \sqrt{m^6}\,\tau.(8)✦

  5. Rounded reconstruction error. For a pivoted direction family ff in dimension m≥2m \ge 2, a positive grid scale τ\tau, a chart index 1≤s≤m31 \le s \le m^3, and a point θ∈ℓ2m\theta \in \ell_2^m, the chart pseudoinverse satisfies (9): ∥Bs(Xus,τ(θ))−θ∥≤m6τ.\bigl\|B_s\bigl(X_{u_s,\tau}(\theta)\bigr) - \theta\bigr\| \le \sqrt{m^6}\,\tau.(9)✦

What Is Checked

The five bounds are stated over real inner-product spaces EE and HH, an arbitrary index set ι\iota, a finite index set κ\kappa, the Hilbert kernel, the kernel distance, the profile constant c*c^*, chart operators, residual operators, chart coordinates, empirical sine transforms, and, for the rounded chart bounds, a pivoted direction family ff in positive dimension mm (with m≥2m \ge 2 for the reconstruction estimate) together with its normalized directions us,iu_{s,i}, chart pseudoinverses BsB_s, and rounded chart vectors Xus,τ(θ)X_{u_s,\tau}(\theta) (for τ>0\tau > 0 and θ∈ℓ2m\theta \in \ell_2^m). For a pivoted direction family ff in positive dimension mm, the frame lower bound constant ℓm\ell_m is strictly positive, and every chart operator JsJ_s satisfies the frame energy lower bound ∥Jsx∥2≥ℓm∥x∥2\|J_s x\|^2 \ge \ell_m \|x\|^2 for all x∈ℓ2mx \in \ell_2^m.✦