精读笔记
Problem Setting
这篇论文实际处理的是 sparse QCQP 的 SDP relaxation exactness 证明问题：不是如何更快求解 sparse SDP，而是如何证明 relaxation 一定能达到 rank-at-most-one optimum。关键困难在于 exactness 是 rank-attainment 性质，不能像 PSD feasibility 那样仅靠 chordal completion 自动局部化。PSD completion theorem 告诉我们 clique-wise PSD 一致即可补成全局 PSD；但 rank-one completion 还要求所有局部 rank-one factor 在 overlap 上一致，尤其多节点 overlap 会产生 off-diagonal product constraints。以前的 exactness 条件大多要求整个 QCQP 同时满足 convexity、sign-pattern、少约束、NIQC/ROG 等某一种全局结构；一旦问题不同区域由不同结构控制，这些全局判据就不够用。本文的关键矛盾是：稀疏性天然支持局部分解，但 rank-one exactness 天然是全局耦合性质。
Motivation
已有路线的不足不在于缺少 exactness 定理，而在于这些定理通常不可组合。Convex QCQP 的 SDP exactness、Z-matrix / sign-pattern exactness、Pataki rank-bound 型结果都能解释某些子结构，但不能直接说明一个由这些子结构拼成的 sparse QCQP 仍然 exact。作者的核心观察是：如果 sparse SDP 已经可以用 chordal clique variables 表示，那么 exactness 也应该尝试在 clique 层面表达；但必须把全局约束 RHS 的分配和 overlap consistency 作为参数显式暴露出来。关键缺口是一个 local certificate 到 global certificate 的拼接原则，而不是又一个单独的 QCQP exactness 条件。
Core Idea
论文真正的核心思想是把 SDP exactness 从“一个全局矩阵是否可取 rank one”改写成“每个 clique-wise local SDP 在全局最优解诱导参数下是否可取 rank one”。具体来说，global clique-wise SDP 的任一最优解会给每个 clique 诱导两类参数：局部 RHS δ，用来记录该 clique 对每条全局约束贡献了多少；consistency matrix U，用来固定该 clique 与其他 clique 共享的矩阵项。固定这些参数后，每个 clique 都变成一个独立 local sub-SDP。如果这些 local sub-SDP 都可以把自己的最优解替换成 rank-at-most-one 解，同时保持同样 δ 和 U，那么这些替换后的局部块自动组成一个全局最优 rank-at-most-one clique-wise 解。
这和 prior 的本质差异是：prior 通常问“整个 QCQP 是否属于某个 exact class”；本文问“能否选择一个稀疏分解，使每个局部块分别属于某个 exact class，并且 overlap 不破坏 rank-one 拼接”。这引入的 inductive bias 是 block-clique sparse compositionality：全局 nonconvexity 可以由若干局部 exactness mechanism 分别吸收，而全局耦合只通过 diagonal shared variables 传递。
Method
第一，作者用 aggregate sparsity graph 的 chordal extension 建立 clique-wise SDP。它解决的是全局 PSD 约束无法直接局部分析的问题；核心变化是把一个大 PSD matrix 变成多个 clique PSD matrices 加 consistency constraints。这里不是为了 computational decomposition，而是为了让 exactness 证明有局部载体。
第二，作者引入 local sub-SDP η_c^p(δ^p,U)。δ^p 解决全局约束 RHS 如何分摊到局部的问题，U 解决 overlapping entries 如何固定的问题。这个参数化是必要的，因为 local subproblem 不是原问题的静态子问题，而是由某个 global optimum 决定的条件化子问题。
第三，Theorem 3.2 给出替换论证：全局最优解诱导的每个局部块本身必须是对应 local sub-SDP 的最优解，否则替换单个块会改进全局目标，矛盾。因此，只要每个 local sub-SDP 存在 rank-one optimum，就可以逐块替换并保持全局最优。这是全文最核心的 proof mechanism。
第四，block-clique assumption 把任意两个 maximal cliques 的交限制为至多一个节点。它解决的是 rank-one factor 在多节点 overlap 上必须满足 u_i u_j = U_ij 的不可预先验证问题。限制到 diagonal consistency 后，只需满足 u_i^2 = U_ii，而 PSD 已保证 U_ii ≥ 0，因此拼接障碍大幅降低。
第五，Section 4 给出可插入框架的 local exactness building blocks：convex、sign-pattern、separable few-constraint，以及 dependent inequalities preservation。它们不是并列模块堆叠，而是给 Theorem 3.2 提供可验证的局部 exactness 来源。
Key Insight / Why It Works
最重要的 insight 是：global optimality 自动把每个 clique block 锁定为某个 induced local sub-SDP 的 optimum。这个事实使得局部 rank-one replacement 不需要重新优化全局问题；只要保持同样 δ 和 U，替换不会破坏全局约束，也不会改变目标值。这是一个很干净的 exchange argument。
真正有效的部分是“参数诱导 + 局部替换 + diagonal consistency”三者的组合。参数诱导让 local problem 精确对齐 global optimum；局部替换把 exactness 变成每个 clique 内部的 rank-one attainability；diagonal consistency 避免 rank-one factors 在 overlap 上需要满足非线性乘积关系。没有 diagonal consistency，local exactness 只能说明每个 clique 内部可 rank one，不能说明这些 rank-one matrices 可以共享同一组 overlap entries。
本文的贡献不是 scaling，也不是 numerical engineering；它是一个 structural certificate。chordal decomposition 本身是已有工具，convex / sign-pattern / rank-bound exactness 也不是新发明。新增信息在于：这些已有 exactness mechanisms 可以通过 induced local sub-SDP 的形式被组合，只要 overlap 足够简单。
也要直接说：block-clique assumption 是这篇论文从“漂亮但很难用的 general theorem”落到“可操作 local certificate”的关键工程化限制。它不是小技术条件，而是避免 off-diagonal rank-one consistency 的核心代价。separable few-constraint 部分的增益也更像把 Pataki rank-bound 放进局部框架，创新性弱于 Theorem 3.2 的拼接机制。
Relation To Prior Work
最接近的谱系有三条：一是 sparse SDP / chordal completion 文献，二是 QCQP SDP exactness 条件，三是 block-clique 结构在 DNN/CPP reformulation 中的使用。本文和 sparse SDP 文献的区别是目标不同：不是降低求解成本，而是利用 clique-wise formulation 证明 rank-one exactness。和 convexity、sign-pattern、rank-bound 等 exactness 文献的区别是粒度不同：它们给单个 QCQP 的全局判据，本文给异质局部判据的组合原则。
看似新的地方中，chordal decomposition、PSD completion、minimum-rank completion、convex/sign-pattern exactness、Pataki rank-bound 都是已有思想；实质创新在于把它们组织成 local-to-global exactness theorem，并明确指出 induced δ 和 U 是正确的局部参数。它也不同于 NIQC/ROG 路线：后者是几何/锥结构的全局性质，不容易局部化；本文选择了更 coefficient-wise、constraint-count-wise 的机制，因为它们对 RHS 和 consistency perturbation 更稳定。
和作者此前 extension results 的关系也清楚：已有 vertical extension 是在固定变量空间中加约束并保持 exactness；本文是 horizontal extension，把不同变量子集上的 exact sub-QCQPs 通过 diagonal consistency 拼起来。这个 framing 是有价值的。
Dataset / Evaluation
这不是经验评估型论文，没有 dataset，也没有 numerical benchmark。Section 5 的 examples 只是在构造层面说明框架能组合 convex、sign-pattern、dependent inequalities、separable few-constraint 等局部机制。它们验证的是 theorem applicability，而不是算法性能、真实问题覆盖率或实际求解收益。
因此，evaluation 对核心理论 claim 是足够的：定理是解析证明，例子展示非空适用域。但它没有证明该框架在真实 sparse QCQP 实例中常见，也没有展示如何自动找到合适 chordal extension / coefficient decomposition。若论文暗含“广泛适用”的 claim，当前 evidence 还不够；更准确地说，它证明了一个结构性可能性，而非 empirical prevalence。
Limitation
最大限制是主框架的可用性依赖未知 induced parameters。Theorem 3.2 说的是：给定一个 global SDP optimum 诱导的 δ 和 U，如果 local sub-SDP exact，则 global exact。对于 convex 和 sign-pattern local classes，exactness 对参数稳定，因此问题不大；但对于 separable few-constraint class，条件显式依赖 δ 和 U，这使 certificate 变得半后验。文中通过例子展示可由其他局部条件强迫 Condition (B)，但一般情形没有系统方法。
第二个限制是 block-clique assumption 很强。许多 chordal extensions 会有多节点 clique intersection，此时 consistency set 包含 off-diagonal entries，rank-one 拼接需要满足 U_ij = u_i u_j。文中没有解决这个问题，而是绕开它。换言之，方法把一部分全局 rank-one 困难转移成了对 chordal extension 结构的要求。
第三，coefficient decomposition A_k = sum_p A_k^p 的选择会影响 local sub-SDP 是否落入 convex / sign-pattern / separable classes。论文承认这一点，但没有给出优化或搜索策略。这意味着框架目前更像 proof design language，而不是自动 certificate generator。
第四，local exactness class 仍偏有限。NIQC/ROG 这类更几何的 exactness 机制被排除在外；这不是偶然，而是因为它们不容易对 induced RHS / consistency 参数保持稳定。框架的上限取决于未来能否发现更多 parameter-stable local exactness conditions。
Takeaway
- 第一，最值得记住的是 exact SDP relaxation 可以被稀疏结构模块化证明：sparsity 不只是 solver trick，也可以是 exactness certificate 的组织原则。
- 第二，local-to-global 成立的关键不是简单“每个局部 exact”，而是“在 global optimum 诱导的 δ 和 U 下每个局部 exact”。
- 这个 induced-parameter viewpoint 很可迁移，可能适用于其他 conic relaxation 的 exactness / integrality 证明。
- 第三，diagonal consistency 是当前框架可操作性的本质前提。
一句话总结
这篇论文把 sparse QCQP 的 SDP exactness 从单一全局判据推进到基于 chordal clique 分解的组合式局部证书，其实质贡献是 induced local sub-SDP 与 diagonal-consistency 下的 rank-one replacement 原理。