低维聚类中低阶多项式方法的计算下界

针对簇数 $K$ 远大于维度 $d$ 的混合分布聚类，新研究证明在多对数中心间距下，低阶多项式算法所需的样本量下界为 $n \gtrsim K^2d^{3/2}$。该下界通过基于对偶 BCH 码构建的 $2K$ 个乘积伯努利混合分布（$K=(d+1)^m$）推导得出。通过高斯化论证，该计算硬度结果可进一步推广至各向同性高斯混合模型。