The Setting
Weighted control of gradient moments concerns averages over pairs of points. Coordinate embeddings require control of every pair at the same time, with a common scale.
Let and be finite sets of edges and vertices. For endpoint maps , the incidence matrix is defined by (1). (1)✦ For endpoint maps and real edge scales , the normalized gradient matrix is obtained by multiplying the incidence matrix on the left by the diagonal matrix with entries , as in (2). (2)✦ For any real matrix , write for its space of gradients.
For labelled points, the standard pair index is the set in (3), with endpoints and . (3)✦
For a real exponent and vectors , the coordinate distance is the quantity in (4). (4)✦
A strictly positive probability on a nonempty finite set is a vector in the set of (5). (5)
The weighted deviation of a moment vector from a level , with respect to a strictly positive probability on , is the real number in (6). (6)
For a measurable map on a probability space and a probability measure on , the th moment vectors and are vectors in given by (7) whenever the integrals exist. (7)
For and , an admissible sample size for is a positive integer for which and the sampling condition (8) holds. (8)
The Claim
Theorem 1. Let be a nonempty finite set and let .
Convex selection. Let be convex and let . Suppose that for every there is with . There is satisfying (9). (9)✦
Empirical moments. Let , and . Suppose that for every there is in the closed convex hull of with . For every admissible sample size for , there are satisfying (10). (10)✦
Gradient maps. Let , , and . Fix a probability space . Suppose that for every there is a measurable map such that for every and . For every admissible sample size for , there are vertex labels satisfying (11). (11)✦
Gradient measures. Under the same conditions on , suppose that for every there is a probability measure on such that a vector drawn according to satisfies and for every , almost surely, and . For every admissible sample size for , there are satisfying (12). (12)✦
Sampled vertex labels. For any , take and let be the normalized gradient matrix for positive lengths . Let , , and . Suppose that and that satisfy the moment bound in (11). The coordinate map from the labelled vertices to is defined by . There is such that (13) holds. (13)✦
Sampling probability. Let , and let be integers with and . Set and . The estimate is (14). (14)✦
In the paper, the result reads: in the finite coordinate setting, if and , and every admits a random normalized gradient with almost surely and , with the same for every , then the points embed into with distortion at most and for an absolute constant .
What Is Checked
The convex selection and sampling statements concern finite real coordinate spaces and probability moments; the embedding statement concerns positive pairwise lengths and the coordinate distance (4).