核心集与精确单均值压缩

形式陈述

设有限输入为带权点集 $(P,w)$ ，其中 $w(p)\ge0$ ；查询集合为 $\mathcal Q$ ，损失函数 $f:P\times\mathcal Q\to[0,\infty)$ 。一个查询的总成本是

\operatorname{cost}_P(q)=\sum_{p\in P}w(p)f(p,q).

本文采用输入子集的约定：核心集（也称核集）为 $(C,u)$ ，其中 $C\subseteq P$ 、 $u(c)\ge0$ ，允许重新分配权重。给定 $0\le\varepsilon<1$ ，若对每一个 $q\in\mathcal Q$ 都有

(1-\varepsilon)\operatorname{cost}_P(q) \le\operatorname{cost}_C(q) \le(1+\varepsilon)\operatorname{cost}_P(q),

则称它为强 $\varepsilon$ -核心集。 $\varepsilon=0$ 时称为精确核心集。强保证保持整族查询的目标函数；只保持最优解或最优值，尚不足以满足这个定义。若构造是随机的，“以至少 $1-\delta$ 的概率成功”指同一个成功事件上所有查询同时满足不等式，而不是每个固定查询各自成功。

强保证可把压缩数据上的求解结果传回原输入。假设两边最优解存在，记原输入的最优解为 $q_*$ ，并设 $q_C$ 在核心集上具有近似比 $\alpha\ge1$ 。那么

\begin{aligned} \operatorname{cost}_P(q_C) &\le\frac{\operatorname{cost}_C(q_C)}{1-\varepsilon}\\ &\le\frac{\alpha\min_{q\in\mathcal Q}\operatorname{cost}_C(q)}{1-\varepsilon}\\ &\le\frac{\alpha\operatorname{cost}_C(q_*)}{1-\varepsilon}\\ &\le\alpha\frac{1+\varepsilon}{1-\varepsilon} \operatorname{cost}_P(q_*). \end{aligned}

所以误差来自两个明确环节：核心集的目标近似与求解器的优化近似。这个不等式链也覆盖最优成本为零的情形；定义本身要求原成本为零的查询在核心集上仍然为零。

精确单均值定理。 令 $P\subset\mathbb R^d$ ， $d\ge1$ ，查询为任意中心 $q\in\mathbb R^d$ ，损失为欧氏平方距离 $f(p,q)=\lVert p-q\rVert^2$ 。任意非负带权输入都存在一个至多 $d+2$ 点、权重非负的精确核心集。

为证明它，定义总质量、一阶矩向量和平方范数矩

M=\sum_pw(p),\qquad m=\sum_pw(p)p,\qquad s=\sum_pw(p)\lVert p\rVert^2.

利用内积展开平方，对每个中心同时得到

\operatorname{cost}_P(q)=s-2\langle q,m\rangle+M\lVert q\rVert^2.

因此，只要子集保持 $(M,m,s)$ ，就保持整个目标函数。若 $M=0$ ，所有输入权重都为零，取空集即可。以下设 $M>0$ ，把每个输入点提升为

z(p)=(p,\lVert p\rVert^2)\in\mathbb R^{d+1}.

归一化矩向量是这些提升点的凸组合：

\left(\frac mM,\frac sM\right) =\sum_{p\in P}\frac{w(p)}M z(p).

由 Carathéodory 定理，它可由至多 $d+2$ 个提升点的凸组合表示。设这些点对应 $C\subseteq P$ ，系数为 $\lambda_c\ge0$ 、 $\sum_c\lambda_c=1$ 。取 $u(c)=M\lambda_c$ ，便分别保持总质量 $M$ 、一阶矩 $m$ 和平方范数矩 $s$ ；代回展开式即证明精确性。提升只用于寻找权重，输出仍是原空间中的输入点。

直觉

核心集把“样本少”改写成“对指定任务足够”。这里每个点对所有查询的贡献都落在同一组函数 $1,q_1,\ldots,q_d,\lVert q\rVert^2$ 的线性组合中，所以再多输入点也只通过 $d+2$ 个系数影响目标。选择少量点并重新加权，就是寻找同一组系数的稀疏表示。

只保留质心会丢失最小残差。令 $\mu=m/M$ ，配方可得

\operatorname{cost}_P(q) =M\lVert q-\mu\rVert^2+ \left(s-M\lVert\mu\rVert^2\right).

第二项是输入相对质心的总平方偏差。在一维，把权重归一化成概率后，它恰为 $M$ 倍的方差。因此质心决定最佳位置，平方范数矩补齐不可消去的残差；二者一起才决定所有中心的成本。这里所需的二阶信息只是标量 $s$ ，无需保存完整协方差矩阵。

凸组合证明也给出可执行的消元。设当前正权重点数超过 $d+2$ ，则齐次矩向量 $(1,p,\lVert p\rVert^2)$ 线性相关，存在不全为零的 $\beta_p$ 满足

\sum_p\beta_p=0,\qquad \sum_p\beta_pp=0,\qquad \sum_p\beta_p\lVert p\rVert^2=0.

由于系数和为零， $\beta$ 必有正项和负项。令

t=\min_{\beta_p>0}\frac{w(p)}{\beta_p},\qquad w'(p)=w(p)-t\beta_p.

正 $\beta_p$ 对应的权重最多减至零，负 $\beta_p$ 对应的权重增加，故没有负权重产生。三个零和等式保证 $(M,m,s)$ 不变，取最小比值则保证至少一个权重恰好变为零。删除零权重点并重复，就把支持集缩减至 $d+2$ 点。全过程的循环不变式是“权重非负且三个矩保持原值”。

例子与边界

取一维输入 $P=\{0,1,2,3\}$ ，四点权重均为 $1$ 。原始矩为

M=4,\qquad m=0+1+2+3=6,\qquad s=0+1+4+9=14.

按点的顺序取 $\beta=(1,-3,3,-1)$ 。直接计算可见

1-3+3-1=0,\qquad 0-3+6-3=0,\qquad 0-3+12-9=0.

因此可以沿这条相关方向消元。步长为 $t=\min\{1,1/3\}=1/3$ ，得到

(w'(0),w'(1),w'(2),w'(3)) =\left(\frac23,2,0,\frac43\right).

删去点 $2$ 后，核心集为 $C=\{0,1,3\}$ 。其三个矩逐一吻合：

\frac23+2+\frac43=4,\qquad 2+\frac43\cdot3=6,\qquad 2+\frac43\cdot9=14.

四个等权点的二次提升具有共同矩中心，删除点二并重新加权后仍保持该中心 — 二次提升中的精确核心集

图中原来的四个提升点与保留的三个提升点都以 $(3/2,7/2)$ 为归一化矩中心。三角形三个顶点的凸组合系数是 $(1/6,1/2,1/3)$ ，乘总质量 $4$ 就得到上述核心集权重。保持这个提升空间中的中心，便同时保持原空间中的位置与平方偏差。

对所有 $q\in\mathbb R$ ，两份数据具有同一个成本多项式：

\operatorname{cost}_P(q)=\operatorname{cost}_C(q) =4q^2-12q+14=4\left(q-\frac32\right)^2+5.

例如 $q=0,3/2,3$ 时，两者成本依次都是 $14,5,14$ 。若只用权重为 $4$ 的新点 $3/2$ 表示输入，虽然仍找到同一个最优中心，却把该处成本从 $5$ 变成 $0$ 。保存“质心、总质量、额外常数 $5$ ”能够回答本例的全部查询，但那采用的是允许新点和加性偏移的摘要接口，不是本文的带权输入子集。

任务换成两个中心时，刚才的精确保证就会失效。取中心集合 $Q=\{0,2\}$ ，每个点的损失为到最近中心的平方距离。原输入成本为

0+1+0+1=2,

而同一核心集的成本为

\frac23\cdot0+2\cdot1+\frac43\cdot1=\frac{10}3.

原因是最近中心的选择随位置变化，损失成为分段二次函数；全局三个矩没有记录各个分配区域中的矩。核心集的有效性始终相对于指定查询族与损失函数，单均值的证明不自动延伸成多中心聚类的保证。

推论与应用

上述消元可直接用于数据流模型。顺序读入正权重点，维护至多 $d+2$ 个代表；新点到来时暂存至多 $d+3$ 点，再对这些点的 $(d+2)\times(d+3)$ 齐次矩矩阵求一个非零零空间向量，并消去至少一点。每次更新都精确保留已读前缀的目标函数，因此结束时得到整份输入的精确核心集。

采用稠密消元，每次零空间求解需要 $O(d^3)$ 次算术运算，总计 $O(nd^3)$ ，工作存储为 $O(d^2)$ 个字，读取输入另需 $O(nd)$ 。这是精确实数算术模型下的计数；有限精度实现还需处理相关性判定及舍入误差，精确有理数实现则需另外计算系数位长的增长。若目的只是回答单均值成本查询，直接累计 $(M,m,s)$ 更省事，预处理后每次查询为 $O(d)$ ；显式扫描至多 $d+2$ 个代表则需 $O(d^2)$ 。保留输入子集的价值在于继续使用接受带权点的已有求解接口。

精确核心集还具有可合并性。将输入分成互不重叠的 $P_1,P_2$ ，分别求出精确核心集 $C_1,C_2$ ，则对每个查询都有

\operatorname{cost}_{C_1\cup C_2}(q) =\operatorname{cost}_{P_1}(q)+\operatorname{cost}_{P_2}(q) =\operatorname{cost}_{P_1\cup P_2}(q).

所以可以先在各个数据块局部压缩，再合并并重新消元至 $d+2$ 点，适用于分布式汇总或分层维护。对于同一 $\varepsilon$ 的近似核心集，直接并集也保持该 $\varepsilon$ ，因为不等式可以逐块相加；若随后再次近似压缩，上下界因子会分别相乘，需要为各层分配误差预算。

本页的 $d+2$ 非负权重上界来自明确的 $\mathbb R^{d+1}$ 二次提升。Jubran、Maalouf 与 Feldman 的准确核心集教程 §3.4.2 使用 $(p,\lVert p\rVert^2,1)$ ，按环境维数给出 $d+3$ 点界；删去这一个冗余常数坐标，便得到这里完整证明的改进。其 §3.4.1 的另一个 $d+2$ 构造允许带符号权重，与本页保持非负权重的凸组合构造不同。

参考资料

Dan Feldman and Michael Langberg, A Unified Framework for Approximating and Clustering Data, STOC 2011, §1、§3：全查询目标近似与强核心集的框架。
Ibrahim Jubran, Alaa Maalouf and Dan Feldman, Introduction to Coresets: Accurate Coresets, 2019, Definition 2、§3.4.1–3.4.2：单均值矩展开、带符号构造与非负提升构造。
Alaa Maalouf, Ibrahim Jubran and Dan Feldman, Fast and Accurate Least-Mean-Squares Solvers, NeurIPS 2019, §2, Theorem 2.2：逐点 Carathéodory 压缩及其算术复杂度。

形式陈述 ​

反向链接

形式陈述