The Setting
In constructing a finite negative-type semimetric for the Goemans-Linial relaxation of uniform sparsest cut, a point set is partitioned into charts equipped with a within-chart distance, and one starts with vectors indexed by the points so that for all points , the inner product may fall below zero down to minus the chart separation truncated at a scale . The triangle repair problem is to find auxiliary Euclidean vectors so that the combined squared distances form a negative-type semimetric, while remains controlled at scale globally and small for pairs at small within-chart distance.
Definitions
Given a chart assignment from an index set to a chart set and a map into a normed space , the chart triangle inequality is the condition on that for all with , (1)✦
The capped distance associated with a chart assignment , a map into a normed space , and a real cap is the real-valued function on given by (2)✦
At a real parameter , the chart kernel of a chart assignment and a map into a normed space is the real matrix indexed by with entries (3)✦
For a chart assignment , a map into a normed space , and a real number , a map into the real Euclidean space on is a repair Gram representation of if for all , (4)✦ where is the chart kernel (3).
The Claim
Theorem 1. Let be a real inner product space, a normed space, a chart assignment from an index set to a chart set , and a map such that satisfies the chart triangle inequality (1). Suppose and satisfies for all , where is the capped distance (2). Then there exist maps into the real Euclidean space on such that is a repair Gram representation (4) of and, for all , (5)✦ where is the chart kernel (3).
In the paper, the result reads: if a finite set is partitioned into charts with a nonnegative multiple of an distance on each chart and for points in different charts, and if and Hilbert vectors satisfy for all , then there exist Hilbert vectors such that is a negative-type semimetric satisfying , together with when and when (here , , and stand for , , and ).
What Is Checked
The triangle repair claim (5) is stated over an index set , a chart set , a chart assignment , a map into a normed space satisfying the chart triangle inequality (1), a positive scale , and a map into a real inner product space satisfying the inner-product lower bound in terms of the capped distance (2), with conclusions in expressed using the chart kernel (3) and repair Gram representations (4).
Write for a positive-semidefinite real matrix indexed by . For every real inner product space , map , and , the Gaussian kernel satisfies (6)✦ Applying the exponential entrywise to any real matrix indexed by with gives (7)✦ If and is a family of real matrices indexed by such that for all and is integrable on for all , then (8)✦
Every real matrix indexed by with admits Gram vectors in the real Euclidean space on such that (9)✦
Whenever and , (10)✦ and when , (11)✦