Orthonormality of the coordinate planes of the selector construction
ProvedExactKMeans.ProductReduction.coordinate_frame_orthonormalcomplexity-theorycomputational-geometry
Let with and odd be the Section 5 parameters, and work in . The selector lives in the coordinate planes , , which occupy the first coordinates, and the last coordinate direction is the axis along which the selectors are placed.
- The vectors form an orthonormal family: and .
- Each and each is orthogonal to the axis, and is a unit vector.
- For all real coefficients and ,
These are the basic facts about the ambient coordinate system of the construction. Every selector point, the averaged vector , and the reference displacement are combinations of this form, so norms of means and cluster costs reduce to sums of squares of coefficients.
Formalization Note In the published definitions, , and are the standard unit vectors of in coordinates , and (zero-based, ), and denotes the Kronecker delta.
Preamble
import Definitions.Def_ExactKMeans_ProductReduction_Selector open scoped BigOperators Classical open Finset open ExactKMeans.ProductReduction
Formal statement
namespace ExactKMeans.ProductReduction
theorem coordinate_frame_orthonormal (p : Parameters) :
(∀ j k : Fin p.b, inner ℝ (e p j) (e p k) = if j = k then (1 : ℝ) else 0) ∧
(∀ j k : Fin p.b, inner ℝ (ep p j) (ep p k) = if j = k then (1 : ℝ) else 0) ∧
(∀ j k : Fin p.b, inner ℝ (e p j) (ep p k) = 0) ∧
(∀ j : Fin p.b, inner ℝ (e p j) (axis p) = 0 ∧ inner ℝ (ep p j) (axis p) = 0) ∧
inner ℝ (axis p) (axis p) = 1 ∧
∀ x y : Fin p.b → ℝ,
‖∑ j, (x j • e p j + y j • ep p j)‖ ^ 2 = ∑ j, (x j ^ 2 + y j ^ 2) := by sorry
end ExactKMeans.ProductReduction
Source
Bai, Fomin, Xu (2026), Exact Euclidean k-Means: Faster in the Plane, Hard Beyond It, held STOC 2027 submission; SHA-256 89f18334320ba73627305c6f8870ae70fef423ca012f8b71a3052e407c7e62ec, printed pp. 28–31 (PDF 29–32), Definitions 3–4: the b orthogonal coordinate planes with basis vectors e_j, e_j^⊥ and their normalized averages; used in the proof of Lemma 14, printed p. 31