核范数近端映射与奇异值软阈值

形式陈述

在实矩阵空间 $\mathbb R^{m\times n}$ 、 $m,n\ge1$ 上使用 Frobenius 内积 $\langle X,Y\rangle=\operatorname{tr}(X^{\mathsf T}Y)$ 。若 $X$ 的奇异值为 $\sigma_1\ge\cdots\ge\sigma_q\ge0$ 、 $q=\min(m,n)$ ，其核范数为

\|X\|_* =\sum_{i=1}^q\sigma_i(X).

这里复用SVD的奇异值与谱范数 $\|X\|_2=\sigma_1(X)$ 。核范数已在分解范数下界中作为谱范数的对偶出现；本页的新问题是如何用它精确求解非光滑矩阵子问题。

给定 $Z\in\mathbb R^{m\times n}$ 和 $\tau>0$ ，若 $Z=U\operatorname{diag}(\sigma_i)V^{\mathsf T}$ 是经济型 SVD，则

\mathcal S_\tau(Z)=U\operatorname{diag}((\sigma_i-\tau)_+)V^{\mathsf T} =\underset{X}{\operatorname{argmin}}\left\{ \frac12\|X-Z\|_F^2+\tau\|X\|_*\right\}. \tag{1}

它是核范数的近端映射，称为奇异值软阈值。最优矩阵唯一；即使 SVD 的基不唯一，输出也不依赖选择。等于阈值的奇异值变为零。 $\tau=0$ 时直接返回 $Z$ ，无需使用下面含 $1/\tau$ 的证书。

验证 (1) 的关键接口是完整次微分。对秩为 $r$ 的矩阵 $X=U_r\Sigma_rV_r^{\mathsf T}$ ，其中只保留正奇异值，有

\partial\|X\|_*= \{U_rV_r^{\mathsf T}+W: U_r^{\mathsf T}W=0,\ WV_r=0,\ \|W\|_2\le1\}. \tag{2}

$X=0$ 时， $U_r,V_r$ 为空，(2) 即整个谱范数闭单位球。非零矩阵的 $U_rV_r^{\mathsf T}$ 固定已使用的左右奇异方向； $W$ 在两侧正交补中补齐其他方向。不能只写一个 $U_rV_r^{\mathsf T}$ ，否则会漏掉低秩解所需的次梯度。

直觉

组收缩缩短已给定分组的长度；核范数收缩缩短由输入矩阵自己决定的奇异方向。两者都可能把结构单位压成零，但“组”和“奇异方向”是不同对象。奇异值的数目决定输出秩，矩阵条目是否为零却由左右基共同决定。

同一矩阵在保留的正交奇异方向上分别执行核惩罚、秩一截断和逐项阈值；核惩罚把奇异值5和1变为3和0，截断保留5，逐项阈值得到秩二单位矩阵 — 同一输入，三个不同优化任务

图中矩阵与数值在下一节完整给出。它比较三份真正不同的优化输出：软阈值会缩短留下的奇异值；截断 SVD 保持留下的奇异值不变；逐项软阈值依赖当前条目坐标，通常不保持原奇异方向。

例子与边界

非对角矩阵的精确去噪证书

取

Z=\begin{pmatrix}3&2\\2&3\end{pmatrix},\quad u=\frac1{\sqrt2}(1,1)^{\mathsf T},\quad v=\frac1{\sqrt2}(1,-1)^{\mathsf T},\quad\tau=2.

这里 $Z=5uu^{\mathsf T}+vv^{\mathsf T}$ ，两个特征值为正，故也是奇异值。式 (1) 给

X^*=3uu^{\mathsf T}=\frac32\begin{pmatrix}1&1\\1&1\end{pmatrix}.

原矩阵秩二，输出秩一，却没有零条目。残差与次梯度证书为

R=Z-X^*=2uu^{\mathsf T}+vv^{\mathsf T} =\begin{pmatrix}3/2&1/2\\1/2&3/2\end{pmatrix}, \qquad G=R/2=uu^{\mathsf T}+\frac12vv^{\mathsf T}.

补空间项 $W=vv^{\mathsf T}/2$ 满足 $u^{\mathsf T}W=Wu=0$ 、 $\|W\|_2=1/2\le1$ ，所以 $G\in\partial\|X^*\|_*$ ，并且 $X^*-Z+2G=0$ 。这已经是完整最优性证书。

对偶也能直接复算。对 $\|Y\|_2\le\tau$ 定义

D_Z(Y)=\langle Z,Y\rangle-\frac12\|Y\|_F^2. \tag{3}

取 $Y=R$ ，谱范数为二，合法； $\langle Z,R\rangle=5\cdot2+1\cdot1=11$ ， $\|R\|_F^2=5$ 。因此

P(X^*)=\frac52+2\cdot3=\frac{17}{2} =D_Z(R).

原、对偶等值认证同一个最优值，并没有通过观察秩来猜测答案。

截断和逐项阈值各自解了什么

同一输入的最佳秩一 Frobenius 逼近由旧 SVD 定理给出 $X_{\mathrm{rank}}=5uu^{\mathsf T}$ 。其平方残差为一，是秩约束任务的正确答案；但放入本页核惩罚目标，得到 $1/2+2\cdot5=21/2>17/2$ 。它没有为留下的奇异方向支付收缩代价。

若把 $Z$ 的每个条目都软阈值二，得到 $X_{\mathrm{entry}}=I_2$ 。其秩仍是二，本页目标为 $\|I-Z\|_F^2/2+2\|I\|_*=8+4=12$ ，也不是答案。逐项阈值正确求解的是带惩罚 $2\sum_{ij}|X_{ij}|$ 的问题；核范数不是逐项绝对值之和，也不是最大列和。

若改成 $Z=\operatorname{diag}(2,2)$ 、 $\tau=2$ ，答案为零且唯一。重复奇异值允许旋转 SVD 的基，不能据此说近端解多值。反过来，最佳秩一逼近此时有多种方向选择；它属于非凸秩约束问题，不能把那项非唯一性搬到 (1)。

推论与应用

从对偶球完整推导次微分

复用核范数—谱范数对偶关系

|\langle G,H\rangle|\le\|G\|_2\|H\|_*,\qquad \|H\|_* =\max_{\|G\|_2\le1}\langle G,H\rangle. \tag{4}

为明确接口，若 $H=\sum_i\sigma_i a_i b_i^{\mathsf T}$ ，逐项 $|a_i^{\mathsf T}Gb_i|\le\|G\|_2$ 得到不等式，取 $G=\sum_i a_i b_i^{\mathsf T}$ 达到上界。这也证明核范数凸：它是一族线性函数的上确界。该对偶性是旧覆盖，不将它当作新定理另建一页。

由次梯度不等式，对任何范数 $N$ ，定义其对偶范数 $N^\circ(G)=\sup_{N(H)\le1}\langle G,H\rangle$ ，与 Fenchel 共轭的指标函数区分。于是 $G\in\partial N(X)$ 当且仅当 $N^\circ(G)\le1$ 且 $\langle G,X\rangle=N(X)$ 。必要性可分别代入 $H=0,2X$ 得到等号，再由一般 $H$ 得 $\langle G,H\rangle\le N(H)$ ；反向把这两条相减即可。于是这里要求 $\|G\|_2\le1$ 和 $\langle G,X\rangle=\|X\|_*$ 。

写 $X=\sum_{i=1}^r\sigma_i u_i v_i^{\mathsf T}$ 。每个 $u_i^{\mathsf T}Gv_i\le1$ ，且全部 $\sigma_i>0$ ；加权和取等迫使每一项都等于一。由 $\|Gv_i\|\le1$ 和 Cauchy–Schwarz 等号，得 $Gv_i=u_i$ 。同理 $G^{\mathsf T}u_i=v_i$ 。因此 $W=G-U_rV_r^{\mathsf T}$ 必须满足 $WV_r=0$ 和 $U_r^{\mathsf T}W=0$ ，且在两侧正交补之间的限制仍是压缩映射， $\|W\|_2\le1$ 。

反向若 $W$ 满足 (2)，在输入、输出的相应正交基中， $G=U_rV_r^{\mathsf T}+W$ 是一个单位块和一个范数至多一的补块。因此 $\|G\|_2\le1$ ，且 $\langle G,X\rangle=\sum_i\sigma_i$ 。由前述范数次梯度刻画，得到完整的 (2)，两个方向都已证明。

软阈值为什么精确求解矩阵近端

把 $Z$ 的正奇异项按 $\sigma_i>\tau$ 与 $0<\sigma_i\le\tau$ 分开，记前者为活动集 $I$ 。定义 $X=\sum_{i\in I}(\sigma_i-\tau)u_i v_i^{\mathsf T}$ 。则

\frac{Z-X}{\tau} =\sum_{i\in I}u_i v_i^{\mathsf T} +\sum_{i\notin I}\frac{\sigma_i}{\tau}u_i v_i^{\mathsf T}.

第二项在活动左右奇异空间的正交补中，谱范数至多一；若没有剩余项，取零。式 (2) 因此证明 $(Z-X)/\tau\in\partial\|X\|_*$ ，正是近端的最优性条件。平方项强凸，故此候选是唯一解。整个推导不需要把旧 Eckart–Young 的秩约束偷偷换成核惩罚，也不需要先假设最优点与输入共享奇异向量；我们构造候选后用全空间次梯度认证它。

可计算间隙与数值代价

由 (4) 与共轭定义， $\tau\|\cdot\|_*$ 的共轭是谱范数半径 $\tau$ 球的指标函数。消去平方损失的残差得到 (3)，并有

P(X)-D_Z(Y) =\frac12\|Z-X-Y\|_F^2+\tau\|X\|_*-\langle X,Y\rangle\ge0 \tag{5}

对任意合法 $Y$ 成立。给定候选 $X$ ，可取 $R=Z-X$ 、 $Y=R/\max\{1,\|R\|_2/\tau\}$ 。若有更便宜的经证实上界 $B\ge\|R\|_2$ ，也可用 $B$ 缩放，证书会更保守。幂迭代得到的通常是谱范数下界，不能未经误差控制就填入这个上界槽位。

一次完整稠密 SVD 的标准实数算术费用为 $O(mn\min(m,n))$ ，显式矩阵存储为 $O(mn)$ ，阈值标量操作为 $O(\min(m,n))$ 。输出秩 $r_\tau$ 的左右因子可用 $O((m+n)r_\tau)$ 存储，但这不自动免除形成输入或求分解的费用。若只计算部分 SVD，只有在余下奇异值都被证明不超过 $\tau$ 时才等于精确 prox；否则它是近似子问题，须另给误差预算。不能以一个目标秩硬截断冒充核范数阈值。

全观测去噪只需一次 (1)。当损失只看部分条目时，零填补后的一次 SVD 解的是另一份完整平方距离；应使用矩阵补全的掩码更新与证书。那里的精确观测约束又有自己的对偶条件。文献中 “SVT algorithm” 还可指在双变量中累积观测残差的特定迭代，不应与本页的单次近端映射同名混用。

两道短自测

$Z=\operatorname{diag}(7,2,1)$ 、 $\tau=2$ 。求输出、残差谱范数与目标值。答案： $X=\operatorname{diag}(5,0,0)$ ， $R=\operatorname{diag}(2,2,1)$ ， $\|R\|_2=2$ ， $P=9/2+10=29/2$ 。第二个奇异值恰在阈值上，仍被清零。
对 $Z=\operatorname{diag}(3,1)$ 、 $\tau=2$ ，只保留第一个奇异方向并保留原幅度三，是合法近端解吗？答案：不是；应输出 $\operatorname{diag}(1,0)$ 。前者残差在活动方向为零，不满足该方向需要的阈值二次梯度平衡。

参考资料

Jian-Feng Cai, Emmanuel J. Candès and Zuowei Shen, A Singular Value Thresholding Algorithm for Matrix Completion，作者稿，§2.1、Theorem 2.1、式(2.6)：核范数近端与次微分；§2.2 的累积双变量算法与单次近端映射有别。本页把式(2.6)的两个方向另行展开证明。
Neal Parikh and Stephen Boyd, Proximal Algorithms，§6.7.1–6.7.3（印刷页191–193），逐项函数、正交不变函数及式(6.13)的奇异值阈值。
Stephen Boyd and Lieven Vandenberghe, Convex Optimization，2004，§3.3.1、Example 3.26（印刷页93）：范数共轭为对偶单位球的指标函数；上文明确区分对偶范数与共轭函数。

形式陈述 ​

非对角矩阵的精确去噪证书 ​

截断和逐项阈值各自解了什么 ​

从对偶球完整推导次微分 ​

软阈值为什么精确求解矩阵近端 ​

可计算间隙与数值代价 ​

两道短自测 ​

反向链接