精读笔记
Problem Setting
这篇论文实际处理的是 SDP 中 PSD cone 的外逼近求解：从一个 LP/SOC/其他 conic relaxation 出发，迭代加入对 Sn_+ 有效的线性 cut，逐步逼近 SDP feasible set。表面问题是 SDP 求解的 scalability，真正问题是 PSD 约束的半无限线性化中 separator 如何选择。
已有 eigencut 路线很自然：当前解 X 非 PSD 时，取最小负特征值对应的 vv^T，加入 <vv^T, X> >= 0。但 rank-one cut 的局部性很强，可能需要很多轮，而且 dense eigenvector 会让 master LP 变差。nuclear cut / higher-rank cut 可以一次覆盖更多负谱方向，但 cut 更重，重优化成本和数值行为不一定更好。sparse eigencut想降低 cut 密度，但 separation 变成组合问题。
关键矛盾是：PSD violation 是 spectral 的，但 master problem 的可解性很大程度由 cut 的 algebraic complexity 控制。强 cut、深 cut、稀疏 cut、低 rank cut不是同一个目标；以前工作往往各自提出一种 cut family，没有统一的尺度解释它们之间到底在 trade off 什么。
Motivation
作者的动机不是发明一个全新的 SDP solver，而是把 PSD cutting-plane 中“separator normalization”这件事正规化。因为 <S, X> >= 0 对 S 的正缩放不敏感，必须先选一个代表切片，否则“最 violated”没有意义。既然 PSD cone 是 spectral object，合理的代表切片应由 unitarily invariant norm 描述；而这类 norm 正好由 symmetric gauge 诱导。
核心观察是：eigencut 和 nuclear cut 不是两个孤立技巧，而是同一个 self-dual PSD cone separation problem 在不同 spectral gauge normalization 下的端点。缺口在于中间连续谱、rank-limited 版本、sparse support 版本，以及这些选择对 convergence / cut depth / master cost 的影响缺少统一语言。
因此这篇论文的出发点是“缺一个切平面设计空间”，而不是“缺一个更快的 eigenvalue oracle”。
Core Idea
论文真正的核心思想是：把 PSD-valid cut 的生成看成在 Sn_+ ∩ B_phi 上解线性 separation，其中 B_phi 是某个 symmetric gauge 诱导的 spectral norm unit ball。这样 separator S 的 spectrum 被 gauge 约束，cut family 的结构由 gauge 决定。
这个建模方式改变了 cut generation 的自由度：过去是从负特征向量中取一个方向，或者手工构造某类 higher-rank separator；现在是先选一个 spectral inductive bias，再自动得到最 violated separator。l1 gauge 对应 trace-normalized PSD separator，极点是 rank-one eigencut；l2 gauge 给出 X^- / ||X^-||_F，是 Frobenius-depth 最深 cut；linf gauge 给出负特征子空间 projector，对应 nuclear cut。
本质区别在于 prior work 多是在 cut family 层面离散地提出构造，而本文把这些 family 放进一个 dual-gauge calculus：cut 的 violation 等于负谱向量的 dual gauge。这使得“选择 cut”变成“选择如何聚合负特征值”。
Method
1. Spectral-gauge separation：解决 separator 缩放任意性。作者限制 S ∈ Sn_+ ∩ B_phi，其中 B_phi 是 phi(lambda(S)) <= 1 的 spectral unit ball。这样每个 PSD separator 都有规范代表，并且 separation 完整：若所有这些 cut 都非负，则 X PSD。
2. Closed-form oracle：解决 oracle 是否可实现的问题。Theorem 3.3 表明 g_phi(X) = -phi^circ(lambda^-(X))，最优 S 与 X 共享特征向量，权重 z 是 dual gauge maximizer。核心变化是把矩阵分离问题降成负谱上的向量范数问题。
3. lp hierarchy：解决已有 cut family 的统一解释。p=1 给 eigencut，p=2 给 Frobenius cut，p=infty 给 nuclear cut，中间 p 给连续插值。这里的核心不是 lp 本身，而是不同 p 对负谱聚合方式不同：max、Euclidean energy、sum。
4. Sparse support extension：解决 cut 密度问题，但代价是组合搜索。固定 support I 时只需对 principal submatrix X_I 做同样 oracle；可变 support m 时等价于在所有 |I|<=m 的 principal blocks 上找最大 violation，对应 factor-width hierarchy。这里把困难清楚地隔离出来：谱分离仍简单，support 选择才难。
5. Rank-limited separator：解决 higher-rank cut 成本控制问题。通过 k-sparse spectral gauge，只保留 k 个最负 eigenvalues，oracle 仍 closed-form。它不让 cut entrywise sparse，但能控制 spectral complexity 和 LP 重优化负担。
Key Insight / Why It Works
最关键的 insight 是：PSD violation 的全部有效信息，在 spectral-gauge normalization 下，可以压缩为 lambda^-(X)。separator 不需要在整个 Sn_+ 中搜索；最优 separator 必然对齐当前矩阵的负特征子空间。这来自 PSD cone 的 self-duality、Von Neumann trace inequality、以及 symmetric gauge 的 duality。换句话说，方法有效不是因为 Kelley method 新，而是因为它找到了 PSD separation 的正确坐标系。
Frobenius cut 值得特别注意。它不是简单的“rank 多一点”，而是在 Frobenius distance/depth 意义下最深：S = X^- / ||X^-||_F。这个解释比实验数字更重要，因为它说明 l2 gauge 的优势来自几何深度，而不是偶然调参。nuclear cut 虽然 violation 最大趋势更强，但它可能过度聚合整个负子空间，增加 master reoptimization burden；eigencut虽然单步弱，但每个 cut 简单，长期可能更稳定。
rank limit 的有效性更像 test-time compute / complexity allocation：每轮根据负谱保留部分方向，用较少 spectral degrees of freedom 换取较可控的 master cost。它不是新的 convex relaxation，本质上是 cut normal 的谱压缩。
entrywise sparse 部分更像把已有 sparse eigencut / factor-width 思想嵌入框架。实质贡献是关系澄清，不是解决了 sparse separation 的难题。文中也显示，一般 sparsity pattern 下 closed form 消失；这说明 spectral gauge 的 tractability 依赖 orthogonal invariance，一旦破坏这个结构，核心机制就不再工作。
实验增益有相当部分可能主要来自 engineering / scaling：LP 初始 relaxation 很便宜，允许更多迭代；SOC 初始 relaxation更强但单轮重，短时间反而差。不同 gauge 的表现不能脱离 master solve time 解释。论文没有充分分解“cut 更强”和“每轮更贵”之间的贡献。
Relation To Prior Work
最接近的谱系是 SDP cutting-plane / PSD cone outer approximation，尤其是 Ramana/Shor eigencut、RLT/PSD cuts、Dey et al. 的 sparse eigencut，以及 Bertsimas-Cory-Wright 的 nuclear cuts 和 polyhedral/SOC decompositions。
和 eigencut 的本质差异：eigencut只看最小负特征方向，本文把它解释为 trace-normalized PSD separator 的最优解，即 l1 spectral gauge 的端点。它不是替代 eigencut，而是把 eigencut放进更大的 normalization family。
和 nuclear cut 的本质差异：nuclear cut 对应 spectral norm normalization 下的 full negative eigenspace projector，即 linf gauge。本文新增的是 gauge-duality 解释和中间谱，而不是 nuclear cut 本身。
和 sparse eigencut / factor-width hierarchy 的关系：本文把固定 principal support 的 separation 化为子矩阵上的 spectral-gauge oracle，并把 bounded support 与 factor-width cone dual 联系起来。这里更多是统一和重组已有思想，实质创新在于 general gauge + block restriction 的表达，而不是解决组合 support optimization。
真正新增的信息是 closed-form spectral-gauge oracle 和由此得到的 lp/rank hierarchy。它属于“用 convex/spectral geometry 重新组织已有 SDP cuts”的方法演化，而非一个新的优化范式。
Dataset / Evaluation
评估覆盖 BoxQP 和 SPCA，两者都属于 SDP relaxation 常见应用场景，并且能体现 cutting-plane bound 在非凸/组合优化中的用途。小规模实例用 MOSEK SDP bound 作为 best，大规模实例则用测试策略中的 30 分钟 best bound 作为 virtual best。
实验支持三个有限 claim：第一，框架容易实例化不同 cut template；第二，没有单一 gauge 全面占优；第三，LP relaxation + eigencut/Frobenius cut 在很多场景是稳健折中。它没有支持更强 claim，比如“spectral-gauge cuts 普遍优于已有方法”或“higher-rank cuts 在大规模一定更好”。
评价的主要 limitation 是大规模没有真实 SDP optimum，gap closed 是相对 tested strategies 的指标，存在策略集合依赖。另一个问题是实验使用 basic Kelley scheme、单 cut per iteration、缺少 cut management；这有利于展示框架干净性，但离实际高性能 SDP cutting-plane implementation 还有距离。
没有真实 branch-and-bound 集成实验，因此“可嵌入 global optimization framework”的动机没有被完整验证。当前实验更像 oracle family benchmark，而不是 end-to-end solver benchmark。
Limitation
1. 核心 tractability 强依赖 orthogonal invariance。只要 separator 约束不是 spectral-compatible，例如一般 sparsity pattern，closed-form oracle 就失效。这限制了框架对真正稀疏大规模 SDP 的直接价值。
2. Rank-limited cuts 不等于 sparse cuts。它们降低了 spectral rank，但 cut matrix 通常仍 dense；对 master LP 的稀疏结构改善有限。文中关于 rank 对 reoptimization 的影响有观察，但机制归因不充分。
3. Convergence bound 很弱。体积 packing bound 说明 epsilon termination，但维度 d=n(n+1)/2，实际不可用于预测算法行为。理论没有解释为什么某个 gauge 在某类实例上更快。
4. 增益来源不清。LP vs SOC 初始 relaxation、cut rank、cut depth、LP barrier solve time、eigen-decomposition time、实例 density 都混在一起。很多结果可能主要来自 scaling / master problem cost，而不是 spectral gauge 本身。
5. Sparse support 版本把问题转移给组合搜索。固定 support 很优雅，可变 support 才是真问题；文中没有给出强 oracle 或 scalable heuristic 的理论保证。
6. 大规模 evaluation 的 best bound 是内部相对指标，不是 ground truth SDP optimum。它能说明策略相对表现，但不能说明最终 bound 离 SDP relaxation 还有多远。
Takeaway
- 1. 最值得迁移的 insight 是：当 cone constraint 的 valid inequalities 对 scaling 不敏感时，先选择一个几何上自然的 normalization slice，cut family 的设计会变得清晰很多。
- 2. 对 PSD cone，separator 的本质信息是负谱如何被聚合。
- l1/l2/linf 分别代表最坏方向、负谱能量、负子空间总体质量；这比简单说 rank-one / full-rank 更有解释力。
- 3. Frobenius cut 的价值在于 depth optimality，而不是它是“中间 p”。
一句话总结
这篇论文把 SDP cutting-plane 中的 eigencut、Frobenius cut、nuclear cut 和 rank/sparsity 变体统一为 symmetric-gauge 归一化下的 PSD spectral separation，是一次以谱几何重写 cut family 设计空间的工作，而不是一个本质全新的 SDP 求解器。