The Setting
Consider mapping points through linear charts, each built from direction vectors in , onto grid-rounded vectors , and then into a real Hilbert space 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 , lower bounds on pairwise inner products in from approximate squared-distance preservation, and local -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 onto a chart and mapping back by its left pseudoinverse.
The Hilbert Kernel and Kernel Distance
For a real inner-product space , a finite index set , a vector family , real scalars , points , and coefficient functions , the kernel pairing is the real number given by (1): (1)✦
Given a real inner-product space , a finite index set , a vector family , real parameters , points , and coefficient functions , the Hilbert kernel is the scale integral (2): (2)✦
Over a finite index set , a vector family in a real inner-product space , real parameters , points , and coefficient functions , the kernel distance is the real number defined by (3): (3)✦
The profile function is the function given by for and ✦, and the profile constant is the integral .✦
Chart Operators, Residuals, and Chart Extensions
To each family of vectors in a real inner-product space , the chart operator into -dimensional Euclidean space is the continuous linear map with -th coordinate for .✦
When is a continuous linear map between real Hilbert spaces with adjoint and is a constant satisfying for every , the Gram operator of is the bijective continuous linear operator ✦, and the left pseudoinverse of is the continuous linear map .✦
Given real normed spaces and together with continuous linear maps , , and the identity operator on , the residual operator of and is the continuous linear operator on given by .✦
For natural numbers and , a family of vectors in a real inner-product space (, ), continuous linear maps from to , real parameters , a chart index , and a point , the chart coordinate is the function given by (4): (4)✦
Direction Families and Rounded Source Charts
Given vectors in a real inner-product space and a vector , the empirical covariance of at is the scalar ✦, and for , the empirical sine transform of at is the vector .✦
For a natural number , a threshold , and a vector in a real inner-product space , the bad projection set is the set of -tuples such that for some .✦ For a natural number , any set , a subset , and an -tuple , the number of bad samples is the count .✦
A direction family in dimension is an -tuple of -tuples of vectors in -dimensional Euclidean space satisfying five conditions: (i) for all and ; (ii) for every , distinct indices , and ; (iii) for every and every unit vector ; (iv) for every and every with ; and (v) for every unit vector .✦ A pivoted direction family in dimension is a direction family in dimension whose coordinates satisfy for all , , and .✦
For a direction family of -tuples in positive dimension , the normalized direction family consists of the vectors for and , and the chart operator of chart is for .✦ For a natural number , the frame lower bound constant is ✦, and for a direction family in positive dimension and chart index , the chart pseudoinverse is the left pseudoinverse of .✦
With , vectors in a real inner-product space , a grid scale , and a point , the integer chart label is the vector with -th coordinate for ✦, and the rounded chart vector is the vector in -dimensional Euclidean space with -th coordinate for .✦
The Claim
Theorem 1.
Rounded distance error. Let be a finite index set, let be a vector family in a real inner-product space , and let real scalars satisfy , , , and . For any points and coefficient functions such that and for all , , , and , the kernel distance satisfies (5): (5)✦
Global angle lower bound. Given an index set , a real inner-product space , a real normed space , maps and (written and ), and real constants and such that for all , every triple satisfies the inner-product lower bound (6): (6)✦
Local profile bound. For positive integers and , let be a family of -tuples of vectors in a real inner-product space , and let be continuous linear maps . Suppose that real scalars satisfy , , , , , , , and , that for all , that for the standard basis vectors of and all , and that for all and all with . Then for the scaled vector families , any chart indices , and points satisfying , , , , , and , the kernel satisfies (7): (7)✦
Rounded residual error. For a pivoted direction family in positive dimension , a positive grid scale , a chart index , and a point , the rounded chart vector satisfies (8): (8)✦
Rounded reconstruction error. For a pivoted direction family in dimension , a positive grid scale , a chart index , and a point , the chart pseudoinverse satisfies (9): (9)✦
What Is Checked
The five bounds are stated over real inner-product spaces and , an arbitrary index set , a finite index set , the Hilbert kernel, the kernel distance, the profile constant , chart operators, residual operators, chart coordinates, empirical sine transforms, and, for the rounded chart bounds, a pivoted direction family in positive dimension (with for the reconstruction estimate) together with its normalized directions , chart pseudoinverses , and rounded chart vectors (for and ). For a pivoted direction family in positive dimension , the frame lower bound constant is strictly positive, and every chart operator satisfies the frame energy lower bound for all .✦