组与矩阵：从结构化收缩到可核验证书 ​

形式陈述 ​

这个终点要求提交两份可重算的报告：一份对整组变量做选择，一份对矩阵奇异方向做收缩。每份报告列出输入、目标定标、更新、合法对偶点、停止间隙、实际成本，以及结论没有保证的对象。

最短组路线是近端算子理路近端算子Proximal operator · Proximity operator在降低凸函数值与保持靠近输入点之间取得精确平衡的单值算子。 → 组Lasso证书理路组 Lasso 的块收缩与对偶证书Group Lasso proximal certificate · Block soft thresholding · 组软阈值对不相交变量组推导径向近端收缩，以整组残差相关性建立KKT和可行对偶间隙，并在耦合设计上认证停止。。会基本矩阵乘法和次微分即可完成任务一、二；一般近端梯度的证明在原页，不要求重学标量Lasso的全部求解器。

矩阵可选支线是SVD理路奇异值分解Singular value decomposition · SVD任意有限维线性映射都可在正交规范基下表示为非负对角伸缩。 → 核范数近端理路核范数近端映射与奇异值软阈值Nuclear norm proximal map · Singular value soft thresholding · 核范数近端收缩推导核范数的完整次微分，以谱范数残差证明奇异值软阈值的唯一最优性，并区分核惩罚、截断SVD和逐项稀疏。 → 补全证书理路矩阵补全的优化间隙与唯一性证书Matrix completion certificate · Nuclear norm completion dual certificate · 核范数补全证书以掩码近端梯度求解带核惩罚的观测损失，用支持受限的谱范数对偶点认证误差，再以切空间严格证书证明精确补全唯一性。，完成任务三至六。已会SVD者直接从核范数近端开始。证明唯一性的切空间部分是进阶终点，完整答案仍在这里给出。

下载固定算例核验器。它仅需 Python 3 标准库，不访问网络、不写文件；默认先用有理数核验精确证书，再以浮点执行两条确定性迭代并报告 gap。允许的浮点门槛不小于 ${10}^{-10}$；计算gap为负时报告数值分辨率不足，预算用尽时先打印最后状态和gap再非零退出。它是这些例子的复算工具，不是一般矩阵补全软件。正文的精确证明独立于脚本。

直觉 ​

对偶证书的形状随惩罚改变：标量绝对值对应区间，组欧氏长度对应球，核范数对应谱范数球。只要把正确的可行域和损失定标带进报告，候选来自哪种迭代就不影响上下界含义。

数据部分又改变了证书：普通回归限制 $A_g^{\mathsf{T}}\theta$，缺失矩阵必须额外限制对偶矩阵只在观测位置有支撑。把一个熟悉的公式写进错误的可行域，会产生没有依据的精度数字。

例子与边界 ​

任务一：从耦合设计算出第一轮，再用KKT确定终点 ​

固定

$$A=\left(\begin{array}{ccc}1& 0& 3/5\\ 0& 1& 0\\ 0& 0& 4/5\end{array}\right),b=(18/5,24/5,0{)}^{\mathsf{T}},P(x)=\frac{1}{2}\Vert b-Ax{\Vert }^2+\sqrt{x_1^2+x_2^2}+|x_3|.$$

从零开始，取 $\alpha =5/8$。要求：算梯度候选、每组阈值、第一步、可行对偶点及gap；再用 $x^{\ast }=(3,4,0)$ 给出精确最优证书。

答案：$A^{\mathsf{T}}A$ 的最大特征值为 $8/5$，步长有效。梯度候选为 $(9/4,3,27/20)$，阈值为 $5/8$，第一组长度 $15/4$，因此

$$x_1=(15/8,5/2,29/40),r_1=(129/100,23/10,-29/50),A^{\mathsf{T}}{r}_1=(129/100,23/10,31/100).$$

令 $\rho =\sqrt{69541}/100$、${\theta }_1=r_1/\rho$；组相关性长度为 $1$ 和 $31/\sqrt{69541}$。于是

$$P(x_1)=29981/4000=7.49525,D({\theta }_1)=\frac{3921}{250\rho }-\frac{14581}{4000{\rho }^2}\approx 5.423339084,$$

第一轮 gap 约为 $2.071910916$。未缩放的残差越过第一组对偶球，不能当作证书。

在 $x^{\ast }=(3,4,0)$，残差 $(3/5,4/5,0)$ 给出组相关性 $(3/5,4/5)$ 与 $9/25$。前者方向等于活动组除以其长度五，后者严格在单位球内，故 KKT 成立。$P=D=11/2$，满列秩保证唯一。

标准库核验器采用固定步长、从零初始化、每轮完整重算残差和全部组相关性。一次实跑的诊断如下；小数不是区间算术证明：

轮次	原始目标	可行对偶值	gap
0	18	5.5	12.5
1	7.49525	5.423339084	2.071910916
2	6.009763502	5.488863719	0.520899783
5	5.501650438	5.499353586	0.002296852
10	5.5000000853	5.4999999878	$9.7422\cdot {10}^{-8}$
12	5.5000000017	5.4999999998	$1.8183\cdot {10}^{-9}$

以 ${10}^{-8}$ 为数值诊断门槛，第12轮首次达标。报告中仍保留阈值和浮点容差，不把这个特例的速度称为普遍收敛率。

任务二：迁移权重，再故意破坏分组条件 ​

先取 $A=I_4$，两组输入分别为 $(3,4),(0,3)$，$\lambda =1$、$w_1=2,w_2=1$。求输出和等值证书。

答案：输出 $((9/5,12/5),(0,2))$，残差 $((6/5,8/5),(0,1))$，其组长度为二和一。平方损失为 $5/2$，惩罚为八，故 $P=D=21/2$。组内各非零坐标并没有分别减去二；保持的是整组方向。

再令组为 $\{1,2\}$ 与 $\{2,3\}$，输入 $(0,3,0)$、两权重及近端参数均为一。独立应用不相交组公式为什么错？答案：两份公式都建议共享坐标取二，但真实目标在其余坐标取零后变为 $(t-3{)}^2/2+2|t|$，唯一最优为一。需要补上共享变量的一致性求解，不能仅把列表中的两个组都遍历一遍。

最后取 $A=(I_2{I}_2)$、$b=2u$、$\Vert u\Vert =1$、$\lambda =w_1=w_2=1$。全部 $(tu,(1-t)u)$、$0\le t\le 1$ 的残差为 $u$，目标和对偶值均为 $3/2$。不同活动组都可以零gap；这直接否定“精确优化会自动给唯一组名单”。

任务三：同一矩阵的三个输出，分别检查目标 ​

取 $Z=\left(\begin{array}{cc}3& 2\\ 2& 3\end{array}\right)$，目标是 $\Vert X-Z{\Vert }_F^2/2+2\Vert X{\Vert }_{\ast }$。要求求核范数近端、最佳秩一逼近、逐项软阈值，并把它们代入同一个核惩罚目标。

答案：令 $u=(1,1)/\sqrt{2},v=(1,-1)/\sqrt{2}$，$Z=5u{u}^{\mathsf{T}}+v{v}^{\mathsf{T}}$。

• 核范数近端：$X=3u{u}^{\mathsf{T}}$，秩一，目标 $17/2$
• 最佳秩一逼近：$X=5u{u}^{\mathsf{T}}$，秩一，目标 $21/2$
• 逐项阈值二：$X=I_2$，秩二，目标 $12$

第一份的残差 $R=2u{u}^{\mathsf{T}}+v{v}^{\mathsf{T}}$ 满足 $\Vert R{\Vert }_2=2$，且 $R/2=u{u}^{\mathsf{T}}+v{v}^{\mathsf{T}}/2\in \partial \Vert X{\Vert }_{\ast }$。$⟨Z,R⟩=11$、$\Vert R{\Vert }_F^2=5$，所以对偶值 $11-5/2=17/2$。后两份是不同任务的正确操作，并非本目标的正确解。

迁移题：把输入改成 $\mathrm{diag}(7,2,1)$、阈值仍为二，答案为 $\mathrm{diag}(5,0,0)$，目标 $29/2$。等于阈值的第二奇异方向清零；这正是要在代码中检查的闭边界。

任务四：三个观测的唯一性，需要两项额外证据 ​

精确观测模式 $\mathrm{\Omega }=\{(1,1),(1,2),(2,1)\}$，数据 $B_E=\left(\begin{array}{cc}4& 2\\ 2& 0\end{array}\right)$。认证 $M=\left(\begin{array}{cc}4& 2\\ 2& 1\end{array}\right)$ 不仅最优，而且唯一。

答案：$M=5u{u}^{\mathsf{T}}$，其中 $u=(2,1)/\sqrt{5}$，取 $v=(-1,2)/\sqrt{5}$。构造

$$Y=u{u}^{\mathsf{T}}-\frac{1}{4}v{v}^{\mathsf{T}}=\left(\begin{array}{cc}3/4& 1/2\\ 1/2& 0\end{array}\right).$$

它只支撑在观测位置，谱范数为一，且 $⟨B_E,Y⟩=5=\Vert M{\Vert }_{\ast }$，因此最优。进一步，补空间范数为 $1/4<1$；全部可行扰动为 $H=h{E}_{22}$，其切空间补投影是 $(4h/5)v{v}^{\mathsf{T}}$，只在 $h=0$ 时为零。于是观测在切空间上单射，唯一性定理给

$$\Vert M+h{E}_{22}{\Vert }_{\ast }-5\ge 3|h|/5.$$

把缺失格填成 $3/2$ 时，至少多付 $3/10$ 的核范数。若只交出 $P=D=5$ 而未检查严格余量和单射性，就只完成了最优性认证，尚未完成本题要求的唯一性报告。

任务五：带惩罚的补全必须保留未观测猜测 ​

改用 $B_P=\left(\begin{array}{cc}19/4& 5/2\\ 5/2& 0\end{array}\right)$、$\lambda =1$，目标变为 $F(X)=\Vert P_{\mathrm{\Omega }}X-B_P{\Vert }_F^2/2+\Vert X{\Vert }_{\ast }$。从零开始，取步长一，写出第一步与停止证书。

答案：每轮输入为 $Z_k=B_P+P_{{\mathrm{\Omega }}^c}{X}_k$，输出为 $X_{k+1}={\mathcal{S}}_1(Z_k)$。第一步精确式为

$$X_1=B_P-\frac{1}{\sqrt{761}}\left(\begin{array}{cc}19& 20\\ 20& -19\end{array}\right).$$

它约为 $\left(\begin{array}{cc}4.061250538& 1.775000566\\ 1.775000566& 0.688749462\end{array}\right)$，秩二。第二次的未观测输入应为 $0.688749462$，重新置零会错误地重复第一次计算。

每个候选取 $R=B_P-P_{\mathrm{\Omega }}X$，再用 $Y=R/max\{1,\Vert R{\Vert }_2\}$；它必须同时满足 $Y_{22}=0$ 和 $\Vert Y{\Vert }_2\le 1$。取终点 $M$ 时，$R$ 恰好为任务四的 $Y$，所以 $F(M)=D(Y)=177/32=5.53125$。

核验器同一次实跑得到：

轮次	原始目标	可行对偶值	gap	输出数值秩
1	5.659369201	5.432846254	0.226522947	2
2	5.540772908	5.513452188	0.027320720	1
5	5.531255843	5.531237506	$1.8338\cdot {10}^{-5}$	1
9	5.5312500003	5.5312499993	$1.0805\cdot {10}^{-9}$	1

数值秩使用 ${10}^{-10}$ 的绝对特征值阈值，仅适用于这里的对称二阶诊断。低秩不是停止标准，gap 才是目标误差接口；第2轮已秩一，却远未达到 ${10}^{-8}$ 门槛。

任务六：识别失败、凸松弛失败与证书未通过 ​

1. 只观测第一行 $(1,1)$，假定真矩阵秩一，能确定第二行吗？答案：不能。$\left(\begin{array}{cc}1& 1\\ t& t\end{array}\right)$ 对每个 $t$ 都符合观测和秩条件，数据不可识别。
2. 观测三格 $(1,2,2)$，秩一模型是否可识别，核范数能否恢复？答案：行列式要求缺失格为四，因此秩一答案唯一，核范数为五；但填一的矩阵核范数为四且是唯一核最优，秩为二。识别成立，凸松弛仍失败。
3. 三个观测都为一，严格切空间证书不存在，是否能断言不唯一？答案：不能。补格 $t$ 的核范数平方在 $t\le 1$ 时为 $4+(t-1{)}^2$，在 $t\ge 1$ 时为 $(t+1{)}^2$，唯一最低点为一；该例的补空间证书范数恰为一。充分条件不满足不等于结论相反。

推论与应用 ​

完整交付还要写出费用与失败状态 ​

组例每轮需要完整矩阵乘法、转置乘法和全部块范数，稠密一般成本为 $O(mp)$；认证下一点的相关性可以与下一轮共享，但不是不用计算。矩阵例若采用完整稠密 SVD，每轮核心为 $O(mnmin(m,n))$，直接的对偶谱范数认证另有同阶成本。小脚本利用二阶对称特征值公式，不代表一般矩阵也有同样常数费用。

两种迭代都固定初始化、步长、精度和预算。若预算用尽，报告实际gap和未达标状态；如果出现负gap，先检查对偶可行性与数值误差。部分SVD要有剩余谱的上界才能当作精确近端；组重叠需要专门的一致性处理。没有这些证据时，应准确交付尚未完成的部分。

原标量结构化优化终点保留坐标下降、ISTA/FISTA、安全筛除与随机/内层误差的原任务。本页独立补齐组选择和矩阵补全，未把原来的标量计算重复计作新增。加速随机近端需要独立的噪声与权重保证，不因为现在会做组或矩阵prox就自动完成。

参考资料 ​

• 组收缩的假设、证明与来源见组Lasso页理路组 Lasso 的块收缩与对偶证书Group Lasso proximal certificate · Block soft thresholding · 组软阈值对不相交变量组推导径向近端收缩，以整组残差相关性建立KKT和可行对偶间隙，并在耦合设计上认证停止。；核范数完整次微分与软阈值见核近端页理路核范数近端映射与奇异值软阈值Nuclear norm proximal map · Singular value soft thresholding · 核范数近端收缩推导核范数的完整次微分，以谱范数残差证明奇异值软阈值的唯一最优性，并区分核惩罚、截断SVD和逐项稀疏。；掩码更新、对偶资格和唯一性证明见补全页理路矩阵补全的优化间隙与唯一性证书Matrix completion certificate · Nuclear norm completion dual certificate · 核范数补全证书以掩码近端梯度求解带核惩罚的观测损失，用支持受限的谱范数对偶点认证误差，再以切空间严格证书证明精确补全唯一性。。
• Cai–Candès–Shen 的近端阈值定理与 Candès–Recht 的确定性唯一性引理回答不同层次的问题；所有特制有理数例子均在本终点给出原始输入和可复算答案。