A Geometric Analysis of Initialization Bias in Spherical $K$-means in the Weak Signal Regime

Amnon Balanov; Tamir Bendory

Source-linked AI summary

A Geometric Analysis of Initialization Bias in Spherical $K$-means in the Weak Signal Regime

Amnon Balanov, Tamir Bendory

arXiv:2609.02205v1Sep 2, 2026eess.SPcs.IT

TL;DR

The paper asks whether spherical K-means corrects initialized directions when directional observations are absent or weakly informative. It analyzes the uniform limit through Voronoi-cell centroids and extends the result to small positive concentration, finding quantified initialization alignment and an O(κ)-close population update.

Problem
The paper studies whether spherical K-means corrects initialized component directions when observations contain no or only weak directional information.
Method
The analysis uses the κ = 0 uniform experiment, Voronoi tessellations, normalized cell centroids, and one-step population-update geometry.
Results
O(K^-2/(d-1)) average and O((log K/K)^(2/(d-1))) worst-case squared geodesic errors quantify alignment for uniformly random initializations in fixed dimension.
Takeaways & Limitations
In the weak-signal regime, the population update remains close to the initialization-induced Voronoi-centroid map, preserving initialization-induced structure.
Takeaways & Limitations
The paper leaves finite-sample tracking, soft-assignment methods, and higher-dimensional repeated-update dynamics for future work.

Abstract

from arXiv · show

We study initialization bias in spherical $K$-means for weakly informative directional mixtures. We model the observations by a $K$-component von Mises-Fisher mixture with a small concentration parameter $κ$, corresponding to a high-dispersion regime in which the data provide limited information about the underlying directions. Our analysis begins with the limiting case $κ=0$ (corresponding to a uniform distribution over the sphere), where one population spherical $K$-means update is governed entirely by the Voronoi tessellation induced by the initialized templates. For uniformly random initializations in fixed dimension $d$, the updated templates become asymptotically aligned with their initial values as $K\to\infty$: the average squared geodesic error scales as $O(K^{-2/(d-1)})$, while the worst-case error is $O((\log K/K)^{2/(d-1)})$. We then show that, in the weak-signal regime of small positive $κ$, the population update remains an $O(κ)$ perturbation of this limiting map. Thus, in the weak-signal regime, spherical $K$-means can preserve initialization-induced structure despite the presence of a genuine but highly dispersed directional signal.

1. INTRODUCTION

The paper analyzes how initialization can shape spherical K-means when directional data are absent or weakly informative. In the uniform case, Voronoi geometry aligns population updates with initialized templates, and this persistence is quantitatively characterized as K grows.

Motivation: Weakly informative or signal-free data can leave iterative, nonconvex inference outputs aligned with initialization-induced hypotheses.Initialization determines early assignments or alignments, which can influence subsequent updates.
Uniform limiting case: At κ = 0, the vMF mixture becomes uniform on the sphere, providing a reference case with no directional signal.The analysis uses this limiting experiment to isolate initialization-induced bias.
Uniform limiting case: In the uniform population limit, initialized templates induce a spherical Voronoi tessellation, and each template updates toward its cell’s normalized centroid.The resulting output can remain aligned with initialized hypotheses rather than being determined by observation directions.
Fixed-dimensional rates: O(K^-2/(d-1)) average squared geodesic error and O((log K/K)^(2/(d-1))) worst-case squared error quantify alignment for uniformly random initializations in fixed dimension.These rates describe typical-cell and covering-radius behavior, respectively.
Weak-signal regime: For small positive κ, the population update remains close to the limiting Voronoi-centroid map, so initialization geometry remains a leading contribution.Figure 1(c) illustrates high alignment for small κ.
Two-dimensional dynamics: For d = 2, cyclic template gaps follow a discrete heat equation, with spectral gap of order K^-2 and relaxation time of order K^2.Repeated updates therefore converge toward uniformly spaced templates on the circle.

2. PROBLEM FORMULATION

The paper formulates spherical K-means for directional observations on the unit sphere and studies a uniform limiting experiment with initialized component directions. The algorithm alternates nearest-template assignments with normalized empirical-mean updates, analyzed here primarily through one population iteration.

2.1. The von Mises-Fisher mixture model: The directional model uses the unit sphere S^(d-1) with normalized surface measure and von Mises-Fisher components indexed by mean directions and concentration parameters.The concentration parameter controls concentration around a mean direction.
2.1. The von Mises-Fisher mixture model: At κ = 0, the von Mises-Fisher density is uniform on S^(d-1), while larger κ produces stronger concentration around µ.This establishes the paper’s no-signal reference model.
2.1. The von Mises-Fisher mixture model: The mixture is specified by component weights, mean directions, and concentrations, with the formulation allowing equal weights and shared concentration in the fitted model.The uniform limiting experiment fits a postulated K-component directional model despite a uniform true distribution.
2.2. The uniform limiting experiment: The uniform limiting experiment samples observations independently from the uniform sphere while fitting a K-component directional model initialized with hypothesized component directions.Its goal is to test whether observations correct the hypotheses or remain aligned with them.
2.3. Spherical K-means: Spherical K-means assigns each observation to the template with the largest inner product, equivalently the nearest template in angular distance.This is the hard-assignment step for equal-weight vMF estimation with common concentration.
2.3. Spherical K-means: Each template is then updated to the normalized empirical mean of its assigned observations, converting the assignment partition into updated directions.The procedure alternates assignment and normalized-mean updates.
2.4. Notation convention: The main analysis considers one assignment-update step, T = 1, and denotes the resulting population update as the n → ∞ limit of the empirical update.Initialized directions are abbreviated as µ_l during the single-step analysis.
2.4. Notation convention: For fixed templates, V_l denotes the spherical Voronoi cell generated by µ_l, and d_S(x,y) denotes geodesic distance on S^(d-1).These objects provide the geometric notation for the population update analysis.

3. RELATION TO THE GAUSSIAN MODEL AND FUNDAMENTAL PROPERTIES

The uniform spherical experiment provides a directional analogue of the pure-noise Gaussian confirmation-bias model. Its population update is a normalized Voronoi-cell centroid, preserving alignment with the initialized template and extending to high-dimensional many-template settings under cyclic decorrelation.

The uniform spherical experiment is the directional counterpart of the pure-noise Gaussian confirmation-bias model.
One population spherical K-means update equals the normalized conditional centroid of each initialization-induced Voronoi cell.The empirical update converges to the conditional centroid, followed by spherical normalization.
Gaussian and spherical hard assignment induce the same Voronoi partition because normalization preserves directional assignments.
Each population update remains in its generating template’s Voronoi cell and is at least as aligned with that template as with any other template.
For two templates, the population update has a closed-form expression obtained from the hemisphere Voronoi cells and their symmetry.
Under cyclic template correlations in a regime where both dimension and template count grow, each fixed-template update aligns asymptotically with its initialized template.

4. FIXED DIMENSION AND GROWING NUMBER OF TEMPLATES

In fixed dimension, increasing the number of randomly initialized templates refines the spherical Voronoi tessellation. The resulting population updates become increasingly aligned with their generating templates, with separate typical-cell and worst-cell rates.

In fixed dimension, increasing K makes Voronoi cells smaller and their normalized centroids closer to the generating templates.This geometric mechanism is relevant when many reference templates densely sample viewing directions and structural hypotheses.
The typical-cell analysis controls average alignment error over the K templates, while the worst-cell analysis controls the largest error simultaneously.
O((log K/K)^(2/(d-1))) is the worst-case squared alignment-error rate, controlled by the spherical covering radius.
O(K^-2/(d-1)) is the average squared geodesic alignment-error rate for uniformly random templates.
Increasing the number of postulated components makes the population update more aligned with initialization even when observations contain no cluster structure.
Figure 2 compares refining Voronoi tessellations with average-cell and worst-cell errors across dimensions d = 2, 3, 4, 5.The simulations use logarithmically spaced K values from 400 to 2000 and 30 independent trials per dimension-template-count pair.

5. CONSEQUENCES AND EXTENSIONS

The section extends the geometric analysis from one update to repeated iterations, weak nonzero concentration, and explicit circle dynamics, while identifying open directions for future work.

5.1. Multiple iterations: As K→∞, the first update becomes increasingly aligned with each generating template; if this persists across fixed T iterations, the T-th iterate remains asymptotically initialization-aligned.
5.2. Small nonzero concentration: For small κ, the vMF mixture is a perturbation of the uniform model, so the one-step population update remains O(κ)-close to the null Voronoi-centroid update.
5.3. Explicit population dynamics on the circle: On S1, each update locally averages neighboring template angles, inducing a discrete heat equation for the cyclic gaps.
5.3. Explicit population dynamics on the circle: As t→∞, the circle templates converge to a regular K-gon up to global rotation, while for t≪K^2 the initialized gap pattern remains close to its starting configuration.
5.4. Future work: Future work includes soft-assignment methods, finite-sample tracking, and higher-dimensional extensions of the explicit S1 dynamics.

A. RADIUS OF A SPHERICAL VORONOI CELL

This section quantifies the radius of a typical spherical Voronoi cell generated by uniformly random templates and derives its natural concentration scale.

The cell radius has an exponentially decaying tail at scale K^-1/(d-1), implying mean squared radius of order K^-2/(d-1).
Proposition A.1 considers K independent uniform templates on S^(d-1) and defines the radius of the cell generated by one template.
The stated bounds hold for fixed d≥2, sufficiently small radii, and constants depending only on d.

A.1. Notation and definitions

This section introduces the geometric tools used to analyze spherical Voronoi-cell radii, including geodesic sectors and their coverage of neighborhoods on the sphere.

The proof uses the Riemannian exponential map to represent nearby spherical points by a tangent direction and geodesic distance.
A finite ε-net of tangent directions generates truncated geodesic sectors around a template.
These sectors lie within the corresponding geodesic ball and collectively cover the punctured ball around the template.
The event E_j(r) records that a directional sector contains no competing template within distance r.

A.2. Auxiliary results

The auxiliary results connect Voronoi-cell extension to empty directional sectors and establish the geometric and probabilistic bounds needed for the radius estimate.

A sector of radius r has surface measure of order r^(d-1), so its probability of containing no competing template decays exponentially in K r^(d-1).
If a Voronoi cell extends beyond radius r, at least one directional sector must be empty of competing templates within that radius.
A closer competing template in the same approximate direction is strictly nearer to the cell point than the generating template, contradicting Voronoi membership.
The key geometric comparison is d_S(v,μ_k)<d_S(v,μ_0), which yields the contradiction required for the empty-sector criterion.

A.3. Proof of Proposition A.1

The proof combines conditional tail bounds, union bounds, and tail integration to derive the stated estimate, with an exponentially small remainder absorbed as negligible.

Proof of Proposition A.1: A conditional bound is obtained from Lemma A.3 and the union bound, uniformly over the relevant initialization parameter.The passage states the conditioning on µ0 and the range 0 < r ≤ rd.
Proof of Proposition A.1: Averaging over µ0 preserves the bound after using K − 1 ≥ K/2 for K ≥ 2 and absorbing constants depending only on d.Uniformity in µ0 permits the averaging step.
Proof of Proposition A.1: The second-moment estimate is derived by applying the tail integration formula to R0, whose values lie in [0, π].The displayed fragment identifies the integral representation used in this step.
Proof of Proposition A.1: For r ≥ rd, monotonicity of the tail probability is combined with (A.1) to control the remaining range.This extends the tail analysis beyond the initial range 0 < r ≤ rd.
Proof of Proposition A.1: The proof concludes after showing that the exponentially small remainder is negligible.This finalizes the estimate after combining the preceding bounds.