Fitting an ellipsoid to random points: predictions using the replica method
Antoine Maillard, Dmitriy Kunisky
cond-mat.dis-nn, cond-mat.stat-mech, cs.DS, math.PR, math.ST
2023-10-02
用统计物理副本方法解析给出，d维n个高斯点的过原点椭球拟合在α=n/d²时相变位于α=1/4，且核范数最小化覆盖整个SAT相。
给定 d 维空间里 n 个标准高斯随机点，能不能找到一个以原点为中心的椭球，让这 n 个点都落在边界上？写成半定规划：求对称矩阵 S ⪰ 0，满足 xμ^T S xμ = d。大维极限取 n、d → ∞ 且 n/d² → α > 0。S 的特征向量是主轴方向；距离按 √d 缩放后，单位球面 S = I 的轴长全是 1。
这个问题从 Minimum Trace Factor Analysis 进来，后来连到平均情形 discrepancy 的 SDP 松弛和过完备 ICA。数值模拟加一条类比给出猜想：α < 1/4 几乎必然有解（SAT），α > 1/4 几乎必然无解（UNSAT）。类比是把 rank-1 矩阵 xx^T 换成 GOE 高斯矩阵，Gordon 逃逸定理（随机仿射子空间与凸锥相交的经典相变）把临界点钉在 PSD 锥的统计维数，渐近就是 d²/4。真问题里仿射子空间不是均匀取向，Gordon 给不出结论。
严谨 SAT 从 n = O(d^{6/5-ε}) 推到 O(d^{3/2-ε})、O(d²/polylog d)，最近到 n ≤ d²/C（C 很大）。UNSAT 唯一硬上界仍是线性无关：n 超过对称矩阵维数即 α > 1/2。均方误差放到 Θ(1/d) 时，单位球面自己就能过关；精确拟合才保留尖锐相变。
解集是凸的，Gibbs 测度对数凹，副本对称成立：解空间是单团簇，不会碎成多团。
把解集体积写成配分函数 Z，自由熵 Φ = lim (1/d²) E log Z。SAT 相 Φ 有限，靠近相变 Φ → −∞。副本方法先算整数阶矩 E[Z^r]，解析延拓后对 r 求导再令 r → 0，用绕路算 E log Z。重叠 Qab = (1/d) Tr[R^a R^b] 是序参量。有效积分里出现 extensive-rank 的 HCIZ 积分：正交群上 exp(θ d/2 Tr[O R O^T Y]) 的积分，大 d 极限只看两矩阵的谱，精确式要解 Burgers 方程，极难用。靠近 SAT/UNSAT 时解空间缩成一点，θ → ∞，dilute 展开的首项就是两矩阵按特征值排序后对齐。
同一套自由熵覆盖一类显式构造：在线性约束下最小化 Tr[V(S)]。V(x) = |x|^γ 是 Schatten-γ 范数（γ = 1 核范数，γ = 2 Frobenius / 最小二乘）；V(x) = |x−1|^γ 是从单位阵出发的扰动。零温极限 β → ∞ 给出这些凸程序最优解的谱。
高斯点的 SAT/UNSAT 相变位于 α = 1/4。
这是该猜想的第一份解析推导。α < 1/4 时 Φ 收敛到有限值，α ↑ 1/4 时 Φ → −∞。
α < 1/4 时，均匀抽样的可行 S 的经验谱收敛到副本方程给出的 μ[α]。靠近相变，μ 趋于 μc：零点处有质量 1/2 的原子，连续部分是半径 3π/2 的四分之一圆，支撑在 [0, 3π/2]。大约一半主轴退化、长度发散，拟合椭球变成椭圆柱。d = 100、α = 0.24、50 次实现里，|λ| < 10^{-3} 的特征值比例约 0.52。约束改成 S ⪰ κ I 后相变下移到 αc(κ) ≤ 1/4，κ → 1 时 αc → 0；给定 α < 1/4，任何拟合椭球的最长主轴至少是某个 ℓ⋆(α) = [κ⋆(α)]^{-1/2}。
| 方法 | 阈值 αc | 对照 |
| min ∥S∥（核范数） | 1/4 | 覆盖整个 SAT 相 |
| min ∥S∥F（最小二乘） | 1/10 | 先前数值约 1/17 |
| min ∥S − I∥F | 1/10 | 与最小二乘相同 |
| min ∥S − I∥op | ≈ 0.1892 | 仍低于 1/4 |
核范数最小化在整个 SAT 相都给出 PSD 解，谱与均匀抽样的典型解相同；α > 1/4 后谱变成两段截断半圆加零点原子。最小二乘的谱是均值 1、方差 2α/(1−2α) 的半圆，左端碰到 0 时正好 α = 1/10。先前把阈值读成约 1/17，更接近有限维效应。
对旋转不变向量 x = √χ · ω（ω 均匀在球面），相变只取决于范数涨落 τ = lim d · Var[∥x∥²/d]。高斯是 τ = 2、αc = 1/4；τ → 0 时 αc → 1/2；τ → ∞ 时 αc → 0。范数完全冻住时单位球面本身就是解。
椭球拟合猜想现在有了钉在 α = 1/4 的解析图像，并且把「解在不在」和「谁能找到解」拆开了。核范数凸程序是这套计算给出的、能跑满整个存在性区间的构造；最小二乘只能用到 SAT 相的 40%。做 MTFA、discrepancy 松弛、过完备 ICA，可以把这些阈值当设计数。
companion paper 用这里的自由熵普适性（低维投影的均匀 CLT，把问题映到 GOE 测量模型），把一个略放松的「几乎精确」版本严格做到 n ≃ d²/4。
原问题的严格证明还没有。相变附近典型秩约 d/2，Grothendieck 那套有限秩近似走不通。
副本方法不是证明：整数阶矩的解析延拓、d → ∞ 与 r → 0 的极限对调都没有着落。正文把结论写成 Claim，companion 严格的是修改后的问题。
HCIZ 精确式基本没用上，分析几乎全靠 dilute 展开。α 远离 1/4 时典型谱只以隐式方程存在，高阶 (1−4α) 展开留作后续。非旋转不变的方向分布没做：ω 冻成固定向量时拟合必然失败，需要多少 delocalization 才能恢复普适性仍是开放问题。τ 随 d 趋于 0 的中间尺度也没做。
有限维实验是 d = 100、Mosek 解 SDP，靠近 α = 1/4 条件数变差。核范数最小化子 likely hard to characterize mathematically，升格成严格存在性证明还差一步。