矩阵补全的优化间隙与唯一性证书

形式陈述

设 $m,n\ge1$ ， $\Omega\subseteq\{1,\ldots,m\}\times\{1,\ldots,n\}$ 为观测位置。定义掩码 $P_\Omega X$ ：保留 $\Omega$ 上的条目，其余设为零。它是 Frobenius 内积下的正交投影，满足 $P_\Omega^2=P_\Omega=P_\Omega^*$ 。输入 $B=P_\Omega B$ 保存观测数值；外部的零只是存储占位，不是观测为零。

须先选择任务。带惩罚的拟合问题是

F_\lambda(X)=\frac12\|P_\Omega X-B\|_F^2+\lambda\|X\|_*,\qquad\lambda>0. \tag{P}

精确观测约束问题则是

\min_X\ \|X\|_*\quad\text{使}\quad P_\Omega X=B. \tag{E}

前者容许拟合残差，后者必须准确满足观测。二者都连续凸，并由核范数的强制增长保证最小点存在；(E) 的可行集非空，因为 $X=B$ 总可行。它们与直接求最低秩的非凸问题也不同。

对于 (P)，取 $R=B-P_\Omega X$ 。核范数次微分给出必要且充分条件

R/\lambda\in\partial\|X\|_*. \tag{1}

对任意满足 $P_\Omega Y=Y$ 、 $\|Y\|_2\le\lambda$ 的矩阵，令

D_\lambda(Y)=\langle B,Y\rangle-\frac12\|Y\|_F^2.

则 $0\le F_\lambda(X)-F_\lambda^*\le F_\lambda(X)-D_\lambda(Y)$ 。对偶点既要满足谱范数约束，也要只在已观测位置有支撑。

对于 (E)，可行 $X$ 最优当且仅当存在

P_\Omega Y=Y,\qquad Y\in\partial\|X\|_*. \tag{2}

此时 $\|Y\|_2\le1$ ， $\langle B,Y\rangle=\|X\|_*$ ，给出原对偶等值。这里零目标间隙仅证明最优；要证明唯一，后文再检验切空间上的观测单射性与补空间的严格余量。这些都是确定性条件，不是“观测数够多”自动成立的概率结论。

直觉

全观测去噪对每个条目都收取平方残差，所以一次奇异值软阈值足够。补全只对已见条目收费。掩码梯度步先纠正已见位置，保留未见位置的当前猜测，再用核惩罚让整个矩阵共享低维结构。

三项结论要分开：算法是否解好了指定凸目标；这个凸目标是否唯一；其唯一答案是否就是生成数据的真实矩阵。最后一项还取决于观测位置和模型识别。即使已知真实矩阵秩一，核范数最小化也可能偏好一个秩二矩阵，下面给出完整反例。

三个观测固定后，仅右下角可变化；对目标矩阵的切空间补投影会看见这个变化，而观测支持内的对偶矩阵在补空间留有四分之三的严格余量 — 一个缺失位置的唯一补全证书

例子与边界

三个观测如何认证第四格为一

令 $\Omega=\{(1,1),(1,2),(2,1)\}$ ，精确观测为

B_E=\begin{pmatrix}4&2\\2&0\end{pmatrix}.

下标 $E$ 标明本例使用 (E)。候选与正交方向为

M=\begin{pmatrix}4&2\\2&1\end{pmatrix}=5uu^{\mathsf T}, \qquad u=\frac1{\sqrt5}(2,1)^{\mathsf T},\quad v=\frac1{\sqrt5}(-1,2)^{\mathsf T}.

构造

Y=uu^{\mathsf T}-\frac14vv^{\mathsf T} =\begin{pmatrix}3/4&1/2\\1/2&0\end{pmatrix}. \tag{3}

它在未观测格为零，谱范数为一，且补方向系数的绝对值为 $1/4<1$ 。因此 (2) 成立； $\langle B_E,Y\rangle=3+1+1=5=\|M\|_*$ ，先证明最优。

任意可行竞争者为 $M+hE_{22}$ 。令 $T=\{ua^{\mathsf T}+cu^{\mathsf T}:a,c\in\mathbb R^2\}$ ，则 $T^\perp$ 由 $vv^{\mathsf T}$ 张成，并且

P_{T^\perp}(hE_{22})=\frac{4h}{5}vv^{\mathsf T}.

所以非零可行扰动不可能同时属于 $T$ ，即观测在 $T$ 上单射。后文的一般证明进而给

\|M+hE_{22}\|_*-5\ge \left(1-\frac14\right)\frac{4|h|}{5} =\frac{3|h|}{5}. \tag{4}

只要缺失格不是一，目标就严格变大。作为独立复算，任意实二阶矩阵有 $\|X\|_*^2=\|X\|_F^2+2|\det X|$ ；因此在 $X=\left(\begin{smallmatrix}4&2\\2&t\end{smallmatrix}\right)$ 上，核范数平方为 $24+t^2+8|t-1|$ ，其唯一最低点也是 $t=1$ 。

同一候选，在另一份惩罚数据上认证

现在改用 (P)，明确改变观测数据为

B_P=P_\Omega(M+Y)=\begin{pmatrix}19/4&5/2\\5/2&0\end{pmatrix},\qquad\lambda=1. \tag{5}

这是按 KKT 反向构造的可核验实例；并非把上一题的 $B_E$ 原样拿来却声称有同一解。候选仍为 $M$ ，此时 $R=B_P-P_\Omega M=Y$ 。由 (3)， $Y\in\partial\|M\|_*$ ，所以 (1) 成立。

$\|Y\|_F^2=17/16$ 、 $\langle B_P,Y\rangle=97/16$ ，于是

F_1(M)=5+\frac{17}{32}=\frac{177}{32} =D_1(Y). \tag{6}

它也是近端梯度的固定点： $M+Y=6uu^{\mathsf T}-vv^{\mathsf T}/4$ ，奇异值为 $6,1/4$ 。对它软阈值一，保留 $5uu^{\mathsf T}=M$ ，并消掉负特征方向对应的奇异项。

从零开始时，第一次输入是 $B_P$ ，不是 $M+Y$ 。 $B_P$ 的特征值为 $(19\pm\sqrt{761})/8$ ，一正一负且两者绝对值都大于一，因此第一步为

X_1=B_P-\frac1{\sqrt{761}} \begin{pmatrix}19&20\\20&-19\end{pmatrix}. \tag{7}

第一步的两个奇异值均非零，不能用“本轮秩二”判断算法失败。后续掩码步会把 $X_{1,22}$ 保留为新猜测；每轮把右下角重新置零再阈值，就会重复第一步，永远没有执行正确的补全迭代。

秩一可识别，也不保证核松弛找回它

保持同一三格观测模式，改观测为 $(1,2,2)$ 。所有可行矩阵为 $X(t)=\left(\begin{smallmatrix}1&2\\2&t\end{smallmatrix}\right)$ 。秩一要求行列式 $t-4=0$ ，因此在秩一模型中唯一可识别的答案是 $t=4$ ，核范数为五。

但 $X(1)$ 的特征值为 $3,-1$ ，核范数仅为四。更精确地，

\|X(t)\|_*^2=9+t^2+2|t-4| =\begin{cases}16+(t-1)^2,&t\le4,\\(t+1)^2,&t\ge4.\end{cases}

唯一核范数最优点是 $t=1$ ，它秩二。低秩模型的识别与凸松弛的成功之间还差一份恢复条件，不能由“秩很低”或“只有一格未见”跳过。

更基本的不可识别例子是只观测第一行 $(1,1)$ 。全部矩阵 $\left(\begin{smallmatrix}1&1\\t&t\end{smallmatrix}\right)$ 都秩一且具有相同观测，任何算法都无法从这些数据确定真实 $t$ 。核范数会偏好 $t=0$ ，只是优化模型的选择，不是数据揭示了真值。

推论与应用

掩码近端梯度、合法gap与不变量

(P) 的光滑梯度为 $\nabla g(X)=P_\Omega X-B$ ，其 Lipschitz 常数至多一。固定 $0<\alpha\le1$ ，从 $X_0=0$ 开始，执行

Z_k=X_k+\alpha(B-P_\Omega X_k),\qquad X_{k+1}=\mathcal S_{\alpha\lambda}(Z_k). \tag{8}

特别是 $\alpha=1$ 时， $Z_k=B+P_{\Omega^c}X_k$ ：已观测位置替换成输入，未观测位置保留上次估计。这个等式是可以逐轮检查的算法不变量，不说明输出 $X_{k+1}$ 仍精确拟合观测；(P) 允许输出收缩。

近端梯度的三点证明适用于向量化后的矩阵空间，给出 $F_\lambda(X_k)$ 不增、点收敛到某个最优解，以及

F_\lambda(X_k)-F_\lambda^*\le \frac{\|X_0-X^*\|_F^2}{2\alpha k}.

只对已观测残差 $R=B-P_\Omega X$ 取

Y=R/\rho,\qquad\rho=\max\{1,\|R\|_2/\lambda\}, \tag{9}

即可同时保证支撑与谱范数约束。若用 $B-X$ ，未观测位置往往非零，会违反对偶支撑。对合法 $Y$ ，平方展开和核—谱对偶给

F_\lambda(X)-D_\lambda(Y)= \frac12\|R-Y\|_F^2+\lambda\|X\|_*-\langle X,Y\rangle\ge0. \tag{10}

内积能写成 $\langle X,Y\rangle$ 正是因为 $Y=P_\Omega Y$ 。当 gap 达到所需 $\varepsilon$ 时，返回当前 $X,Y$ 、gap、迭代数及定标；预算到期则报告未达标。负gap首先触发支撑、谱范数或数值误差检查，不视作超越最优。

每轮掩码操作在观测列表上为 $O(|\Omega|)$ ；若显式存储矩阵，构造输入及输出另为 $O(mn)$ 。完整稠密 SVD 为 $O(mn\min(m,n))$ ，认证残差的谱范数在最直接实现中还需一次同阶分解；可缓存或采用经认证上界，但不能把证书费用省略。 $k$ 轮总成本按这些费用相乘。低秩因子输出减少存储不等于已经证明部分 SVD 的精确性。这里复用确定性近端梯度，没有另创一个没有误差账本的随机或加速版本。

精确约束为什么存在这种对偶点

(E) 的对偶为

\max_Y\ \langle B,Y\rangle, \qquad P_\Omega Y=Y,\quad\|Y\|_2\le1. \tag{11}

充分性直接可见：每个可行 $X$ 都有 $\langle B,Y\rangle=\langle X,Y\rangle\le\|X\|_*$ 。取到等号恰为核范数的次梯度条件。

必要性可用有限维 Fenchel 资格。将 $P_\Omega$ 的值域视为只含观测位置的矩阵空间，写 $f(X)=\|X\|_*$ 、 $g(Z)=\delta_{\{B\}}(Z)$ 。 $f$ 在全空间有限连续，任意可行 $X$ 满足 $X\in\operatorname{ri}(\operatorname{dom}f)$ 和 $P_\Omega X=B\in\operatorname{ri}\{B\}$ ，故资格成立，且已知最小点存在。于是有最优乘子；改变符号并嵌回观测支撑空间，就得到 (2)。这说明非严格的支持次梯度条件是最优性的充要条件；下面更强的条件仅作为唯一性的充分证书。

切空间证书的完整唯一性证明

对可行候选 $M=U\Sigma V^{\mathsf T}$ 、秩 $r$ ，定义线性空间

T=\{UA^{\mathsf T}+CV^{\mathsf T}:A\in\mathbb R^{n\times r},\ C\in\mathbb R^{m\times r}\}.

它是固定秩矩阵在 $M$ 处的切空间；本证明只使用这一明确的线性表达。令 $P_U=UU^{\mathsf T},P_V=VV^{\mathsf T}$ 。按正交投影分块，有

P_{T^\perp}H=(I-P_U)H(I-P_V),\qquad P_TH=P_UH+HP_V-P_UHP_V. \tag{12}

在左右基分别扩充后的四块中， $T^\perp$ 只保留右下块，其余三块组成 $T$ ，故 (12) 确实是正交分解。

假设存在 $Y$ 满足

P_\Omega Y=Y,\qquad P_TY=UV^{\mathsf T},\qquad \eta:=\|P_{T^\perp}Y\|_2<1, \tag{13}

并且 $\ker P_\Omega\cap T=\{0\}$ 。那么 $M$ 是 (E) 的唯一解。证明如下。

令 $H\ne0$ 为任意可行扰动，即 $P_\Omega H=0$ ，写 $H_\perp=P_{T^\perp}H$ 。若 $H_\perp=0$ ，则 $H\in T\cap\ker P_\Omega$ ，与单射性矛盾，所以 $H_\perp\ne0$ 。对 $H_\perp$ 的 SVD 取左右奇异向量乘积之和 $W_H$ 。它仍在 $T^\perp$ 中， $\|W_H\|_2=1$ ，并且 $\langle W_H,H_\perp\rangle=\|H_\perp\|_*$ 。

由核范数次微分公式， $UV^{\mathsf T}+W_H$ 是 $M$ 处的次梯度。再令 $W=P_{T^\perp}Y$ ，利用 $\langle Y,H\rangle=0$ ，得到

\begin{aligned} \|M+H\|_*-\|M\|_* &\ge\langle UV^{\mathsf T}+W_H,H\rangle\\ &=\langle W_H-W,H_\perp\rangle\\ &\ge(1-\eta)\|H_\perp\|_*>0. \end{aligned} \tag{14}

因此任意其他可行矩阵都更差。例 (3) 逐项算出了 $\eta=1/4$ 与单射性，而不是只引用这个定理。

严格性是充分条件的一部分，并非每个唯一最优点都必须具有严格证书。例如三个已观测格都为一，候选全一矩阵的缺失格为 $t=1$ 。沿唯一自由格，核范数平方为 $3+t^2+2|t-1|$ ，在 $t\le1$ 时为 $4+(t-1)^2$ ，在 $t\ge1$ 时为 $(t+1)^2$ ，所以唯一最小点仍是 $t=1$ 。但其支撑次梯度必须取 $Y=\left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right)$ ，补空间范数恰为一，无法通过 (13)。证书测试不通过时，应报告“这份充分证书未建立”，不能报告“不唯一”。

两道短自测

对 (5) 的最优点 $M$ ，用完整差 $B_P-M$ 替代已观测残差会怎样？答案：右下角变为 $-1$ ，违反 $P_\Omega Y=Y$ ；即使再缩放到谱球内，也没有修复支撑错误。
三个观测为 $(4,2,2)$ ，某可行候选把缺失格填为 $3/2$ 。与最优核范数五相比，(4) 给出的差距下界是多少？答案： $h=1/2$ ，至少 $3/10$ 。实际差距可以更大；这是确定性下界，不是统计置信区间。

参考资料

Emmanuel J. Candès and Benjamin Recht, Exact Matrix Completion via Convex Optimization，作者稿，§3、式(3.4)–(3.5)、Lemma 3.1（印刷页15–16）：切空间、支撑对偶与严格唯一性证书。本页证明并使用确定性引理，不宣称已证明全文的随机采样恢复率。
Jian-Feng Cai, Emmanuel J. Candès and Zuowei Shen, A Singular Value Thresholding Algorithm for Matrix Completion，§2.1 的近端映射与 §2.3、式(2.10)的带惩罚补全固定点。其式(2.7)的命名 SVT 迭代针对另一个带 Frobenius 正则的精确约束模型，不与本页 (8) 混用。
Neal Parikh and Stephen Boyd, Proximal Algorithms，§4.2 与 §6.7：复合算法和矩阵近端；本页单独检查掩码的梯度常数、对偶支撑与证书费用。

形式陈述 ​

三个观测如何认证第四格为一 ​

同一候选，在另一份惩罚数据上认证 ​

秩一可识别，也不保证核松弛找回它 ​

掩码近端梯度、合法gap与不变量 ​

精确约束为什么存在这种对偶点 ​

切空间证书的完整唯一性证明 ​

两道短自测 ​

反向链接