核范数求导(derivative of the nuclear norm)
我在网上找到了关于核范数求导的两种方式，一种是论文里常用的Singular Value Thresholding（SVT）方法，另外一种是网上流传的通过SVD的方式直接求导的方式。
1. Singular Value Thresholding
这种方法最早是针对矩阵补全的问题提出的，在论文《A Singular Value Thresholding Algorithm for Matrix Completion》中，作者提出了关于以下形式问题的求解方法
即对于（2.3）公式中的优化问题而言，其最优解X等于
D
τ
(
Y
)
D_{\tau}(Y)
Dτ(Y)，而
D
τ
(
Y
)
D_{\tau}(Y)
Dτ(Y)的定义如下：
也就是说对于公式（2.3），为了获得X的最优解，我们需要将Y进行SVD（skinny SVD）分解，U和V保持不变，但是对于所有的特征值要减去
τ
\tau
τ（注意：这个
τ
\tau
τ是公式中核范数前面的系数），并进行max(0,t)操作，那么对于
σ
i
<
τ
\sigma_i<\tau
σi<τ的那些特征值就会被置0，这是SVT的主要思想，而论文中通常会先将带有核范数的目标函数转化成如（2.3）形式的问题，再利用上述SVT的解法求得最优解。
举个具体的实例：
有目标函数一：
min
Z
f
(
Z
)
+
λ
∥
Z
∥
∗
\min_{Z}f(Z)+\lambda\|Z\|_*
Zminf(Z)+λ∥Z∥∗
首先引入中间变量
X
X
X，得到如下目标函数二：
min
Z
,
X
f
(
Z
)
+
λ
∥
X
∥
∗
s
.
t
.
Z
=
X
\min_{Z,X}f(Z)+\lambda\|X\|_*\\ s.t. Z=X
Z,Xminf(Z)+λ∥X∥∗s.t.Z=X
利用增广拉格朗日得到目标函数三：
min
Z
,
X
f
(
Z
)
+
λ
∥
X
∥
∗
+
t
r
(
A
T
(
Z
−
X
)
)
+
μ
2
∥
Z
−
X
∥
F
2
\min_{Z,X}f(Z)+\lambda\|X\|_*+tr(A^T(Z-X))+\frac{\mu}{2}\|Z-X\|_F^2
Z,Xminf(Z)+λ∥X∥∗+tr(AT(Z−X))+2μ∥Z−X∥F2
只关注与X有关的项，我们可以得到如下优化问题一：
arg
min
X
λ
∥
X
∥
∗
+
t
r
(
A
T
(
Z
−
X
)
)
+
μ
2
∥
Z
−
X
∥
F
2
\arg\min_X \lambda\|X\|_*+tr(A^T(Z-X))+\frac{\mu}{2}\|Z-X\|_F^2\\
argXminλ∥X∥∗+tr(AT(Z−X))+2μ∥Z−X∥F2
经过计算，得到优化问题二：
arg
min
X
λ
μ
∥
X
∥
∗
+
1
2
∥
X
−
(
Z
+
1
μ
A
)
∥
F
2
\arg\min_X \frac{\lambda}{\mu}\|X\|_*+\frac{1}{2}\|X-(Z+\frac{1}{\mu}A)\|_F^2\\
argXminμλ∥X∥∗+21∥X−(Z+μ1A)∥F2
此时不难发现优化问题二就和公式(2.3)有着相似的结构了(
λ
μ
\frac{\lambda}{\mu}
μλ对应
τ
\tau
τ，
(
Z
+
1
μ
A
)
(Z+\frac{1}{\mu}A)
(Z+μ1A)对应
Y
Y
Y），直接利用SVT求解即可
2. 直接求导
考虑到矩阵核范数的定义如下：
∥
X
∥
∗
=
t
r
(
X
T
X
)
\|X\|_*=tr(\sqrt{X^TX})
∥X∥∗=tr(XTX)
结合特征值分解有
X
=
U
Σ
V
T
X=U\Sigma V^T
X=UΣVT，可以得到以下结论：
t
r
(
X
T
X
)
=
t
r
(
Σ
)
tr(\sqrt{X^TX})=tr(\Sigma)
tr(XTX)=tr(Σ)
对于X而言：
∂
X
=
(
∂
U
)
Σ
V
T
+
U
(
∂
Σ
)
V
T
+
U
Σ
(
∂
V
T
)
\partial X=(\partial U)\Sigma V^T+U(\partial \Sigma) V^T+ U\Sigma (\partial V^T)
∂X=(∂U)ΣVT+U(∂Σ)VT+UΣ(∂VT)
将上述公式右侧的第二项挪至等号左边并左乘U^T，右乘V，得到
∂
Σ
=
U
T
(
∂
X
)
V
−
U
T
(
∂
U
)
Σ
−
Σ
(
∂
V
T
)
V
\partial \Sigma=U^T(\partial X)V-U^T(\partial U)\Sigma-\Sigma(\partial V^T)V
∂Σ=UT(∂X)V−UT(∂U)Σ−Σ(∂VT)V
由于后面两项的值为0，所以
∂
Σ
=
U
T
(
∂
X
)
V
\partial \Sigma=U^T(\partial X)V
∂Σ=UT(∂X)V
对X的核范数直接求导，得到
∂
∥
X
∥
∗
∂
X
=
t
r
(
Σ
)
∂
X
=
t
r
(
U
T
(
∂
X
)
V
∂
X
=
V
U
T
(
∂
X
)
∂
X
=
(
V
U
T
)
T
=
U
V
T
\frac{\partial \|X\|_*}{\partial X}=\frac{tr(\Sigma)}{\partial X}=\frac{tr(U^T(\partial X)V}{\partial X}=\frac{VU^T(\partial X)}{\partial X}=(VU^T)^T=UV^T
∂X∂∥X∥∗=∂Xtr(Σ)=∂Xtr(UT(∂X)V=∂XVUT(∂X)=(VUT)T=UVT
在知乎的一个答案中看到了关于第二种方法正确性的讨论，这种方法并不适用于所有的W，详情参考矩阵的核范数的导数是什么？
参考文献：
- Cai J F, Candès E J, Shen Z. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on optimization, 2010, 20(4): 1956-1982.
- Boyd S, Parikh N, Chu E, et al. Distributed Optimization and Statistics via Alternating Direction Method of Multipliers[J]. 2013.
- https://math.stackexchange.com/questions/701062/derivative-of-the-nuclear-norm
- https://hyper.ai/wiki/2687