betaFeedback

WorksComputer Science

How Much Distribution Shift Can a Clustering Withstand? Exact Split and Merge Certificates for Structured Transports

Abstract

In clustering, the distribution of the population being clustered is often uncertain or changes over time, so the true distribution may shift away from the nominal distribution used to form the clustering. Once the clustering is committed and each member is assigned to a cluster, such shifts may change the distribution of each cluster. They can make a cluster too spread out for one representative at a given resolution, motivating a split, or bring distinct clusters close enough to share a representative at that resolution, motivating a merge. We make these split and merge events precise using a local stability criterion built on the phase-transition analysis in deterministic annealing. This notion of stability enables us to quantify how robust a clustering is against such events. Furthermore, motivated by applications in which uncertainty and population change are structured, we study shifts whose displacements are restricted to a prescribed subspace. The smallest structured shifts that reach the respective thresholds define the split and merge radii, for which we obtain exact semidefinite programming (SDP) reformulations. The split SDP has only two scalar decision variables. These convex reformulations enable us to combine the radii into a robustness certificate for the full clustering that gives the size of the smallest structured shift that reaches any monitored split or merge threshold.

Introduction

Clustering addresses a fundamental problem: how to represent or serve a population effectively with a limited number of representatives. This problem arises in applications ranging from data compression and learning to sensor coverage and resource allocation (Rose, 1998; Mavridis and Baras, 2023b,a; Cortes et al., 2004; Sharma et al., 2008; Bayati et al., 2025). A clustering partitions points in Rd\mathbb{R}^{d} into groups, each summarized by a representative or assigned a shared model, controller, or resource. The quality of this representation is commonly measured through distortion, typically defined as the average squared Euclidean distance between members and their representatives.

Once a clustering is committed, uncertainty in the original data (e.g., measurement errors) or later changes in the population may cause its distribution to differ from the nominal distribution used to form the clustering. We call this difference a distribution shift. Such a shift may change the number of representatives the population needs. A cluster may become too dispersed for one representative, motivating a split, or several clusters may come close enough to share one, motivating a merge. These revisions can incur both operational and computational costs: splitting may require additional resources, merging may require reconfiguring assignments or shared models, and finding a new globally optimal clustering is generally NP-hard [1]. It is therefore valuable to ask in advance: How much distribution shift can a labeled clustering withstand before a split or a merge is warranted?

To make this question precise, we must account for resolution: the number of representatives a population needs depends on the resolution at which it is viewed. At a coarse resolution, one representative may suffice for the entire population, whereas at a fine enough resolution, each distinct member of a finite population may need its own. Between these extremes, critical resolutions mark where a cluster splits into finer clusters or where several clusters merge into one. One way to formalize this notion of resolution is through deterministic annealing (DA), which uses a temperature parameter TT to balance distortion against the entropy of cluster assignments [19, 21]. The resulting objective is called the free energy. At sufficiently high temperatures, coincident representatives at the population mean form a local minimum of the free energy, resulting in a single effective cluster. As TT decreases, the resolution increases, and the coincident configuration undergoes a bifurcation at a critical temperature. Just below this temperature, the configuration becomes a saddle point, and separating the representatives along certain directions lowers the free energy, allowing distinct clusters to emerge and reveal finer structure in the population [19]. We refer to this local behavior as the stability of a distribution at temperature TT (Definition 1), which we apply to individual clusters and to collections of clusters.

To assess a given clustering without changing its assignments, we keep cluster labels attached to population members as the distribution shifts, preserving each cluster’s mass. At a fixed temperature TT, a distribution reaches the stability threshold when TT is its critical temperature. A split event occurs when a shift brings a cluster’s initially stable distribution to this threshold, and a merge event occurs when a shift brings a specified collection’s initially unstable pooled distribution to it. The events to monitor, for example splits of selected clusters or only pairwise merges, are prescribed by the application. For squared Euclidean distortion, Rose’s phase-transition analysis [19] gives the second-order stability criterion λmax⁡(C(q))<T/2\lambda_{\max}(C(q)) < T/2, where C(q)C(q) is the covariance of the distribution qq, with equality defining the stability threshold. This criterion involves only the covariance of the distribution being tested, so it can be used to assess a clustering regardless of how that clustering was obtained.

Quantifying the distance to a stability threshold requires specifying which population shifts are allowed and how their magnitude is measured. We measure a distribution shift by the square root of the smallest expected squared Euclidean displacement needed to transport the nominal distribution to the shifted distribution. Without restrictions on the displacements, this is the 2-Wasserstein distance [18].

In many applications, shifts are structured. For instance, disturbances and attacks in cyber-physical systems act through specific actuator or sensor channels [9], changes in feature vectors may affect only selected attributes while others remain fixed [22], and adversarial image perturbations may be restricted to a low-frequency subspace [12]. We model this structure by requiring displacements to lie in a prescribed linear subspace U⊆Rd\mathcal{U} \subseteq\mathbb{R}^{d}, with U=Rd\mathcal{U} = \mathbb{R}^{d} recovering unrestricted shifts. The split radius and merge radius are the smallest structured shifts, measured by this transport distance, that reach the respective events. These radii quantify the robustness of individual clusters or collections to specific events. To assess the clustering as a whole, we combine them into an overall robustness measure. Here, we adopt a worst-case approach: we define a transport distance for the entire labeled population and use the distance to the nearest monitored event as a robustness certificate. Every smaller structured shift is guaranteed to avoid all monitored events.

Such a certificate can also help compare candidate clusterings before deployment. Figure 1 compares two clusterings of the same population with identical nominal distortion. Under horizontal shifts at the same temperature, A’s split radius is more than three times B’s, revealing a substantial difference in robustness that distortion alone cannot capture. Comparing certificates across choices of U\mathcal{U} shows how a clustering’s robustness depends on the allowed displacement directions.

Figure 1. Two clusterings of the same population with identical distortion need very different horizontal shifts to reach the split threshold. (a), (b) Candidate clusterings A and B; stars mark the cluster centroids. (c), (d) Minimum-cost horizontal shifts that bring one cluster in each clustering to the split threshold at the same TT; grey shows the nominal cluster and v⋆\mathbf{v}^{\star} the split direction. The threshold is reached when the covariance ellipse, with longest semiaxis λmax⁡(C(q))\sqrt{\lambda_{\max}(C(q))}, touches the dotted circle of radius T/2\sqrt{T/2}. (e) Histograms of point displacement magnitudes under the shifts in (c) and (d); each split radius is the corresponding root-mean-square displacement.

Structured shifts introduce a geometric difficulty: restricting displacements to U\mathcal{U} does not restrict the direction of instability to U\mathcal{U} (notice how v∗v^{*} is not aligned with U\mathcal{U} in Figure 1(c)). Displacements within U\mathcal{U} can change the variance along directions with components in both U\mathcal{U} and U⊥\mathcal{U}^{\perp}, so the structured problem cannot generally be solved by projecting the unrestricted problem onto U\mathcal{U}. However, these displacements leave each point’s component in U⊥\mathcal{U}^{\perp} unchanged. Thus, a collection whose variance along some direction in U⊥\mathcal{U}^{\perp} already exceeds the threshold T/2T/2 cannot reach the merge threshold at any transport budget. An initially stable cluster, on the other hand, can always reach the split threshold when U≠{0}\mathcal{U} \ne\{0\}.

For fixed TT and U\mathcal{U}, we show that each event radius depends only on the covariance of the tested cluster or pooled collection. Our contributions are fourfold:

  1. Exact moment reduction. We reduce the split and merge radius problems from optimization over infinite-dimensional structured transport plans to finite-dimensional optimization over the displacement covariance and the cross-covariance between nominal points and their displacements. The reduction is exact: every feasible pair of moments is realized by a structured transport plan. The results hold for arbitrary nominal distributions with finite second moments.

  1. Split radius. For each feasible direction, we derive the minimum structured transport cost needed to reach the split threshold along it. Although minimizing this cost over directions is nonconvex, we compute the squared split radius through an exact SDP reformulation with two scalar decision variables. We recover an optimal split direction and construct an attaining structured transport plan.

  1. Merge radius. For a specified collection of clusters, we formulate the squared merge radius as an exact SDP. We show that a merge is feasible if and only if the nominal pooled distribution has variance at most T/2T/2 along every direction in U⊥\mathcal{U}^{\perp}. Whenever this condition holds, a deterministic affine structured transport map attains the minimum cost.

  1. Clustering certificate. We define a label-preserving structured transport distance on clusterings and show that the distance to the nearest monitored event equals the minimum of the event radii, each scaled by the square root of the affected population mass. If this certificate is finite, an attaining

distribution shift exists which can cause at least one of the monitored events to happen, provided its corresponding transport budget.

Related work. The interpretation of DA temperature as resolution is also used by Srivastava et al. [21] to assess clusterings through the range of resolutions over which they persist, and by online DA methods to progressively increase model complexity (Mavridis and Baras [15]). While these works vary the resolution, we ask a complementary question: with the clustering and resolution fixed, what is the smallest distribution shift that reaches a split or merge threshold?

Resampling stability asks whether rerunning an algorithm on a new sample produces the same partition ([5] (von Luxburg 2010)), and perturbation stability assumes that an optimal clustering must remain unchanged under bounded multiplicative perturbations of pairwise distances ([2]). Our certificate concerns prescribed split and merge events for a given labeled clustering, without requiring optimality or rerunning the algorithm.

Wasserstein distributionally robust optimization (DRO) chooses decisions that minimize worst-case expected cost over a Wasserstein ball ([17, 11]). For kk-means clustering, Malik et al. [13] use this framework to design representatives that minimize worst-case distortion under a prescribed shift budget. We instead assess a given clustering and quantify its robustness, rather than designing representatives.

Our use of displacement covariances and cross-covariances between nominal points and their displacements is related to moment formulations in covariance steering ([7, 3]). Our setting differs from transport between spaces of unequal dimensions ([16]), as both nominal and shifted distributions lie in Rd\mathbb{R}^{d}, while their displacements are restricted to a subspace U\mathcal{U}. Lastly, our transport plans preserve cluster labels and each point’s component in U⊥\mathcal{U}^{\perp}. The resulting distance is therefore a conditional Wasserstein distance in the sense of Chemseddine et al. [6], conditioned on the label and the unchanged orthogonal component.

Notation. Vector norms are Euclidean, IdI_d is the identity matrix, and Sd\mathbb{S}^{d} denotes the real symmetric d×dd \times d matrices. For A,B∈SdA, B \in\mathbb{S}^{d}, λmax⁡(A)\lambda_{\max}(A) is the largest eigenvalue of AA, and A⪯BA \preceq B means that B−AB-A is positive semidefinite. We denote the Moore–Penrose pseudoinverse by A†A^{\dagger}. For a set EE, 2E2^{E} denotes its power set, the collection of all subsets of EE. The set P2(Rd)\mathcal{P}_{2}(\mathbb{R}^{d}) consists of probability distributions with finite second moments; μ(q)\mu(q) and C(q)C(q) denote the mean and covariance of qq. For q0,q∈P2(Rd)q_{0},q \in\mathcal{P}_{2}(\mathbb{R}^{d}), Γ(q0,q)\Gamma(q_{0},q) denotes the set of couplings, or transport plans, of q0q_{0} and qq, i.e., probability distributions on Rd×Rd\mathbb{R}^{d} \times\mathbb{R}^{d} with first marginal q0q_{0} and second marginal qq. The squared 2-Wasserstein distance is

W22(q0,q):=inf⁡γ∈Γ(q0,q)∫∥z−x∥2 γ(dx,dz).(1)W_{2}^{2}(q_{0},q) := \inf_{\gamma\in\Gamma(q_{0},q)} \int\lVert z-x\rVert^{2}\,\gamma(dx,dz). \tag*{(1)}

Background and Problem Formulation

Clustering and free energy. Squared-error clustering chooses representatives Y=(y1,…,yk)Y=(y_{1},\ldots,y_{k}) to minimize the distortion D(Y;q):=∫min⁡j∥x−yj∥2 q(dx)D(Y;q) := \int\min_{j} \lVert x-y_{j}\rVert^{2}\,q(dx), corresponding to assigning each point to one (the nearest) representative. Deterministic annealing (DA) replaces these binary assignments with probabilities and subtracts T>0T>0 times their entropy. Minimizing the resulting free energy ([19]) over the assignment probabilities gives

FT(Y;q):=−T∫log⁡(∑j=1ke−∥x−yj∥2/T)q(dx).(2)F_{T}(Y;q) := -T \int\log\left(\sum_{j=1}^{k} e^{-\lVert x-y_{j}\rVert^{2}/T}\right)q(dx). \tag*{(2)}

As T↓0T \downarrow0, FT(Y;q)F_T(Y;q) converges to D(Y;q)D(Y;q), uniformly in YY. (see Appendix § 6).

Following the DA formulation, we fix a temperature T>0T > 0 to specify the resolution and use the free energy to decide when a single representative at the mean is locally optimal for a distribution. Concretely, for q∈P2(Rd)q \in\mathcal{P}_2(\mathbb{R}^d), we place k≥2k \ge2 representatives at μ(q)\mu(q) and ask whether slightly separating them lowers the free energy (2). This coincident configuration Yμ(q):=(μ(q),…,μ(q))Y_{\mu(q)} := (\mu(q),\ldots,\mu(q)) is always first-order stationary, i.e., ∇YFT(Yμ(q);q)=0\nabla_Y F_T(Y_{\mu(q)};q) = 0 (Appendix § 9.§ 1), so we examine its Hessian.

Definition 1 (Stability). At temperature T>0T > 0 and for any k≥2k \ge2, a distribution q∈P2(Rd)q \in\mathcal{P}_2(\mathbb{R}^d) is stable if ∇Y2FT(Yμ(q);q)≻0\nabla_Y^2 F_T(Y_{\mu(q)};q) \succ0, unstable if this Hessian has a negative eigenvalue, and critical if it is positive semidefinite but singular (we call it critical because TT is then its critical temperature).

This classification does not depend on kk (see Lemma 2), and critical distributions are exactly those at the stability threshold.

A split event occurs when an initially stable cluster distribution reaches the stability threshold, and a merge event occurs when the initially unstable pooled distribution of a collection reaches it. Both events include critical distributions, since an arbitrarily small (unrestricted) perturbation of a critical qq in the 2-Wasserstein sense can make it stable (e.g., a contraction about its mean) or unstable (e.g., an expansion). The covariance criterion in Lemma 2 makes this clear.

To determine which shifts can reach these thresholds and at what cost, we first define structured transport plans. Let U⊆Rd\mathcal{U} \subseteq\mathbb{R}^d be a prescribed linear subspace with U≠{0}\mathcal{U} \ne\{0\}. A transport plan is U\mathcal{U}-structured if its displacements lie in U\mathcal{U} almost surely. For q0,q∈P2(Rd)q_0,q \in\mathcal{P}_2(\mathbb{R}^d), define

ΓU(q0,q):={γ∈Γ(q0,q):z−x∈U for γ-a.e. (x,z)},(3)\Gamma_{\mathcal{U}}(q_0,q) := \left\{\gamma\in\Gamma(q_0,q) : z-x \in\mathcal{U}\ \text{for }\gamma\text{-a.e. }(x,z)\right\}, \tag*{(3)}

and the structured transport distance

W2,U2(q0,q):=inf⁡γ∈ΓU(q0,q)∫∥z−x∥2 γ(dx,dz),(4)W_{2,\mathcal{U}}^2(q_0,q) := \inf_{\gamma\in\Gamma_{\mathcal{U}}(q_0,q)} \int\lVert z-x\rVert^2 \,\gamma(dx,dz), \tag*{(4)}

the least cost of transporting q0q_0 to qq with U\mathcal{U}-structured plans. We use the convention inf⁡∅=+∞\inf\varnothing= +\infty; for U=Rd\mathcal{U} = \mathbb{R}^d, W2,U=W2W_{2,\mathcal{U}} = W_2. The distance is finite if and only if q0q_0 and qq have the same marginal on U⊥\mathcal{U}^{\perp}, and if so, an optimal plan exists. When the U⊥\mathcal{U}^{\perp} marginals agree, W2,UW_{2,\mathcal{U}} is the conditional Wasserstein distance of Chemseddine et al. [6], with the U⊥\mathcal{U}^{\perp}-component as the conditioning variable. Appendix § 7 proves both facts (Lemma 7) and makes this connection precise.

The Split and Merge Problems. For a nominal cluster distribution q0∈P2(Rd)q_0 \in\mathcal{P}_2(\mathbb{R}^d), the split radius is

ρs,U(q0;T):=inf⁡q∈P2(Rd){W2,U(q0,q):∇Y2FT(Yμ(q);q)≠0},(5)\rho_{s,\mathcal{U}}(q_0;T) := \inf_{q \in\mathcal{P}_2(\mathbb{R}^d)} \left\{ W_{2,\mathcal{U}}(q_0,q) : \nabla_Y^2 F_T(Y_{\mu(q)};q) \ne0 \right\}, \tag*{(5)}

which is positive when q0q_0 is stable. Similarly, for the nominal pooled distribution q0∈P2(Rd)q_0 \in\mathcal{P}_2(\mathbb{R}^d) of a collection of clusters, the merge radius is

ρm,U(q0;T):=inf⁡q∈P2(Rd){W2,U(q0,q):∇Y2FT(Yμ(q);q)⪰0},(6)\rho_{m,\mathcal{U}}(q_0;T) := \inf_{q \in\mathcal{P}_2(\mathbb{R}^d)} \left\{ W_{2,\mathcal{U}}(q_0,q) : \nabla_Y^2 F_T(Y_{\mu(q)};q) \succeq0 \right\}, \tag*{(6)}

which is positive when q0q_0 is unstable. Both radii equal zero when q0q_0 is critical.

The radii above quantify the robustness of a single cluster to splitting or of a collection of clusters to merging into one. To assess the whole clustering against a set of monitored events, we need a distance on population shifts that accounts for each cluster’s displacement and mass.

Consider a labeled clustering with MM clusters, indexed by [M]:={1,…,M}[M] := \{1,\ldots,M\}. Let mj>0m_j > 0 denote the mass of cluster jj, i.e., its fraction of the population, with ∑jmj=1\sum_j m_j = 1, and let q~0j,q~j∈P2(Rd)\tilde q_0^j,\tilde q^j \in\mathcal{P}_2(\mathbb{R}^d) denote the nominal and shifted distributions conditional on the cluster label jj. Write q0:=(q01,…,q0M)\mathbf{q}_0 := (q_0^1,\ldots,q_0^M) and q:=(q1,…,qM)\mathbf{q} := (q^1,\ldots,q^M) for the corresponding tuples of cluster distributions. Since labels stay attached to the transported mass, each mjm_j is preserved, and each cluster moves by its own U\mathcal{U}-structured plan. The population transport cost is the mass-weighted sum of the cluster transport costs. For fixed shifted distributions, the plans can be optimized independently, so the minimum population cost is the mass-weighted sum of the minimum cluster costs. We therefore define the label-preserving U\mathcal{U}-structured transport distance

WU2(q0,q):=∑j=1MmjW2,U2(q0j,qj).(7)W_{\mathcal{U}}^2(\mathbf{q}_0,\mathbf{q}) := \sum_{j=1}^{M}m_j W_{2,\mathcal{U}}^2(q_0^j,q^j). \tag*{(7)}

When finite, it is a conditional 2-Wasserstein distance, conditioned on both the cluster label and the unchanged U⊥\mathcal{U}^{\perp}-component.

Let S⊆[M]\mathcal{S}\subseteq[M] index the clusters monitored for splitting, and let A⊆2[M]\mathcal{A}\subseteq2^{[M]} be the family of collections monitored for merging, with ∣A∣≥2|A|\geq2 for every A∈AA\in\mathcal{A}. For each such collection, define its mass and nominal pooled distribution by

mA:=∑j∈Amj,q0A:=∑j∈AmjmAq0j.(8)m_A := \sum_{j\in A}m_j,\qquad q_0^A := \sum_{j\in A}\frac{m_j}{m_A}q_0^j. \tag*{(8)}

At temperature TT, we assume that q0jq_0^j is stable for every j∈Sj\in\mathcal{S}, and q0Aq_0^A is unstable for every A∈AA\in\mathcal{A}. We define the clustering’s robustness certificate as its WUW_{\mathcal{U}}-distance to the nearest monitored event. This distance is exactly

RU(q0;T)=min⁡{min⁡j∈Smj ρs,U(q0j;T), min⁡A∈AmA ρm,U(q0A;T)}.(9)R_{\mathcal{U}}(\mathbf{q}_0;T)=\min\left\{\min_{j\in\mathcal{S}}\sqrt{m_j}\,\rho_{s,\mathcal{U}}(q_0^j;T),\ \min_{A\in\mathcal{A}}\sqrt{m_A}\,\rho_{m,\mathcal{U}}(q_0^A;T)\right\}. \tag*{(9)}

since the minimum cost of reaching an event is achieved by moving only the clusters involved in it. A structured shift that splits cluster jj has WUW_{\mathcal{U}}-distance from q0\mathbf{q}_0 of at least mjρs,U(q0j;T)\sqrt{m_j}\rho_{s,\mathcal{U}}(q_0^j;T), with equality for the shift that moves cluster jj by a plan attaining its split radius (which exists by Theorem 6) and leaves the other clusters unchanged. Likewise, a structured shift that brings the pooled distribution of AA to or beyond the merge threshold has WUW_{\mathcal{U}}-distance of at least mAρm,U(q0A;T)\sqrt{m_A}\rho_{m,\mathcal{U}}(q_0^A;T), with equality, when this radius is finite, for the shift that moves the clusters in AA by a plan that attains the merge radius of q0Aq_0^A (which exists by Proposition 4) and leaves the other clusters unchanged. Appendix § 8 gives the formal argument, including the decomposition of this pooled plan into individual cluster plans.

Consequently, every structured shift with WU(q0,q)<RU(q0;T)W_{\mathcal{U}}(\mathbf{q}_0,\mathbf{q})<R_{\mathcal{U}}(\mathbf{q}_0;T) avoids all monitored events, and when RU(q0;T)R_{\mathcal{U}}(\mathbf{q}_0;T) is finite, some shift at this distance reaches at least one of the events. Computing the robustness certificate therefore reduces to solving the split and merge radius problems (5)–(6), which we investigate next.

Main Results: Split and Merge Radii and SDP Reformulations

The phase-transition analysis of Rose [19] turns the Hessian conditions of DA stability (Definition 1) into conditions on the covariance matrix, which we state in our notation as the following lemma. All proofs for this section are given in Appendix § 9.

Lemma 2 ([19]). Let q∈P2(Rd)q\in\mathcal{P}_2(\mathbb{R}^d), T>0T>0, and k≥2k\geq2. Then

∇Y2FT(Yμ(q);q)⪰0⟺C(q)⪯T2Id.(10)\nabla_Y^2 F_T(Y_\mu(q);q)\succeq0 \quad\Longleftrightarrow\quad C(q)\preceq\frac{T}{2}I_d. \tag*{(10)}

with strict positive definiteness of the left-hand side if and only if the inequality on the right-hand side is strict. Hence qq is stable, critical, or unstable depending on whether λmax⁡(C(q))\lambda_{\max}(C(q)) is less than, equal to, or greater than T/2T/2, independently of kk.

Proof. The proof is given in Appendix § 9.§ 1.

We now incorporate the subspace constraint into the displacement coordinates. Let ℓ:=dim⁡U\ell:= \dim\mathcal{U}, and let B∈Rd×ℓB \in\mathbb{R}^{d \times\ell} have orthonormal columns spanning U\mathcal{U}. Since columns of BB form a basis for U\mathcal{U}, every structured displacement is uniquely represented as z−x=Bδz-x = B\delta. We therefore optimize over displacement plans, which are the joint distributions of nominal points and their displacement coordinates

Π(q0):={π∈P2(Rd×Rℓ):π(⋅×Rℓ)=q0}.\Pi(q_0) := \left\{ \pi\in\mathcal{P}_2(\mathbb{R}^d \times\mathbb{R}^{\ell}) : \pi(\cdot\times\mathbb{R}^{\ell}) = q_0 \right\}.

For (X,Δ)∼π(X,\Delta) \sim\pi, let qπq_\pi be the distribution of Z=X+BΔZ = X+B\Delta. This construction gives a one-to-one correspondence between any U\mathcal{U}-structured transport plan γ∈ΓU(q0,q)\gamma\in\Gamma_{\mathcal{U}}(q_0,q) and its displacement plan π∈Π(q0)\pi\in\Pi(q_0), with qπ=qq_\pi= q. The inverse is Δ=BT(Z−X)\Delta= B^{\mathsf{T}}(Z-X), and the correspondence preserves cost because ∥Z−X∥2=∥Δ∥2\lVert Z-X\rVert^2 = \lVert\Delta\rVert^2. Using Lemma 2, the split and merge problems therefore become

ρe,U2(q0;T)=inf⁡π∈Π(q0){∫∥δ∥2 π(dx,dδ):C(qπ)∈Ee},e∈{s,m},(11)\rho^2_{e,\mathcal{U}}(q_0;T) = \inf_{\pi\in\Pi(q_0)} \left\{ \int\lVert\delta\rVert^2 \,\pi(\mathrm{d}x,\mathrm{d}\delta) : C(q_\pi) \in\mathcal{E}_e \right\}, \qquad e \in\{s,m\}, \tag*{(11)}

where Es:={C:λmax⁡(C)≥T/2}\mathcal{E}_s := \{C : \lambda_{\max}(C) \ge T/2\} and Em:={C:C⪯(T/2)Id}\mathcal{E}_m := \{C : C \preceq(T/2)I_d\}. Without loss of generality, we restrict the problems above to displacement plans with zero displacement mean, since otherwise centering the displacements leaves C(qπ)C(q_\pi) unchanged and strictly reduces the cost.

Let μ0:=μ(q0)\mu_0 := \mu(q_0) and C0:=C(q0)C_0 := C(q_0). For (X,Δ)∼π(X,\Delta) \sim\pi with Eπ[Δ]=0\mathbb{E}_\pi[\Delta] = 0, define

K:=Eπ[(X−μ0)ΔT]∈Rd×ℓ,S:=Eπ[ΔΔT]∈Rℓ×ℓ(12)K := \mathbb{E}_\pi\left[(X-\mu_0)\Delta^{\mathsf{T}}\right] \in\mathbb{R}^{d \times\ell}, \qquad S := \mathbb{E}_\pi\left[\Delta\Delta^{\mathsf{T}}\right] \in\mathbb{R}^{\ell\times\ell} \tag*{(12)}

for the cross-covariance between nominal points and their displacements and the displacement covariance, respectively. Furthermore, define

M(C0):={(K,S)∈Rd×ℓ×Sℓ:(C0KKTS)⪰0},\mathcal{M}(C_0) := \left\{(K,S) \in\mathbb{R}^{d \times\ell} \times\mathbb{S}^{\ell} : \begin{pmatrix} C_0 & K \\ K^{\mathsf{T}} & S \end{pmatrix} \succeq0 \right\},
CB(K,S):=C0+KBT+BKT+BSBT.(13)C_B(K,S) := C_0 + KB^{\mathsf{T}} + BK^{\mathsf{T}} + BSB^{\mathsf{T}}. \tag*{(13)}

Proposition 3. The split and merge radii problems are equivalent to

ρs,U2(q0;T)=inf⁡(K,S)∈M(C0){tr⁡S:λmax⁡(CB(K,S))≥T/2},(14)\rho^2_{s,\mathcal{U}}(q_0;T) = \inf_{(K,S)\in\mathcal{M}(C_0)} \left\{\operatorname{tr} S : \lambda_{\max}(C_B(K,S)) \ge T/2\right\}, \tag*{(14)}
ρm,U2(q0;T)=inf⁡(K,S)∈M(C0){tr⁡S:CB(K,S)⪯(T/2)Id}.(15)\rho^2_{m,\mathcal{U}}(q_0;T) = \inf_{(K,S)\in\mathcal{M}(C_0)} \left\{\operatorname{tr} S : C_B(K,S) \preceq(T/2)I_d\right\}. \tag*{(15)}

Every feasible pair (K,S)(K,S) is realized by the joint law of (X,Δ)(X,\Delta), where X∼q0X \sim q_0 and Δ=KTC0†(X−μ0)+η\Delta= K^{\mathsf{T}}C_0^{\dagger}(X-\mu_0)+\eta, where η\eta is zero mean and independent of XX, with covariance S−KTC0†KS-K^{\mathsf{T}}C_0^{\dagger}K. If (K,S)(K,S) is optimal, the joint law of (X,X+BΔ)(X,X+B\Delta) is an optimal U\mathcal{U}-structured transport plan.

Proof. The proof is given in Appendix § 9.§ 2.

We next provide SDP formulations of both split (14) and merge (15) problems and characterize their feasibility, attainment, and optimal transport plans.

The Merge Problem. The merge problem (15) is an SDP. The following proposition characterizes its feasibility and shows that, when feasible, a deterministic affine map attains the minimum.

Proposition 4. Let PU⊥:=Id−BBTP_{\mathcal{U}^{\perp}} := I_d - BB^{\mathsf{T}} be the orthogonal projection onto U⊥\mathcal{U}^{\perp}. The merge problem (15) is feasible if and only if

PU⊥C0PU⊥⪯T2PU⊥.(16)P_{\mathcal{U}^{\perp}} C_0 P_{\mathcal{U}^{\perp}} \preceq\frac{T}{2} P_{\mathcal{U}^{\perp}} . \tag*{(16)}

Whenever feasible, the minimum is attained by a pair (K⋆,S⋆)(K^\star, S^\star) satisfying S⋆=(K⋆)TC0−1K⋆S^\star= (K^\star)^{\mathsf{T}} C_0^{-1} K^\star. The corresponding optimal U\mathcal{U}-structured transport plan is induced by the deterministic affine map x↦x+B(K⋆)TC0−1(x−μ0)x \mapsto x + B(K^\star)^{\mathsf{T}} C_0^{-1}(x-\mu_0).

Proof. The proof is given in Appendix § 9.§ 3.

The Split Problem. The split constraint in (14) is generally nonconvex, so the problem is not directly an SDP. It holds exactly when vTCB(K,S)v≥T/2v^{\mathsf{T}}C_B(K,S)v \ge T/2 for some unit vector vv. Fixing vv gives an SDP with a closed-form solution for the smallest shift needed to reach the split threshold along vv. Minimizing this quantity over unit directions yields the split radius and an optimal split direction.

Lemma 5. Let q0q_0 be stable at temperature T>0T>0, so that C0≺(T/2)IdC_0 \prec(T/2)I_d. For any unit direction v∉U⊥v \notin\mathcal{U}^{\perp}, the minimum structured shift needed to reach the split threshold along vv is

min⁡(K,S)∈M(C0){tr⁡S:vTCB(K,S)v≥T2}=(T/2−vTC0v)2∥BTv∥2.(17)\min_{(K,S)\in\mathcal{M}(C_0)} \left\{ \operatorname{tr} S : v^{\mathsf{T}}C_B(K,S)v \ge\frac{T}{2} \right\} = \frac{\left(\sqrt{T/2}-\sqrt{v^{\mathsf{T}}C_0v}\right)^2}{\lVert B^{\mathsf{T}}v\rVert^2}. \tag*{(17)}

It is feasible exactly when v∉U⊥v \notin\mathcal{U}^{\perp}, and the minimum is attained with vTCB(K,S)v=T/2v^{\mathsf{T}}C_B(K,S)v=T/2.

Proof. The proof is given in Appendix § 9.§ 4.

Notice that a unit direction v∉Uv \notin\mathcal{U} has ∥BTv∥<1\lVert B^{\mathsf{T}}v\rVert<1, which increases the directional cost, but a sufficiently small numerator can compensate and make it optimal (Figure 1). In particular, if U=Rd\mathcal{U}=\mathbb{R}^d, then ∥BTv∥=1\lVert B^{\mathsf{T}}v\rVert=1 for every unit vv, so the cost is minimized along the top eigenvector of C0C_0, giving ρs,U(q0;T)=T/2−λmax⁡(C0)\rho_{s,\mathcal{U}}(q_0;T)=\sqrt{T/2}-\sqrt{\lambda_{\max}(C_0)}. In general, minimizing this cost over unit directions is nonconvex, but the next theorem reformulates it exactly as an SDP.

Theorem 6. Let q0q_0 be stable at temperature T>0T>0. Then the squared split radius is given by the following SDP, which is feasible, and its maximum is always attained:

ρs,U2(q0;T)=max⁡η,τ≥0 η\rho_{s,\mathcal{U}}^2(q_0;T)=\max_{\eta,\tau\ge0}\ \eta
subject to(τ(T2Id−C0)−ηId−τC01/2B−τBTC01/2(1−τ)Iℓ)⪰0.(18)\text{subject to}\quad \begin{pmatrix} \tau\left(\frac{T}{2}I_d-C_0\right)-\eta I_d & -\tau C_0^{1/2}B \\ -\tau B^{\mathsf{T}}C_0^{1/2} & (1-\tau)I_{\ell} \end{pmatrix}\succeq0. \tag*{(18)}

Proof. The proof is given in Appendix § 9.§ 5, together with the recovery of an attaining split direction and its U\mathcal{U}-structured transport plan.

Numerical Experiments

S1–S3 benchmarks. We use the S1–S3 benchmarks of Fränti and Virmajoki [10]: 5000 points in R2\mathbb{R}^2 from 15 Gaussian clusters, with overlap increasing from S1 to S3. Each dataset is centered and normalized to unit root-mean-square norm. We obtain nominal clusterings by running Lloyd’s algorithm initialized at the supplied ground-truth centers; we then hold the labels fixed.

Figure 2 shows the representatives (stars), their Voronoi cells, the covariance ellipses, with semi-axes λi(Cj)\sqrt{\lambda_i(C_j)}, and concentric circles of radius T/2\sqrt{T}/2. By Lemma 2, a cluster is stable when its ellipse lies strictly inside its circle and reaches the split threshold when the two first touch. For a monitored merge, the analogous threshold is reached when the pooled covariance ellipse first fits inside the circle about its pooled mean; Figure 4 of the appendix illustrates attaining merge shifts.

Figure 2. Nominal clusterings S1–S3 at T=0.1T = 0.1.

Figure 4. Attaining shifts of the events realizing RUR_U at T=0.1T = 0.1 (events of Table 1). Each panel shows the nominal (grey) and shifted (black) covariance contours of the affected cluster or pooled pair; the shifted contours touch the T/2\sqrt{T/2} circles.

We monitor all 15 splits and the merges of neighboring clusters whose Voronoi cells share an edge. We pick T=0.1T = 0.1 from the common range of temperatures (approximately 0.0759<T<0.13150.0759 < T < 0.1315) for which every cluster is stable and the pooled distribution of every monitored pair is unstable in all three datasets. Table 1 reports the certificates and attaining events under unrestricted, horizontal, and vertical shifts (U=R2\mathcal{U} = \mathbb{R}^2, span⁡{e1}\operatorname{span}\{e_1\}, span⁡{e2}\operatorname{span}\{e_2\}); all radii in this section are in units of 10−310^{-3}. The radius SDPs are solved with Clarabel through CVXPY. In S1, merge {6,13}\{6, 13\} is the most vulnerable event under unrestricted shifts, with radius 12.08. Its two clusters are aligned nearly vertically, so vertical shifts attain almost the same radius (13.12), whereas under horizontal shifts the most vulnerable event becomes merge {3,9}\{3, 9\}, at almost twice the radius (23.38). In S3, split 9 is the most vulnerable event under all three choices of U\mathcal{U} at T=0.1T = 0.1. To examine the effect of resolution, we keep the S3 clustering and monitored events fixed and consider unrestricted shifts. As TT increases from 0.10 to 0.12, the minimum mass-weighted split radius rises from 7.23 to 12.59, while the minimum mass-weighted merge radius falls from 15.98 to 7.90. At this coarser resolution, merge {4,13}\{4, 13\} therefore replaces split 9 as the most vulnerable event. Appendix E gives event rankings, attaining shifts, and further results for S3 with its clusters moved farther apart.

DatasetEventRUR_{\mathcal{U}}EventRUR_{\mathcal{U}}EventRUR_{\mathcal{U}}
S1Merge {6,13}\{6, 13\}12.08Merge {3,9}\{3, 9\}23.38Merge {6,13}\{6, 13\}13.12
S2Merge {2,15}\{2, 15\}12.16Merge {2,15}\{2, 15\}16.69Merge {1,8}\{1, 8\}15.49
S3Split 97.23Split 98.96Split 98.54

Table 1. Certificates RUR_{\mathcal{U}} (units of 10−310^{-3}) and attaining events at T=0.1T = 0.1.

Higher-dimensional example: DIM64. To demonstrate the SDP formulations in higher dimensions, we consider the DIM64 benchmark from the same repository: 1024 points in R64\mathbb{R}^{64} from 16 clusters. We monitor all 16 splits and all 120 pairwise merges. Keeping the nominal clustering and T=0.1T = 0.1 fixed, we enlarge the admissible subspace Uℓ=span⁡{e1,…,eℓ}U_{\ell} = \operatorname{span}\{e_1, \ldots, e_{\ell}\} for ℓ∈{10,30,50,55,60,64}\ell\in\{10, 30, 50, 55, 60, 64\}, with ℓ=64\ell= 64 permitting unrestricted shifts. Since the subspaces UℓU_{\ell} are nested, the event radii are nonincreasing in ℓ\ell and the number of feasible merges is nondecreasing. Split 13 attains the certificate for every tested ℓ\ell, and the certificate decreases from 53.6 to 50.7. No merge is feasible for ℓ≤50\ell\le50, and all 120 are feasible at ℓ=64\ell= 64. Table 5 in Appendix § 10 gives the detailed setup and numerical results.

ℓ\ellWeighted splitWeighted mergeRUℓR_{U\ell}Attaining eventFeasible merges
100.053610∞\infty0.053610Split 130/120
300.052094∞\infty0.052094Split 130/120
500.051143∞\infty0.051143Split 130/120
550.0509810.1683480.050981Split 1320/120
600.0509510.1456840.050951Split 1396/120
640.0507490.1329860.050749Split 13120/120

Table 5. DIM64 at T=0.1T = 0.1: minimum mass-weighted split and merge radii, robustness certificates, and attaining events. All values are WUW_U distances in normalized coordinates; ∞\infty indicates that no monitored merge is feasible.

Conclusion and discussion

We used the phase-transition analysis of deterministic annealing to formalize split and merge thresholds at a prescribed resolution. We quantified the smallest structured distribution shifts reaching these thresholds, which we call the split and merge radii. We reformulated their computation as exact SDPs, and combined them into an exact robustness certificate for a given labeled clustering. This certificate equals the smallest structured population transport distance to any monitored event. Experiments on two-dimensional and higher-dimensional datasets demonstrated the computational tractability of the formulations and the effect of displacement restrictions on robustness.

The framework can be extended to more general distortions, such as Bregman divergences, and more general transport costs. Another direction is to consider a population evolving under underlying dynamics and design controls to steer its covariance toward desired split or merge thresholds or maintain robustness against unwanted ones, connecting the framework to covariance steering.

DA free energy

Let q∈P2(Rd)q \in\mathcal{P}_2(\mathbb{R}^d), and let Y=(y1,…,yk)Y=(y_1,\ldots,y_k) be a collection of representatives at fixed T>0T>0.

Entropy formulation. Let each point x∈Rdx\in\mathbb{R}^d be assigned to representative yjy_j with probability pj∣xp_{j|x}, where

p⋅∣x∈Δk:={p∈[0,1]k:∑j=1kpj=1}.p_{\cdot|x}\in\Delta_k:=\left\{p\in[0,1]^k:\sum_{j=1}^k p_j=1\right\}.

For representatives Y=(y1,…,yk)Y=(y_1,\ldots,y_k), define the expected distortion and conditional assignment entropy by

D(Y,p;q):=∫∑j=1kpj∣x∥x−yj∥2q(dx),H(p;q):=−∫∑j=1kpj∣xlog⁡pj∣xq(dx),D(Y,p;q):=\int\sum_{j=1}^k p_{j|x}\|x-y_j\|^2q(dx),\qquad H(p;q):=-\int\sum_{j=1}^k p_{j|x}\log p_{j|x}q(dx),

with 0log⁡0=00\log0=0. At temperature T>0T>0, the free energy is

FT(Y,p;q):=D(Y,p;q)−TH(p;q)=∫∑j=1kpj∣x(∥x−yj∥2+Tlog⁡pj∣x)q(dx).(19)\begin{aligned} F_T(Y,p;q):=D(Y,p;q)-TH(p;q) \\ &=\int\sum_{j=1}^k p_{j|x}\left(\|x-y_j\|^2+T\log p_{j|x}\right)q(dx). \tag*{(19)} \end{aligned}

For fixed YY, minimizing over assignments gives the Gibbs probabilities

pj∣x∗(Y)=e−∥x−yj∥2/T∑ℓ=1ke−∥x−yℓ∥2/T.(20)p^*_{j|x}(Y)=\frac{e^{-\|x-y_j\|^2/T}}{\sum_{\ell=1}^k e^{-\|x-y_\ell\|^2/T}}. \tag*{(20)}

Substituting these assignments into (19) gives the reduced free energy

FT(Y;q):=inf⁡pFT(Y,p;q)=−T∫log⁡(∑j=1ke−∥x−yj∥2/T)q(dx),F_T(Y;q):=\inf_p F_T(Y,p;q)=-T\int\log\left(\sum_{j=1}^k e^{-\|x-y_j\|^2/T}\right)q(dx),

as stated in (2).

Zero-temperature limit. Let m(x):=min⁡j∥x−yj∥2m(x):=\min_j\|x-y_j\|^2. Since

e−m(x)/T≤∑j=1ke−∥x−yj∥2/T≤ke−m(x)/T,e^{-m(x)/T}\le\sum_{j=1}^k e^{-\|x-y_j\|^2/T}\le ke^{-m(x)/T},

taking −Tlog⁡-T\log and integrating gives

D(Y;q)−Tlog⁡k≤FT(Y;q)≤D(Y;q).(21)D(Y;q)-T\log k\le F_T(Y;q)\le D(Y;q). \tag*{(21)}

Thus, since kk is fixed, the reduced free energy converges to the distortion uniformly in YY, as T↓0T\downarrow0.

Finiteness and attainment of W2,UW_{2,U}

Lemma 7. For q0,q∈P2(Rd)q_0, q \in\mathcal{P}_2(\mathbb{R}^d), W2,U(q0,q)<∞W_{2,U}(q_0,q) < \infty if and only if q0q_0 and qq have the same marginal on U⊥U^\perp, in which case the infimum in (4) is attained.

Proof. Let PUP_U and PU⊥P_{U^\perp} be the orthogonal projections onto UU and U⊥U^\perp. For X∼q0X \sim q_0, write XU:=PUXX_U := P_UX and XU⊥:=PU⊥XX_{U^\perp} := P_{U^\perp}X, and define ZU,ZU⊥Z_U, Z_{U^\perp} similarly for Z∼qZ \sim q. Any UU-structured plan satisfies Z−X∈UZ-X \in U, equivalently ZU⊥=XU⊥Z_{U^\perp}=X_{U^\perp}, almost surely. Thus, the U⊥U^\perp-marginals of qq and q0q_0 must be equal.

Conversely, suppose that XU⊥X_{U^\perp} and ZU⊥Z_{U^\perp} have the same distribution ν\nu, and let Ξ∼ν\Xi\sim\nu denote the unchanged U⊥U^\perp component. Define

PΞ,XU:=PXU⊥,XU,PΞ,ZU:=PZU⊥,ZU.P_{\Xi,X_U}:=P_{X_{U^\perp},X_U}, \qquad P_{\Xi,Z_U}:=P_{Z_{U^\perp},Z_U}.

These joint distributions share the marginal ν\nu on Ξ\Xi.

This matches the conditional Wasserstein distance formulation of Chemseddine et al. [6], with Ξ\Xi as the conditioning variable. The orthogonal decomposition preserves cost, since

∥Z−X∥2=∥(ZU⊥,ZU)−(XU⊥,XU)∥2.\lVert Z-X\rVert^2=\lVert(Z_{U^\perp},Z_U)-(X_{U^\perp},X_U)\rVert^2.

Thus, W2,U(q0,q)W_{2,U}(q_0,q) is equivalent to their conditional 2-Wasserstein distance between PΞ,XUP_{\Xi,X_U} and PΞ,ZUP_{\Xi,Z_U}. Their Proposition 1(iii) constructs an optimal conditional coupling α\alpha between PΞ,XUP_{\Xi,X_U} and PΞ,ZUP_{\Xi,Z_U}, preserving the Ξ\Xi-component. Let (Ξ1,V1,Ξ2,V2)∼α(\Xi_1,V_1,\Xi_2,V_2)\sim\alpha. Then the law of (Ξ1+V1,Ξ2+V2)(\Xi_1+V_1,\Xi_2+V_2) is an optimal UU-structured plan between q0q_0 and qq, since Ξ1=Ξ2\Xi_1=\Xi_2 almost surely and this correspondence preserves transport costs. Its cost is finite because ∥z−x∥2≤2∥x∥2+2∥z∥2\lVert z-x\rVert^2\le2\lVert x\rVert^2+2\lVert z\rVert^2 and q0,q∈P2(Rd)q_0,q\in\mathcal{P}_2(\mathbb{R}^d). □\square

Proof of the clustering certificate

For a split of cluster jj, any shift that brings q0jq_0^j to or beyond the split threshold satisfies WU2(q0,q)≥mjW2,U2(q0j,qj)≥mjρs,U2(q0j;T)W_U^2(q_0,q)\ge m_jW_{2,U}^2(q_0^j,q^j)\ge m_j\rho_{s,U}^2(q_0^j;T), with equality when q0jq_0^j is transported by a plan attaining its split radius and every other cluster is unchanged.

For a merge, however, it is less obvious that transporting a collection AA by a pooled structured plan attaining its merge radius ρm,U(q0A;T)\rho_{m,U}(q_0^A;T) incurs WUW_U-distance mAρm,U(q0A;T)\sqrt{m_A}\rho_{m,U}(q_0^A;T), since WUW_U measures the transport of each cluster separately rather than of the pooled distribution. To show this, suppose the merge radius of q0Aq_0^A is finite, and let γA,⋆∈ΓU(q0A,qA)\gamma^{A,\star}\in\Gamma_U(q_0^A,q^A) be such a plan, i.e., qAq^A is at or beyond the merge threshold and

∫∥z−x∥2 γA,⋆(dx,dz)=W2,U2(q0A,qA)=ρm,U2(q0A;T).(22)\int\lVert z-x\rVert^2\,\gamma^{A,\star}(dx,dz)=W_{2,U}^2(q_0^A,q^A)=\rho_{m,U}^2(q_0^A;T). \tag*{(22)}

We can condition this pooled plan on the cluster label to obtain a UU-structured transport plan γj\gamma^j for each cluster j∈Aj\in A, whose first marginal is q0jq_0^j by construction. Denote the second marginal by qjq^j, such that

γA,⋆=∑j∈AmjmAγj,qA=∑j∈AmjmAqj.(23)\gamma^{A,\star}=\sum_{j\in A}\frac{m_j}{m_A}\gamma^j,\qquad q^A=\sum_{j\in A}\frac{m_j}{m_A}q^j. \tag*{(23)}

Each γj\gamma^j is an optimal structured plan between q0jq_0^j and qjq^j. Otherwise, some γ~j∈ΓU(q0j,qj)\widetilde{\gamma}^j\in\Gamma_U(q_0^j,q^j) has a lower cost, and replacing γj\gamma^j by γ~j\widetilde{\gamma}^j in (23) gives a plan in ΓU(q0A,qA)\Gamma_U(q_0^A,q^A) with a lower cost than γA,⋆\gamma^{A,\star}, contradicting its optimality. Plugging (23) into (22) therefore gives

mAρm,U2(q0A;T)=∑j∈Amj∫∥z−x∥2 γj(dx,dz)=∑j∈AmjW2,U2(q0j,qj).m_A\rho_{m,U}^2(q_0^A;T)=\sum_{j\in A}m_j\int\lVert z-x\rVert^2\,\gamma^j(dx,dz)=\sum_{j\in A}m_jW_{2,U}^2(q_0^j,q^j).

Transporting each cluster j∈Aj\in A by γj\gamma^j and leaving every other cluster unchanged thus reaches the merge event at WUW_U-distance mAρm,U(q0A;T)\sqrt{m_A}\rho_{m,U}(q_0^A;T).

Proofs

Second variation and DA stability

Let q∈P2(Rd)q \in\mathcal{P}_2(\mathbb{R}^d), T>0T > 0, and k≥2k \ge2. Write μ:=μ(q)\mu:= \mu(q), C:=C(q)C := C(q), and Yμ:=Yμ(q)=(μ,…,μ)Y_\mu:= Y_\mu(q) = (\mu,\ldots,\mu). We first derive the second variation at YμY_\mu, then use it to prove Lemma 2.

Second variation at coincidence. For a perturbation ϕ=(ϕ1,…,ϕk)\phi= (\phi_1,\ldots,\phi_k), with ϕj∈Rd\phi_j \in\mathbb{R}^d, define

Yjε:=μ+εϕj,Yε:=Yμ+εϕ.Y_j^\varepsilon:= \mu+ \varepsilon\phi_j,\qquad Y^\varepsilon:= Y_\mu+ \varepsilon\phi.

Lemma 8 (Second variation). The configuration YμY_\mu is stationary, and the second variation of FTF_T at YμY_\mu is

Q(ϕ):=d2dε2FT(Yε;q)∣ε=0=4T∫(1k∑j=1kϕjT(x−μ))2q(dx)+2k∑j=1kϕjT(Id−2TC)ϕj.(24)Q(\phi) := \left.\frac{d^2}{d\varepsilon^2}F_T(Y^\varepsilon;q)\right|_{\varepsilon=0} = \frac{4}{T}\int\left(\frac{1}{k}\sum_{j=1}^{k}\phi_j^\mathsf{T}(x-\mu)\right)^2q(dx) +\frac{2}{k}\sum_{j=1}^{k}\phi_j^\mathsf{T}\left(I_d-\frac{2}{T}C\right)\phi_j. \tag*{(24)}

Proof. Write pj∣xε:=pj∣x∗(Yε)p_{j|x}^\varepsilon:= p^*_{j|x}(Y^\varepsilon) for the Gibbs assignments at the perturbed configuration. Differentiating (2) with respect to ε\varepsilon gives

ddεFT(Yε;q)=−2∫∑j=1kpj∣xεϕjT(x−μ−εϕj)q(dx).(25)\frac{d}{d\varepsilon}F_T(Y^\varepsilon;q) =-2\int\sum_{j=1}^{k}p_{j|x}^\varepsilon\phi_j^\mathsf{T}(x-\mu-\varepsilon\phi_j)q(dx). \tag*{(25)}

where differentiation under the integral, for both first and second variations, is justified by the finite second moment of qq.

At ε=0\varepsilon=0, the assignments are uniform, pj∣x0=1/kp_{j|x}^0=1/k, so

ddεFT(Yε;q)∣ε=0=−2k∑j=1kϕjT∫(x−μ)q(dx)=0.\left.\frac{d}{d\varepsilon}F_T(Y^\varepsilon;q)\right|_{\varepsilon=0} =-\frac{2}{k}\sum_{j=1}^{k}\phi_j^\mathsf{T}\int(x-\mu)q(dx)=0.

Since this holds for every ϕ\phi, ∇YFT(Yμ;q)=0\nabla_YF_T(Y_\mu;q)=0.

Differentiating the Gibbs assignments gives

ddεpj∣xε=2Tpj∣xε[ϕjT(x−μ−εϕj)−∑ℓ=1kpℓ∣xεϕℓT(x−μ−εϕℓ)].(26)\frac{d}{d\varepsilon}p_{j|x}^\varepsilon =\frac{2}{T}p_{j|x}^\varepsilon\left[\phi_j^\mathsf{T}(x-\mu-\varepsilon\phi_j)-\sum_{\ell=1}^{k}p_{\ell|x}^\varepsilon\phi_\ell^\mathsf{T}(x-\mu-\varepsilon\phi_\ell)\right]. \tag*{(26)}

Differentiating (25) once more, using (26), and evaluating at ε=0\varepsilon=0 yields

Q(ϕ)=2k∫∑j=1k∥ϕj∥2q(dx)−4kT∫∑j=1k(ϕjT(x−μ))2q(dx)+4T∫(1k∑j=1kϕjT(x−μ))2q(dx).\begin{aligned} Q(\phi) ={}&\frac{2}{k}\int\sum_{j=1}^{k}\lVert\phi_j\rVert^2q(dx)\\ &-\frac{4}{kT}\int\sum_{j=1}^{k}\left(\phi_j^\mathsf{T}(x-\mu)\right)^2q(dx)\\ &+\frac{4}{T}\int\left(\frac{1}{k}\sum_{j=1}^{k}\phi_j^\mathsf{T}(x-\mu)\right)^2q(dx). \end{aligned}

By the definition of CC, the first two terms equal

2k∑j=1kϕjT(Id−2TC)ϕj,\frac{2}{k}\sum_{j=1}^{k}\phi_j^{\mathsf{T}}\left(I_d-\frac{2}{T}C\right)\phi_j,

which gives (24).

Covariance criterion. We now establish the stability condition from the second variation.

Proof of Lemma 2. The first term of (24) is nonnegative. If λmax⁡(C)<T/2\lambda_{\max}(C)<T/2, then

Id−2TC≻0.I_d-\frac{2}{T}C\succ0.

The second term is therefore strictly positive for every nonzero ϕ\phi. Thus, the Hessian is positive definite, and stationarity implies that YμY_\mu is a strict local minimum.

Let vv be a unit eigenvector corresponding to λmax⁡(C)\lambda_{\max}(C), and define

ϕj={v,j=1,−v,j=2,0,j≥3.\phi_j= \begin{cases} v, & j=1,\\ -v, & j=2,\\ 0, & j\ge3. \end{cases}

Because ∑jϕj=0\sum_j\phi_j=0, the first term of (24) vanishes, giving

Q(ϕ)=4kvT(Id−2TC)v=4k(1−2λmax⁡(C)T).Q(\phi)=\frac{4}{k}v^{\mathsf{T}}\left(I_d-\frac{2}{T}C\right)v =\frac{4}{k}\left(1-\frac{2\lambda_{\max}(C)}{T}\right).

If λmax⁡(C)>T/2\lambda_{\max}(C)>T/2, then Q(ϕ)<0Q(\phi)<0, so the Hessian has a negative eigenvalue and YμY_\mu is a saddle point. Finally, if λmax⁡(C)=T/2\lambda_{\max}(C)=T/2, then Id−2C/T⪰0I_d-2C/T\succeq0, so Q(ϕ)≥0Q(\phi)\ge0 for every ϕ\phi. The nonzero perturbation ϕ\phi satisfies Q(ϕ)=0Q(\phi)=0. Thus, the Hessian is positive semidefinite but singular, and qq is critical. These three cases establish the claimed equivalences for every k≥2k\ge2.

Proof of Proposition 3

Let π∈Π(q0)\pi\in\Pi(q_0) and (X,Δ)∼π(X,\Delta)\sim\pi. As discussed in the main text, we assume without loss of generality that Eπ[Δ]=0\mathbb{E}_{\pi}[\Delta]=0. Let KK and SS be the associated moment matrices defined in (12). The covariance of the stacked random vector (XT,ΔT)T∈Rd+ℓ(X^{\mathsf{T}},\Delta^{\mathsf{T}})^{\mathsf{T}}\in\mathbb{R}^{d+\ell} is given by

(C0KKTS)=Eπ[(X−μ0Δ)(X−μ0Δ)T]⪰0,\begin{pmatrix} C_0 & K\\ K^{\mathsf{T}} & S \end{pmatrix} = \mathbb{E}_{\pi}\left[ \begin{pmatrix} X-\mu_0\\ \Delta \end{pmatrix} \begin{pmatrix} X-\mu_0\\ \Delta \end{pmatrix}^{\mathsf{T}} \right]\succeq0,

so (K,S)∈M(C0)(K,S)\in\mathcal{M}(C_0). Moreover,

C(qπ)=C0+KBT+BKT+BSBT=CB(K,S),Eπ[∥Δ∥2]=tr⁡S.C(q_\pi)=C_0+KB^{\mathsf{T}}+BK^{\mathsf{T}}+BSB^{\mathsf{T}}=C_B(K,S), \qquad\mathbb{E}_{\pi}[\lVert\Delta\rVert^2]=\operatorname{tr}S.

Hence, every centered displacement plan yields a feasible moment pair with the same cost and target covariance.

Conversely, let (K,S)∈M(C0)(K,S)\in\mathcal{M}(C_0). The generalized Schur complement gives

V:=S−KTC0†K⪰0,C0C0†K=K.V:=S-K^{\mathsf{T}}C_0^{\dagger}K\succeq0,\qquad C_0C_0^{\dagger}K=K.

Choose X∼q0X \sim q_0 and a zero-mean random vector η∈Rℓ\eta\in\mathbb{R}^{\ell}, independent of XX, with covariance VV (for example η∼N(0,V)\eta\sim\mathcal{N}(0,V)), and set

Δ:=KTC0†(X−μ0)+η.\Delta:= K^{\mathsf{T}}C_0^{\dagger}(X-\mu_0)+\eta.

The joint law π\pi of (X,Δ)(X,\Delta) belongs to Π(q0)\Pi(q_0), and Eπ[Δ]=0\mathbb{E}_{\pi}[\Delta]=0. Since X−μ0X-\mu_0 and η\eta are independent and have zero mean, Eπ[(X−μ0)ηT]=0\mathbb{E}_{\pi}[(X-\mu_0)\eta^{\mathsf{T}}]=0, so

Eπ[(X−μ0)ΔT]=C0C0†K=K.\mathbb{E}_{\pi}[(X-\mu_0)\Delta^{\mathsf{T}}]=C_0C_0^{\dagger}K=K.

Moreover,

Eπ[ΔΔT]=KTC0†C0C0†K+V=S.\mathbb{E}_{\pi}[\Delta\Delta^{\mathsf{T}}]=K^{\mathsf{T}}C_0^{\dagger}C_0C_0^{\dagger}K+V=S.

Thus, every feasible moment pair is realized by a centered displacement plan. Finally, if the moment infimum is attained at (K⋆,S⋆)(K^\star,S^\star), the construction above yields an optimal displacement plan π⋆\pi^\star. The corresponding optimal U\mathcal{U}-structured transport plan γ⋆\gamma^\star is then given by the joint law of (X,X+BΔ)(X,X+B\Delta), where (X,Δ)∼π⋆(X,\Delta)\sim\pi^\star.

Proof of Proposition 4

Proof. Since PU⊥B=0P_{\mathcal{U}^{\perp}}B=0, multiplying the merge constraint CB(K,S)⪯T2IdC_B(K,S)\preceq\frac{T}{2}I_d by PU⊥P_{\mathcal{U}^{\perp}} on both sides gives

PU⊥C0PU⊥=PU⊥CB(K,S)PU⊥⪯T2PU⊥,P_{\mathcal{U}^{\perp}}C_0P_{\mathcal{U}^{\perp}} = P_{\mathcal{U}^{\perp}}C_B(K,S)P_{\mathcal{U}^{\perp}} \preceq \frac{T}{2}P_{\mathcal{U}^{\perp}},

which proves the necessity of (16). Conversely, suppose this condition holds and choose K=−C0BK=-C_0B and S=BTC0BS=B^{\mathsf{T}}C_0B. Then

(C0KKTS)=(Id−BT)C0(Id−B)⪰0,\begin{pmatrix} C_0 & K\\ K^{\mathsf{T}} & S \end{pmatrix} = \begin{pmatrix} I_d\\ -B^{\mathsf{T}} \end{pmatrix} C_0 \begin{pmatrix} I_d & -B \end{pmatrix} \succeq0,

and

CB(K,S)=PU⊥C0PU⊥⪯T2PU⊥⪯T2Id.C_B(K,S)=P_{\mathcal{U}^{\perp}}C_0P_{\mathcal{U}^{\perp}} \preceq\frac{T}{2}P_{\mathcal{U}^{\perp}} \preceq\frac{T}{2}I_d.

Thus, the merge problem is feasible.

We next show that the feasible set is compact. For any feasible pair (K,S)(K,S), multiplying the merge constraint on the left by BTB^{\mathsf{T}} and on the right by BB, and using BTB=IℓB^{\mathsf{T}}B=I_{\ell}, gives

S⪯T2Iℓ−BTC0B−(BTK+KTB).S\preceq\frac{T}{2}I_{\ell}-B^{\mathsf{T}}C_0B-(B^{\mathsf{T}}K+K^{\mathsf{T}}B).

The block PSD constraint, evaluated on (2Bv,v)(2Bv,v) for every v∈Rℓv\in\mathbb{R}^{\ell}, yields

BTK+KTB⪰−2BTC0B−12S.B^{\mathsf{T}}K+K^{\mathsf{T}}B\succeq-2B^{\mathsf{T}}C_0B-\frac{1}{2}S.

Substituting this bound gives S⪯T2Iℓ+BTC0B+12SS\preceq\frac{T}{2}I_{\ell}+B^{\mathsf{T}}C_0B+\frac{1}{2}S. Rearranging, we obtain

0⪯S⪯2BTC0B+TIℓ.0\preceq S\preceq2B^{\mathsf{T}}C_0B+TI_{\ell}.

Thus, SS is bounded. The block PSD constraint also implies that its 2×22\times2 principal minors are nonnegative, so

(C0)iiSjj−Kij2≥0,i=1,…,d,j=1,…,ℓ.(C_0)_{ii}S_{jj}-K_{ij}^{2}\ge0,\qquad i=1,\ldots,d,\quad j=1,\ldots,\ell.

Since C0C_0 is fixed and SS is bounded, every entry of KK is bounded, and hence KK is also bounded. The feasible set is also closed and therefore compact, whenever nonempty. Hence, the continuous objective tr⁡S\operatorname{tr} S attains its minimum.

Finally, let (K⋆,S⋆)(K^\star,S^\star) be an optimal pair. The generalized Schur complement gives

C0C0†K⋆=K⋆,V:=S⋆−(K⋆)TC0†K⋆⪰0.C_0 C_0^\dagger K^\star= K^\star,\qquad V := S^\star- (K^\star)^{\mathsf T} C_0^\dagger K^\star\succeq0.

Replacing S⋆S^\star by S~:=(K⋆)TC0†K⋆\widetilde{S}:=(K^\star)^{\mathsf T}C_0^\dagger K^\star still satisfies the block PSD constraint and gives

CB(K⋆,S~)=CB(K⋆,S⋆)−BVBT⪯T2Id.C_B(K^\star,\widetilde{S})=C_B(K^\star,S^\star)-BVB^{\mathsf T}\preceq\frac{T}{2}I_d.

Thus, the pair (K⋆,S~)(K^\star,\widetilde{S}) is feasible and reduces the objective by tr⁡V\operatorname{tr} V. Optimality of S⋆S^\star implies tr⁡V=0\operatorname{tr} V=0, and hence V=0V=0.

Consequently, the construction in Proposition 3 gives an optimal displacement

Δ=(K⋆)TC0†(X−μ0).\Delta=(K^\star)^{\mathsf T}C_0^\dagger(X-\mu_0).

The corresponding optimal U\mathcal{U}-structured transport plan is then given by

x↦x+B(K⋆)TC0†(x−μ0).x\mapsto x+B(K^\star)^{\mathsf T}C_0^\dagger(x-\mu_0).

Proof of Lemma 5

Proof. Since q0q_0 is stable, vTC0v<T/2v^{\mathsf T}C_0v<T/2 for every unit direction vv. If v∈U⊥v\in\mathcal{U}^{\perp}, then BTv=0B^{\mathsf T}v=0, so vTCB(K,S)v=vTC0v<T/2v^{\mathsf T}C_B(K,S)v=v^{\mathsf T}C_0v<T/2 for every feasible (K,S)(K,S). Therefore, the directional constraint is infeasible.

Now suppose BTv≠0B^{\mathsf T}v\ne0. By Proposition 3, every (K,S)∈M(C0)(K,S)\in\mathcal{M}(C_0) is realized by a displacement plan π\pi, with X∼q0X\sim q_0 and Eπ[Δ]=0\mathbb{E}_{\pi}[\Delta]=0. Expanding the directional constraint gives

vTC0v+2vTKBTv+vTBSBTv≥T2.v^{\mathsf T}C_0v+2v^{\mathsf T}KB^{\mathsf T}v+v^{\mathsf T}BSB^{\mathsf T}v\ge\frac{T}{2}.

Using the definition of KK and Cauchy–Schwarz, we obtain

vTKBTv=vTEπ[(X−μ0)ΔT]BTv=Eπ[(vT(X−μ0))(ΔTBTv)]≤Eπ[(vT(X−μ0))2]Eπ[(ΔTBTv)2]=vTC0vvTBSBTv.(27)\begin{aligned} v^{\mathsf T}KB^{\mathsf T}v &=v^{\mathsf T}\mathbb{E}_{\pi}\left[(X-\mu_0)\Delta^{\mathsf T}\right]B^{\mathsf T}v\\ &=\mathbb{E}_{\pi}\left[\left(v^{\mathsf T}(X-\mu_0)\right)\left(\Delta^{\mathsf T}B^{\mathsf T}v\right)\right]\\ &\le\sqrt{\mathbb{E}_{\pi}\left[\left(v^{\mathsf T}(X-\mu_0)\right)^2\right]}\sqrt{\mathbb{E}_{\pi}\left[\left(\Delta^{\mathsf T}B^{\mathsf T}v\right)^2\right]}\\ &=\sqrt{v^{\mathsf T}C_0v}\sqrt{v^{\mathsf T}BSB^{\mathsf T}v}. \tag*{(27)} \end{aligned}

It follows that

vTCB(K,S)v≤vTC0v+2vTC0vvTBSBTv+vTBSBTv=(vTC0v+vTBSBTv)2.\begin{aligned} v^{\mathsf T}C_B(K,S)v &\le v^{\mathsf T}C_0v+2\sqrt{v^{\mathsf T}C_0v}\sqrt{v^{\mathsf T}BSB^{\mathsf T}v}+v^{\mathsf T}BSB^{\mathsf T}v\\ &=\left(\sqrt{v^{\mathsf T}C_0v}+\sqrt{v^{\mathsf T}BSB^{\mathsf T}v}\right)^2. \end{aligned}

Moreover, since S=Eπ[ΔΔT]S=\mathbb{E}_{\pi}[\Delta\Delta^{\mathsf T}], one more Cauchy–Schwarz gives

vTBSBTv=vTBEπ[ΔΔT]BTv=Eπ[(ΔTBTv)2]≤∥BTv∥2Eπ∥Δ∥2=tr⁡S∥BTv∥2.(28)\begin{aligned} v^{\mathsf T}BSB^{\mathsf T}v &=v^{\mathsf T}B\mathbb{E}_{\pi}[\Delta\Delta^{\mathsf T}]B^{\mathsf T}v\\ &=\mathbb{E}_{\pi}\left[(\Delta^{\mathsf T}B^{\mathsf T}v)^2\right]\le\lVert B^{\mathsf T}v\rVert^2\mathbb{E}_{\pi}\lVert\Delta\rVert^2=\operatorname{tr}S\lVert B^{\mathsf T}v\rVert^2. \tag*{(28)} \end{aligned}

Combining these bounds gives

vTCB(K,S)v≤(vTC0v+∥BTv∥tr⁡S)2.(29)v^{\mathsf{T}}C_B(K,S)v \le\left(\sqrt{v^{\mathsf{T}}C_0v}+\lVert B^{\mathsf{T}}v\rVert\sqrt{\operatorname{tr} S}\right)^2. \tag*{(29)}

The bound (29) holds with equality when both (27) and (28) hold with equality. For α≥0\alpha\ge0, this occurs when

Δ=αBTvvT(X−μ0)\Delta=\alpha B^{\mathsf{T}}v v^{\mathsf{T}}(X-\mu_0)

if vTC0v>0v^{\mathsf{T}}C_0v>0, which gives

K=αC0vvTB,S=α2(vTC0v)BTvvTB.K=\alpha C_0v v^{\mathsf{T}}B,\qquad S=\alpha^2(v^{\mathsf{T}}C_0v)B^{\mathsf{T}}v v^{\mathsf{T}}B.

If vTC0v=0v^{\mathsf{T}}C_0v=0, choose Δ=ακBTv\Delta=\alpha\kappa B^{\mathsf{T}}v, where κ\kappa is a zero mean and unit variance random variable independent of XX. This gives

K=0,S=α2BTvvTB.K=0,\qquad S=\alpha^2B^{\mathsf{T}}v v^{\mathsf{T}}B.

Rearranging (29) under the constraint vTCB(K,S)v≥T/2v^{\mathsf{T}}C_B(K,S)v\ge T/2 gives

tr⁡S≥(T/2−vTC0v)2∥BTv∥2.(30)\operatorname{tr} S\ge\frac{\left(\sqrt{T/2}-\sqrt{v^{\mathsf{T}}C_0v}\right)^2}{\lVert B^{\mathsf{T}}v\rVert^2}. \tag*{(30)}

Choosing α\alpha in the above feasible pairs so that vTCB(K,S)v=T/2v^{\mathsf{T}}C_B(K,S)v=T/2 attains equality in (30). Thus, this lower bound is attained and equals the minimum structured transport cost needed to reach the split threshold along vv.

Proof of Theorem 6 and recovery of a split direction

Proof. The problem we want to solve is

ρs,u2(q0;T)=min⁡∥v∥=1BTv≠0(T/2−vTC0v)2∥BTv∥2.\rho_{s,u}^2(q_0;T)=\min_{\substack{\lVert v\rVert=1\\B^{\mathsf{T}}v\ne0}}\frac{\left(\sqrt{T/2}-\sqrt{v^{\mathsf{T}}C_0v}\right)^2}{\lVert B^{\mathsf{T}}v\rVert^2}.

To put the problem in a form suitable for applying the S-lemma, we reformulate it in the following way

ρs,u2(q0;T)=max⁡η≥0 η\rho_{s,u}^2(q_0;T)=\max_{\eta\ge0}\ \eta

subject to

η≤(T/2−vTC0v)2∥BTv∥2\eta\le\frac{\left(\sqrt{T/2}-\sqrt{v^{\mathsf{T}}C_0v}\right)^2}{\lVert B^{\mathsf{T}}v\rVert^2}

for all ∥v∥=1\lVert v\rVert=1, BTv≠0B^{\mathsf{T}}v\ne0.

Since q0q_0 is stable, T/2−vTC0v>0\sqrt{T/2}-\sqrt{v^{\mathsf{T}}C_0v}>0. Taking the square root and rearranging gives

vTC0v+η∥BTv∥≤T/2.\sqrt{v^{\mathsf{T}}C_0v}+\sqrt{\eta}\lVert B^{\mathsf{T}}v\rVert\le\sqrt{T/2}.

This inequality is automatically satisfied when BTv=0B^{\mathsf{T}}v=0, so we can include all unit directions. Hence,

ρs,u2(q0;T)=max⁡η≥0{η:max⁡∥v∥=1(vTC0v+η∥BTv∥)≤T/2}.(31)\rho_{s,u}^2(q_0;T)=\max_{\eta\ge0}\left\{\eta:\max_{\lVert v\rVert=1}\left(\sqrt{v^{\mathsf{T}}C_0v}+\sqrt{\eta}\lVert B^{\mathsf{T}}v\rVert\right)\le\sqrt{T/2}\right\}. \tag*{(31)}

We next rewrite the inner maximum using the identity ∥a∥=max⁡∥u∥=1uTa\lVert a\rVert=\max_{\lVert u\rVert=1}u^{\mathsf{T}}a. In particular,

vTC0v=∥C01/2v∥=max⁡∥u∥=1vTC01/2u,η∥BTv∥=max⁡∥w∥2≤ηvTBw,\sqrt{v^{\mathsf{T}}C_0v}=\lVert C_0^{1/2}v\rVert=\max_{\lVert u\rVert=1}v^{\mathsf{T}}C_0^{1/2}u,\qquad \sqrt{\eta}\lVert B^{\mathsf{T}}v\rVert=\max_{\lVert w\rVert^2\le\eta}v^{\mathsf{T}}Bw,

where u∈Rdu \in\mathbb{R}^d and w∈Rℓw \in\mathbb{R}^{\ell} are auxiliary vectors. Their choices are independent, so

max⁡∥v∥=1(vTC0v+η∥BTv∥)=max⁡∥v∥=1max⁡∥u∥=1∥w∥2≤ηvT(C01/2u+Bw)=max⁡∥u∥=1∥w∥2≤ηmax⁡∥v∥=1vT(C01/2u+Bw)=max⁡∥u∥=1∥w∥2≤η∥C01/2u+Bw∥.(32)\begin{aligned} \max_{\lVert v\rVert=1}\left(\sqrt{v^{\mathsf{T}}C_0v}+\sqrt{\eta}\lVert B^{\mathsf{T}}v\rVert\right) = \max_{\lVert v\rVert=1}\max_{\substack{\lVert u\rVert=1\\\lVert w\rVert^2\leq\eta}}v^{\mathsf{T}}\left(C_0^{1/2}u+Bw\right) \\ &= \max_{\substack{\lVert u\rVert=1\\\lVert w\rVert^2\leq\eta}}\max_{\lVert v\rVert=1}v^{\mathsf{T}}\left(C_0^{1/2}u+Bw\right) \\ &= \max_{\substack{\lVert u\rVert=1\\\lVert w\rVert^2\leq\eta}}\lVert C_0^{1/2}u+Bw\rVert. \tag*{(32)} \end{aligned}

Consequently, the constraint in (31) is equivalent to

∥C01/2u+Bw∥2≤T2whenever ∥u∥=1, ∥w∥2≤η.(33)\lVert C_0^{1/2}u+Bw\rVert^2\leq\frac{T}{2}\qquad\text{whenever }\lVert u\rVert=1,\ \lVert w\rVert^2\leq\eta. \tag*{(33)}

This is equivalent to the quadratic implication

∥w∥2≤η∥u∥2⟹∥C01/2u+Bw∥2≤T2∥u∥2(34)\lVert w\rVert^2\leq\eta\lVert u\rVert^2\quad\Longrightarrow\quad\lVert C_0^{1/2}u+Bw\rVert^2\leq\frac{T}{2}\lVert u\rVert^2 \tag*{(34)}

for all u,wu,w. To see this, assume (33) holds. For any u≠0u\ne0 and ww satisfying ∥w∥2≤η∥u∥2\lVert w\rVert^2\leq\eta\lVert u\rVert^2, apply it to u/∥u∥u/\lVert u\rVert and w/∥u∥w/\lVert u\rVert, then multiply the resulting inequality by ∥u∥2\lVert u\rVert^2. If u=0u=0, then w=0w=0, so the conclusion holds automatically. Conversely, restricting (34) to ∥u∥=1\lVert u\rVert=1 recovers (33).

For η>0\eta>0, any u≠0u\ne0 and w=0w=0 satisfy η∥u∥2−∥w∥2>0\eta\lVert u\rVert^2-\lVert w\rVert^2>0. Therefore, by the S-lemma, (34) is equivalent to the existence of λ≥0\lambda\geq0 such that

T2∥u∥2−∥C01/2u+Bw∥2−λ(η∥u∥2−∥w∥2)≥0for all u,w.(35)\frac{T}{2}\lVert u\rVert^2-\lVert C_0^{1/2}u+Bw\rVert^2-\lambda\left(\eta\lVert u\rVert^2-\lVert w\rVert^2\right)\geq0\qquad\text{for all }u,w. \tag*{(35)}

Expanding ∥C01/2u+Bw∥2=uTC0u+2uTC01/2Bw+wTw\lVert C_0^{1/2}u+Bw\rVert^2=u^{\mathsf{T}}C_0u+2u^{\mathsf{T}}C_0^{1/2}Bw+w^{\mathsf{T}}w, the left-hand side of (35) equals

(uw)T((T2−λη)Id−C0−C01/2B−BTC01/2(λ−1)Iℓ)(uw).\begin{pmatrix}u\\w\end{pmatrix}^{\mathsf{T}} \begin{pmatrix} \left(\frac{T}{2}-\lambda\eta\right)I_d-C_0 & -C_0^{1/2}B\\ -B^{\mathsf{T}}C_0^{1/2} & (\lambda-1)I_{\ell} \end{pmatrix} \begin{pmatrix}u\\w\end{pmatrix}.

Its nonnegativity for every u,wu,w is equivalent to

M(η,λ)=((T2−λη)Id−C0−C01/2B−BTC01/2(λ−1)Iℓ)⪰0.(36)M(\eta,\lambda)= \begin{pmatrix} \left(\frac{T}{2}-\lambda\eta\right)I_d-C_0 & -C_0^{1/2}B\\ -B^{\mathsf{T}}C_0^{1/2} & (\lambda-1)I_{\ell} \end{pmatrix}\succeq0. \tag*{(36)}

Since λ≥1\lambda\geq1 (by lower-right block), setting τ:=1/λ∈(0,1]\tau:=1/\lambda\in(0,1] and multiplying (36) by τ>0\tau>0 gives

\begin{pmatrix} \tau\left(\frac{T}{2}I_d-C_0\right)-\eta I_d & -\tau C_0^{1/2}B\\ -\tau B^{\mathsf{T}}C_0^{1/2} & (1-\tau)I_{\ell} \end{pmatrix}\succeq0. \tag*{(37)}\end{pmatrix}

This is now affine in τ,η\tau,\eta. For positive η\eta, every step above is an equivalence.

Note that allowing τ=0\tau=0 forces η=0\eta=0, which already satisfies (31) and therefore does not change the optimal value. Hence, maximizing η\eta over η,τ≥0\eta,\tau\geq0 subject to (37) gives the SDP in (18).

It is straightforward to check that 0≤τ≤10\leq\tau\leq1 and 0≤η≤T/20\leq\eta\leq T/2, and the feasible set is nonempty, so the maximum is attained.

Recovering an optimal split direction. One way to recover an optimal split direction from (η⋆,τ⋆)(\eta^\star,\tau^\star) is as follows. The constraint (33) can be written as

max⁡∥u∥=1∥w∥2≤η⋆∥C01/2u+Bw∥2≤T2.\max_{\lVert u\rVert=1 \atop\lVert w\rVert^2\leq\eta^\star} \left\lVert C_0^{1/2}u+Bw\right\rVert^2 \leq\frac{T}{2}.

The maximum is attained by compactness. Since the objective is strictly convex in ww, an interior point cannot maximize it, so any maximizing pair satisfies ∥w⋆∥2=η⋆\lVert w^\star\rVert^2=\eta^\star. Moreover, the inequality must be tight at optimality. Otherwise, a positive gap would allow every feasible ww to be scaled by a factor α>1\alpha>1 sufficiently close to one while still satisfying the inequality. The larger budget α2η⋆\alpha^2\eta^\star would then be feasible, contradicting optimality. Thus, an attaining pair satisfies

∥u⋆∥=1,∥w⋆∥2=η⋆,∥C01/2u⋆+Bw⋆∥2=T2.\lVert u^\star\rVert=1,\qquad\lVert w^\star\rVert^2=\eta^\star,\qquad\left\lVert C_0^{1/2}u^\star+Bw^\star\right\rVert^2=\frac{T}{2}.

Since η⋆>0\eta^\star>0, we have τ⋆>0\tau^\star>0. Set λ⋆:=1/τ⋆\lambda^\star:=1/\tau^\star, and let M⋆M^\star denote the matrix in (36) evaluated at (η⋆,λ⋆)(\eta^\star,\lambda^\star). The equalities above make the S-lemma certificate (35) zero, giving

(u⋆w⋆) ⁣⊤M⋆(u⋆w⋆)=0.\begin{pmatrix}u^\star\\w^\star\end{pmatrix}^{\!\top} M^\star \begin{pmatrix}u^\star\\w^\star\end{pmatrix}=0.

Since M⋆⪰0M^\star\succeq0, the stacked vector ((u⋆)⊤,(w⋆)⊤)⊤((u^\star)^\top,(w^\star)^\top)^\top lies in ker⁡M⋆\ker M^\star. Hence, recovering vv reduces to finding

(uw)∈ker⁡M⋆,∥u∥=1,∥w∥2=η⋆.\begin{pmatrix}u\\w\end{pmatrix}\in\ker M^\star,\qquad\lVert u\rVert=1,\qquad\lVert w\rVert^2=\eta^\star.

Once such a pair is found, as per (32), the maximization of v⊤(C01/2u+Bw)v^\top(C_0^{1/2}u+Bw) over ∥v∥=1\lVert v\rVert=1 is attained at

v⋆=C01/2u+Bw∥C01/2u+Bw∥=C01/2u+BwT/2,v^\star=\frac{C_0^{1/2}u+Bw}{\lVert C_0^{1/2}u+Bw\rVert} =\frac{C_0^{1/2}u+Bw}{\sqrt{T/2}},

which recovers a splitting direction v⋆v^\star. To confirm this, observe that

T/2=(v⋆)⊤(C01/2u+Bw)≤∥C01/2v⋆∥∥u∥+∥B⊤v⋆∥∥w∥≤(v⋆)⊤C0v⋆+η⋆∥B⊤v⋆∥≤T/2.\begin{aligned} \sqrt{T/2}=(v^\star)^\top(C_0^{1/2}u+Bw)\leq\lVert C_0^{1/2}v^\star\rVert\lVert u\rVert+\lVert B^\top v^\star\rVert\lVert w\rVert\\ &\leq\sqrt{(v^\star)^\top C_0v^\star}+\sqrt{\eta^\star}\lVert B^\top v^\star\rVert\leq\sqrt{T/2}. \end{aligned}

Both inequalities are therefore equalities, so v⋆v^\star attains the directional cost η⋆\eta^\star. Using this direction in the displacement construction from the proof of Lemma 5 yields an optimal U\mathcal{U}-structured transport plan.

Additional simulations and experiments

S1–S3 SIPU datasets

S3 vs. S3 with clusters moved apart As a controlled check, we scale the S3 cluster means by 1.25, keeping each cluster’s points fixed relative to its mean (Figure 3). As expected, the smallest mass-weighted split radius, attained by split 9, remains unchanged at 7.23, 8.96, and 8.54 under unrestricted, horizontal, and vertical shifts (in units of 10−310^{-3}). The smallest merge events are also unchanged (4+13, 4+13, and 3+14), but their mass-weighted radii increase from 16.0, 16.8, and 19.0 to 36.8, 39.4, and 39.7, roughly by a factor of 2.1–2.3, so, as expected, the clustering becomes more robust to merges.

S3 and S3 with cluster means scaled by 1.25

Figure 3. (a) S3 and (b) S3 with cluster means scaled by 1.25, at T=0.1T = 0.1 and on the same axes. The covariance ellipses and T/2\sqrt{T}/2 circles are unchanged.

Minimum split and merge radii Tables 2 and 3 report the minimum unweighted and mass-weighted split and merge radii. Mass weighting can change which event is most vulnerable: under unrestricted shifts in S1, cluster 10 has the smallest split radius, but splitting cluster 1 requires the least population transport distance. Figure 4 shows attaining shifts for the certificate-attaining events.

DatasetWeightingUnrestricted EventUnrestricted RadiusHorizontal EventHorizontal RadiusVertical EventVertical Radius
S1UnweightedSplit 10115.56Split 10115.92Split 10122.59
S1Mass-weightedSplit 129.44Split 129.60Split 1031.97
S2UnweightedSplit 1475.42Split 1479.78Split 1486.40
S2Mass-weightedSplit 1419.52Split 1420.65Split 1422.36
S3UnweightedSplit 928.80Split 935.68Split 934.02
S3Mass-weightedSplit 97.23Split 98.96Split 98.54

Table 2. Minimum split radii at T=0.1T = 0.1. Unweighted rows minimize ρs,U(qj0;T)\rho_{s,U}(q_j^0; T) over clusters jj; mass-weighted rows minimize mjρs,U(qj0;T)\sqrt{m_j}\rho_{s,U}(q_j^0; T). All values are reported in units of 10−310^{-3}. Bold values attain the clustering certificate RUR_U.

For unrestricted shifts across S1–S3, Table 4 reports the three smallest split and merge radii, ranked separately before and after mass weighting, with ratios to their respective minima.

DatasetWeightingRankSplits EventSplits RadiusSplits RatioMerges EventMerges RadiusMerges Ratio
S1Unweighted1Split 10115.561.0000Merge {6,13}\{6, 13\}32.781.0000
S1Unweighted2Split 11115.591.0002Merge {2,5}\{2, 5\}39.131.1939
S1Unweighted3Split 1120.791.0453Merge {1,8}\{1, 8\}48.911.4921
S1Mass-weighted1Split 129.441.0000Merge {6,13}\{6, 13\}12.081.0000
S1Mass-weighted2Split 1030.141.0236Merge {2,5}\{2, 5\}14.031.1618
S1Mass-weighted3Split 1130.411.0328Merge {1,8}\{1, 8\}17.391.4396
S2Unweighted1Split 1475.421.0000Merge {2,15}\{2, 15\}33.361.0000
S2Unweighted2Split 1286.121.1419Merge {1,8}\{1, 8\}42.291.2677
S2Unweighted3Split 591.221.2096Merge {5,15}\{5, 15\}43.171.2943
S2Mass-weighted1Split 1419.521.0000Merge {2,15}\{2, 15\}12.161.0000
S2Mass-weighted2Split 1222.491.1521Merge {1,8}\{1, 8\}15.121.2427
S2Mass-weighted3Split 523.511.2042Merge {5,15}\{5, 15\}15.861.3040
S3Unweighted1Split 928.801.0000Merge {4,13}\{4, 13\}42.201.0000
S3Unweighted2Split 538.871.3493Merge {3,14}\{3, 14\}50.541.1977
S3Unweighted3Split 1245.581.5825Merge {6,10}\{6, 10\}53.781.2746
S3Mass-weighted1Split 97.231.0000Merge {4,13}\{4, 13\}15.981.0000
S3Mass-weighted2Split 59.391.2992Merge {3,14}\{3, 14\}18.371.1499
S3Mass-weighted3Split 1211.691.6173Merge {6,10}\{6, 10\}19.891.2449

Table 4. Three smallest split and merge radii under unrestricted shifts at T=0.1T = 0.1. Rankings are computed separately for each dataset, event type, and weighting. Radii are reported in units of 10−310^{-3}; mass-weighted radii are population transport distances WUW_U. Each ratio is relative to the minimum in its own ranking. Merge rankings include only monitored neighboring pairs. Event labels match Figure 2.

DatasetWeightingUnrestricted EventUnrestricted RadiusHorizontal EventHorizontal RadiusVertical EventVertical Radius
S1UnweightedMerge {6,13}\{6, 13\}32.78Merge {3,9}\{3, 9\}64.61Merge {6,13}\{6, 13\}35.60
S1Mass-weightedMerge {6,13}\{6, 13\}12.08Merge {3,9}\{3, 9\}23.38Merge {6,13}\{6, 13\}13.12
S1Feasible pairs34/3413/3414/34
S2UnweightedMerge {2,15}\{2, 15\}33.36Merge {2,15}\{2, 15\}45.76Merge {1,8}\{1, 8\}43.34
S2Mass-weightedMerge {2,15}\{2, 15\}12.16Merge {2,15}\{2, 15\}16.69Merge {1,8}\{1, 8\}15.49
S2Feasible pairs33/3314/3314/33
S3UnweightedMerge {4,13}\{4, 13\}42.20Merge {4,13}\{4, 13\}44.44Merge {3,14}\{3, 14\}52.12
S3Mass-weightedMerge {4,13}\{4, 13\}15.98Merge {4,13}\{4, 13\}16.83Merge {3,14}\{3, 14\}18.95
S3Feasible pairs35/3514/3514/35

Table 3. Minimum merge radii at T=0.1T = 0.1. Unweighted rows minimize ρm,U(q0A;T)\rho_{m,U}(q_0^A; T) over monitored pairs AA; mass-weighted rows minimize mAρm,U(q0A;T)\sqrt{m_A}\rho_{m,U}(q_0^A; T). All radii are reported in units of 10−310^{-3}. Bold values attain the clustering certificate RUR_U. Feasible-pair counts give the number of finite merge radii out of all monitored pairs.

Higher-dimensional example: DIM64

We consider the DIM64 benchmark from the same SIPU repository, with 1024 points in R64\mathbb{R}^{64} and 16 clusters. Centering, normalization, and the Lloyd initialization are the same as for S1–S3. The resulting labels are held fixed, and we use the same temperature T=0.1T = 0.1. Feasible radius problems are solved using SCS through CVXPY. If a merge fails the feasibility condition (16), no SDP solve is required.

References

  1. [1]Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat. NP-hardness of Euclidean sum-of-squares clustering. Machine Learning, 75(2):245–248, May 2009. ISSN 1573-0565. doi: 10.1007/s10994-009-5103-0. URL https://doi.org/10.1007/s10994-009-5103-0.
  2. [2]Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. Information Processing Letters, 112(1):49–54, January 2012. ISSN 0020-0190. doi: 10.1016/j.ipl.2011.10.006. URL https://www.sciencedirect.com/science/article/pii/S0020019011002778.DOI
  3. [3]Isin M. Balci and Efstathios Bakolas. Exact SDP Formulation for Discrete-Time Covariance Steering with Wasserstein Terminal Cost, May 2022. URL http://arxiv.org/abs/2205.10740. arXiv:2205.10740 [math.OC].
  4. [5]Shai Ben-David, Ulrike von Luxburg, and Dávid Pál. A Sober Look at Clustering Stability. In Gábor Lugosi and Hans Ulrich Simon, editors, Learning Theory, pages 5–19, Berlin, Heidelberg, 2006. Springer. ISBN 978-3-540-35296-9. doi: 10.1007/11776420_4.
  5. [6]Jannis Chemseddine, Paul Hagemann, Gabriele Steidl, and Christian Wald. Conditional Wasserstein Distances with Applications in Bayesian OT Flow Matching. Journal of Machine Learning Research, 26 (141):1–47, 2025. ISSN 1533-7928. URL http://jmlr.org/papers/v26/24-0586.html.arxiv.org/abs/2403.18705
  6. [7]Yongxin Chen, Tryphon T. Georgiou, and Michele Pavon. Optimal Steering of a Linear Stochastic System to a Final Probability Distribution, Part I. IEEE Transactions on Automatic Control, 61(5):1158–1169, May 2016. ISSN 1558-2523. doi: 10.1109/TAC.2015.2457784. URL https://ieeexplore.ieee.org/document/7160692.DOI
  7. [9]Hamza Fawzi, Paulo Tabuada, and Suhas Diggavi. Secure Estimation and Control for Cyber-Physical Systems Under Adversarial Attacks. IEEE Transactions on Automatic Control, 59(6):1454–1467, June 2014. ISSN 1558-2523. doi: 10.1109/TAC.2014.2303233. URL https://ieeexplore.ieee.org/document/6727407.DOI
  8. [10]Pasi Fränti and Olli Virmajoki. Iterative shrinking method for clustering problems. Pattern Recognition, 39(5):761–775, May 2006. ISSN 0031-3203. doi: 10.1016/j.patcog.2005.09.012. URL https://www.sciencedirect.com/science/article/pii/S0031320305003778.DOI
  9. [11]Rui Gao and Anton Kleywegt. Distributionally Robust Stochastic Optimization with Wasserstein Distance. Mathematics of Operations Research, 48(2):603–655, May 2023. ISSN 0364-765X. doi: 10.1287/moor.2022.1275. URL https://pubsonline.informs.org/doi/full/10.1287/moor.2022.1275.DOI
  10. [12]Chuan Guo, Jared S. Frank, and Kilian Q. Weinberger. Low Frequency Adversarial Perturbation. In Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, pages 1127–1137. PMLR, August 2020. URL https://proceedings.mlr.press/v115/guo20a.html.
  11. [13]Vikrant Malik, Taylan Kargin, and Babak Hassibi. Distributionally Robust K-Means Clustering, 2026. URL https://arxiv.org/abs/2604.11118. Version Number: 1.
  12. [15]Christos N. Mavridis and John S. Baras. Annealing Optimization for Progressive Learning With Stochastic Approximation. IEEE Transactions on Automatic Control, 68(5):2862–2874, May 2023b. ISSN 1558-2523. doi: 10.1109/TAC.2022.3232706. URL https://ieeexplore.ieee.org/document/10002308.DOI
  13. [16]Robert J. McCann and Brendan Pass. Optimal Transportation Between Unequal Dimensions. Archive for Rational Mechanics and Analysis, 238(3):1475–1520, December 2020. ISSN 1432-0673. doi: 10.1007/s00205-020-01569-5. URL https://doi.org/10.1007/s00205-020-01569-5.
  14. [17]Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations. Mathematical Programming, 171(1):115–166, September 2018. ISSN 1436-4646. doi: 10.1007/s10107-017-1172-1. URL https://doi.org/10.1007/s10107-017-1172-1.
  15. [18]Gabriel Peyré and Marco Cuturi. Computational Optimal Transport with Applications to Data Sciences. Foundations and Trends in Machine Learning, 11(5-6):355–607, February 2019. ISSN 1935-8237. doi: 10.1561/2200000073. URL https://doi.org/10.1561/2200000073.
  16. [19]K. Rose. Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. Proceedings of the IEEE, 86(11):2210–2239, November 1998. ISSN 1558-2256. doi: 10.1109/5.726788. URL https://ieeexplore.ieee.org/document/726788/.DOI
  17. [21]Amber Srivastava, Mayank Baranwal, and Srinivasa Salapaka. On the Persistence of Clustering Solutions and True Number of Clusters in a Dataset. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):5000–5007, July 2019. ISSN 2374-3468. doi: 10.1609/aaai.v33i01.33015000. URL https://ojs.aaai.org/index.php/AAAI/article/view/4431.DOI
  18. [22]Berk Ustun, Alexander Spangher, and Yang Liu. Actionable Recourse in Linear Classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* ’19, pages 10–19, New York, NY, USA, January 2019. Association for Computing Machinery. ISBN 978-1-4503-6125-5. doi: 10.1145/3287560.3287566. URL https://dl.acm.org/doi/10.1145/3287560.3287566.DOI

Paper details

vlnc:W_ygv9fe3h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents