Extrapolating Clusterings from Semidefinite Subsamples

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

The Peng-Wei relaxation of $k$-means minimizes a distance-based linear objective over $X\succeq0$ with $X\geq0$, $X\mathbf1=\mathbf1$, and $\operatorname{tr}X=k$, using the source's distance normalization.

A semidefinite program optimizes a linear functional of a symmetric matrix subject to affine constraints and positive semidefiniteness. The condition $X\succeq0$ means $v^TXv\geq0$ for every real vector $v$.

Statement recorded in the supplied source.

Given a full data set $T$ and a sampled subset $S$, can a near-optimal clustering of $T$ be extrapolated from the Peng–Wei semidefinite program applied to $S$? [S2]

Scope qualification.

The sampling distribution, cluster count, separation assumptions, approximation loss, and extrapolation rule are not stated.

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Recover a nearly optimal full-data clustering from a semidefinite clustering of sampled data.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30003758 (OWR-15999-007). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Applied Harmonic Analysis and Data Processing $2019$, Oberwolfach Reports, DOI 10.4171/owr/2018/14, pp. 723--792 https://doi.org/10.4171/owr/2018/14.
• S3 Oberwolfach Report 14 https://doi.org/10.4171/OWR/2018/14.
• S4 K-means SDP certificates https://arxiv.org/abs/1710.00956.
• S5 Sketch-and-solve k-means https://academic.oup.com/imaiai/article/13/3/iaae016/7713562. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30003758 and source code OWR-15999-007 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The geometric-clustering talk in OWR 14/2018, pp. 785--786, was read. It samples uniformly without replacement and uses the subsample SDP chiefly to lower-bound the full optimum before asking about extrapolating an actual clustering. A lower-bound certificate is not itself an assignment rule. The following conditional margin argument and explicit failure of frozen subsample centers investigate that gap, without asserting a guarantee for every possible extrapolation algorithm.

Research attempt: A margin-based extension and a missed-cluster counterexample

A deterministic extension lemma.

Suppose the full data have a specified partition into $k$ nonempty classes, each contained in a ball of radius $r$ around a center $\mu_j$, and the centers satisfy $\|\mu_i-\mu_j\|>4r$ for $i\ne j$. Assume the sample contains at least one point from each class and a procedure has recovered its class labels correctly. Let $\widehat\mu_j$ be the mean of its sampled points in class $j$. Then $\|\widehat\mu_j-\mu_j\|\le r$, because an average of vectors of norm at most $r$ also has norm at most $r$. A full point from class $j$ lies within $2r$ of $\widehat\mu_j$, but at distance greater than $2r$ from every other sampled centroid, by the triangle inequality. Assigning all points to their nearest sampled centroid therefore recovers the full specified partition.

This is an optimal-clustering guarantee only if that specified partition is independently known to be optimal; geometric separation without size assumptions need not prove that. Nor does the lemma prove that the Peng--Wei SDP is integral or that its rounding recovered the sample labels. Those are explicit additional steps.

If every class has at least an $\alpha$ fraction of the $N$ full data points and $S$ is a uniform size-$s$ sample without replacement, the probability of missing a class of size $N_j$ is \[ \frac{\binom{N-N_j}{s}}{\binom Ns} \le(1-N_j/N)^s\le e^{-\alpha s}, \] with probability zero if $s>N-N_j$. The product formula for drawing only outside points proves the first inequality, since each successive conditional outside probability is at most $1-N_j/N$. A union bound shows that $s\ge\alpha^{-1}\log(k/\delta)$ ensures coverage with probability at least $1-\delta$, provided such an $s\le N$ is chosen; taking the full set gives coverage automatically. This supplies the coverage step alone, not SDP correctness.

An exact sample SDP can still miss a crucial full-data center.

Let $T$ be the one-dimensional sequence with $m$ copies of $0$, $m$ copies of $1$, and one point $R>2$, so $N=2m+1$, and take $k=2$. Suppose $S$ omits $R$ but contains both locations $0,1$, with $s\ge2$. The Peng--Wei objective on $S$ has value zero, attained by its two location blocks. In fact this solution is unique. Zero objective and entrywise nonnegativity force all cross-location matrix entries to be zero. Each within-location block is symmetric positive semidefinite and has row sums one, so it has eigenvalue one and all other eigenvalues nonnegative. The total trace is two, forcing each block's other eigenvalues to be zero. The block is therefore the rank-one orthogonal projection onto its all-ones vector, namely $|C|^{-1}\mathbf1\mathbf1^T$.

Consequently even exact solution and exact integral rounding on the sample produce centers $0$ and $1$. The simple extension that freezes these centers and assigns all data to the nearer one has normalized squared cost at least \[ \frac{(R-1)^2}{N}. \] On the other hand the full two-means optimum is at most $m/(2N)<1/4$, by placing one center at $1/2$ for the zeros and ones and the other at $R$. Thus the ratio for the frozen-center extension is at least $4(R-1)^2/N$, unbounded as $R$ grows. This is a comparison of the frozen-center objective; an algorithm that inspects all of $T$ and updates centers could detect the missing point and is not ruled out.

The bad sampling event can have high probability. A union bound on its complement gives \[ \Pr(S\text{ omits }R\text{ and contains }0,1) \ge1-\frac{s}{N}-2\left(\frac{m+1}{N}\right)^s. \] Here $s/N$ is the inclusion probability of the outlier and the other terms bound missing each common location. For large $m$ and $s$ growing logarithmically while $s/N\to0$, the lower bound tends to one. Thus neither a perfect sample SDP nor high probability of seeing the common clusters supplies a distribution-free full-data approximation ratio when arbitrarily rare distant structure is allowed.

Verification and adversarial audit

The centroid margin proof uses strict separation to avoid ties and keeps full optimality and SDP integrality as separate assumptions. The without-replacement probability was derived from conditional sampling. In the counterexample, feasibility and uniqueness of the zero-cost sample SDP were proved spectrally, and the full-data upper and lower costs were evaluated explicitly. The result is limited to freezing sampled centers, not every algorithm allowed to read all full data.

Audit corrections.

Separated subsample lower-bound certification from full-data assignment and kept the extension lemma conditional on correct sample labels. Proved that the failure example has an exactly integral sample SDP, while explicitly allowing that a more adaptive full-data algorithm could avoid the obstruction.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The original question's near-optimal extrapolation algorithm remains unconstructed. Missing ingredients include a sampling/size model that controls rare clusters, an SDP recovery or rounding theorem, and an extension rule with a full-data approximation guarantee. The conditional margin lemma and the explicit frozen-center failure identify these gaps without turning the source's lower-bound certificate into a clustering algorithm.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46736 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and written-proof review of this attempt; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.