精读笔记
Problem Setting
这篇论文解决的不是一般 matrix completion，也不是低秩恢复的统计问题，而是 rank-one DNN completion 在 QCQP 松弛下的 exactness 问题。给定 bipartite sparsity pattern Omega 和正观测 A_ij，目标是判断 SDP/DNN/CP 松弛是否能恢复 rank-one 非负因子 z，从而补全 X = xy^T。
真正困难点在 lifted formulation：Z = zz^T 中只有与观测边相关的交叉项被约束，其他 entries 是松弛变量。SDP/DNN 松弛可能利用这些自由度得到非 rank-one 的低目标值。因此 tightness 的关键矛盾是：凸锥给了太多 completion 自由度，但 rank-one recovery 要求这些自由度最终必须兼容一个全局一维因子结构。
以前方法要么走高阶 SOS/Lasserre，理论上强但规模不可控；要么在一般 QCQP exactness 文献中依赖 graph sparsity，但没有针对 rank-one DNN completion 给出显式、可读的 tightness certificate。本文卡住的问题正是：能否在低阶 SDP/DNN 层面直接证明 exactness，而不升到高阶矩层级。
Motivation
作者的核心观察是：稀疏 QCQP 的 tightness 可以被看成一个 matrix completion 问题，而不是单纯的 relaxation gap 问题。也就是说，松弛是否 tight 取决于未指定 lifted entries 是否能被选择成 rank-one DNN completion。
已有路线缺的是低阶、结构化、可解释的证书。SOS 路线可以把 rank-one completion 放进 polynomial optimization 框架，但证书维度随阶数膨胀；CP/COP 描述更贴近非负 rank-one 几何，但计算上不可处理。本文试图找到中间层：利用 graph pattern 让 DNN/SPN 证书在某些结构下等价于 CP/COP 证书，同时在 cycle 上显式构造 tightness 条件。
因此动机不是“提出更强松弛”，而是识别什么时候简单松弛已经足够强，以及这种足够强来自哪里。
Core Idea
论文真正的核心是把 exactness 证明从 primal completion 问题转到 dual slack certificate。给定一个 rank-one 最优解 z*，如果能找到 dual variables 使 slack matrix S 与 Z* 满足 complementary slackness，即 Z*S = 0，并且 S 落在相应对偶锥中，那么 SDP/DNN 松弛 tight。这样 rank-one recovery 不再靠求解器“碰巧”输出 rank-one，而是靠显式证书锁定 rank-one 解。
在 cycle graph 上，这个证书可以沿环递推构造。alpha 变量对应边权，beta 调整 anchor 节点。只要这些边权能保持非正，slack matrix 的 Schur complement 会变成一个具有非正 off-diagonal、零行和的 Laplacian-like 矩阵，从而自动 PSD。这是整篇最重要的建模转移：把非凸 rank-one 约束的全局一致性，重写为图上边权传播和 Laplacian PSD。
和 prior 的本质区别在于，它没有通过更高阶 moment 捕捉 rank-one 结构，而是用 sparsity graph 的低阶 dual geometry 捕捉 rank-one completion。scalability 的潜力也来自这里：证书只依赖原图边和局部/累积比值，而不是高阶 monomial explosion。
Method
第一，QCQP formulation 的作用是把 rank-one completion 的双线性约束 X_ij = x_i y_j 放进统一 conic relaxation 框架。z_1 = 1 用来固定尺度，否则 rank-one factorization 有缩放不唯一性；z >= 0 对应 DNN 非负性；r 和 penalty rho 主要是为了得到有界性、Slater 条件和 inequality formulation。
第二，dual equivalence 的作用是处理 CP/COP 的不可计算性。对偶 slack matrix 的 sparsity graph 若每个 block 都是 edge 或 cycle，则 COP membership 等价于 SPN membership。由于 SPN 是 DNN 的对偶，作者得到在这类图上 CP 与 DNN 对偶松弛等价。这个结果不是说 CP 变容易了，而是说在特定 sparsity pattern 下，CP/COP 比 DNN/SPN 没有额外表达力。
第三，tightness certificate 的作用是把 rank-one optimality 变成可构造条件。complementary slackness 给出线性系统，cycle graph 使该系统可递推求解。作者设计 alpha，使它既满足线性系统，又满足 alpha <= 0。后者通过 Lemma 4.3 保证 slack matrix PSD，是连接代数构造与 conic feasibility 的关键桥。
第四，三类 sufficient conditions 分别控制 alpha 的符号：local ratio bound 保证每一步 imbalance 不爆；adding edges 给 alpha 更多自由度，从而去掉上界；cumulative-difference condition 则直接约束沿 cycle 累积的 y-side 与 x-side 差异。这三者本质都是为了保证非正 dual edge weights 可行。
Key Insight / Why It Works
最核心 insight 是：在 rank-one DNN completion 的 cycle sparsity 下，tightness 不是由 SDP 锥本身“神奇”恢复 rank-one，而是由一个可传播的 nonpositive dual certificate 强制出来。alpha <= 0 是关键，因为它让 slack matrix 的 Schur complement 变成 Laplacian 型对象；Laplacian PSD 是整个 tightness 证明的底层机制。
论文最实质的贡献是把 ratio/cumulative 条件和 dual certificate 的符号联系起来。local ratio bound 不是任意技术假设，它控制的是沿 cycle 递推时 cumulative imbalance Delta_k 不超过下一节点的平方尺度，从而避免某些 alpha 变正。一旦 alpha 变正，Laplacian 论证就断掉，PSD 证书不再自动成立。
adding edges 的作用也很清楚：它不是增强求解器，而是增加 dual variables 的自由度，使原来必须沿单一 cycle 传播的 imbalance 可以通过额外边直接吸收。因此条件从双边 ratio bound 退化为一侧 z_{n+j}/z_i >= 1。这里的增益主要来自 graph densification 带来的 certificate flexibility，不是来自更强 conic relaxation。
这篇没有 scaling、retrieval、data coverage 之类因素；它是纯结构性 inductive bias。inductive bias 来自 bipartite graph sparsity 和 nonnegativity：非负性让 ratio/order 条件有意义，cycle 结构让递推闭合，Laplacian 结构让 PSD 可证。没有这些结构，方法很可能不能直接迁移。
辅助部分是 QCQP penalty formulation 和 rho bound。它们让 equality/inequality 两种 formulation 都能纳入同一证书，但核心能力仍来自 theta=0 slack matrix 的构造。rho 只要足够大且 alpha <= rho 即可，增益来源不在 penalty。
Relation To Prior Work
最接近的技术谱系有三条：sparse QCQP exact SDP relaxation、rank-one matrix completion 的 SOS/Lasserre relaxation、以及 CP/COP/DNN cone hierarchy。本文的位置是在 sparse QCQP exactness 与 rank-one completion 之间，用 conic dual certificate 连接二者。
相对 SOS/Lasserre，本文的不同点是拒绝高阶 moment hierarchy，而是在一阶 lifted matrix 上做 tightness。它牺牲了普适性，换来显式条件和可解释证书。看似是 matrix completion 论文，但本质更像 graph-structured QCQP exactness 论文。
相对已有 sparse QCQP exactness 工作，本文新增的是 rank-one DNN completion 语境下对“未指定 lifted entries”的解释，以及 cycle pattern 上可手写的 certificate family。已有工作已经知道 graph structure 会影响 SDP exactness；本文的实质新增信息是：在 rank-one DNN completion 中，cycle 上的 exactness 可以由 ratio/cumulative imbalance 控制，并且加边会放松这些控制条件。
SPN/COP equivalence 本身依赖已有 SPN graph 定理，因此不是 cone theory 的原创突破；它的价值在于把该定理放进 DNN completion dual relaxation 中，说明 CP 对偶在 edge/cycle block 图上不比 DNN 对偶更强。
Dataset / Evaluation
没有数据集意义上的 evaluation，也没有数值实验。论文的验证方式是 deterministic theorem proof。对这类优化理论论文来说，这可以支持“在给定结构和条件下 tight”的 claim，但不能支持更广泛的 practical scalability 或 empirical prevalence claim。
任务覆盖范围较窄：主要是 connected square n x n completion，核心 tightness 定理集中在 cycle graph、cycle 加特定 auxiliary edges，以及 edge/cycle block 的 dual equivalence。没有真实世界矩阵、没有 noisy observation、没有随机采样 regime，也没有大规模 solver 行为分析。
因此 evaluation 能验证的是证书正确性，而不是“该方法在一般 completion 场景中有用”。文中未充分说明这些 sufficient conditions 在典型应用数据或随机 pattern 下是否常见，也未展示求解器是否实际稳定返回 rank-one 解。
Limitation
第一，条件是充分而非必要。local ratio bound、cumulative difference bound、z_{n+j}/z_i >= 1 都可能只是方便构造 alpha <= 0 的技术条件，而不代表 tightness 的真实边界。tightness 可能在更大区域成立，但本文没有刻画。
第二，图结构限制很强。cycle 是可分析的最小非树结构，但一般 sparse bipartite graph 会有多个 cycle、chord、复杂 block interaction；当前递推式 certificate 不明显能推广。Theorem 3.1 的 edge/cycle block 条件也排除了大量实际 sparsity pattern。
第三，加边结果有问题转移的味道。添加 Omega_add 后条件放松，是因为约束图更密、dual 自由度更多；但在 matrix completion 语境下，加边意味着需要更多指定 entries。这不是免费提升，而是在观测模式上引入更强信息。文中对“哪些边最有效”“最少加多少边”“一般图如何加边”未充分说明。
第四，rank-one exact feasibility 是强前提。论文假设存在正的 rank-one solution z*，并围绕它构造证书；对 noisy、inconsistent、approximately rank-one 的情况没有稳定性分析。现实 completion 更常见的是近似低秩和噪声观测，这套 exact certificate 不能直接说明恢复误差。
第五，scalability claim 只能说相对 SOS 更轻，不能说已形成可扩展算法。论文主要给出证书条件，而不是面向大规模实例的检测/求解流程。增益来源是结构可证性，不是 computational engineering。
Takeaway
- 1. 最值得记住的是 tightness-as-completion：稀疏 QCQP 松弛的 exactness 可以被理解为未指定 lifted entries 是否存在 rank-one DNN completion。
- 2. 对 cycle-type sparsity，rank-one recovery 的核心证书是 nonpositive edge weights + Laplacian PSD，而不是 SDP/DNN 锥本身的泛化能力。
- 3. 加边放松 tightness 条件的机制值得迁移：额外 connectivity 可以增加 dual certificate 的自由度，减少沿长 cycle 累积误差的压力。
- 未来更有价值的问题是系统化研究 graph augmentation 与 certificate feasibility 的关系。
一句话总结
这篇论文把 rank-one DNN matrix completion 的 conic relaxation tightness 重写为稀疏图上的 dual certificate 构造问题，并在 cycle 类结构中证明了低阶 SDP/DNN 松弛何时足以恢复 rank-one 解。