核范数 Nuclear Norm

核范数是矩阵奇异值的和，用于约束矩阵的低秩，对于稀疏性质的数据而言，其矩阵是低秩且会包含大量冗余信息，这些信息可被用于恢复数据和提取特征。

核范数定义

矩阵 X 的核范数定义式为：

${{ \left\Vert {X} \right\Vert }\mathop{{}}\nolimits_{{*}}\text{ }=\text{ }tr{ \left( {\sqrt{{X\mathop{{}}\nolimits^{{T}}X}}} \right) }}$

根据上式可以得出，核范数等价于矩阵特征值的和，考虑 X 的特征值分解 ${X\text{ }=\text{ }U \Sigma V\mathop{{}}\nolimits^{{T}}}$ ，可以得出以下结论：

${\begin{array}{*{20}{l}} {tr{ \left( {\sqrt{{X\mathop{{}}\nolimits^{{T}}X}}} \right) }}&{=\text{ }tr{ \left( {\sqrt{{{ \left( {U \Sigma V\mathop{{}}\nolimits^{{T}}} \right) }\mathop{{}}\nolimits^{{T}}U \Sigma V\mathop{{}}\nolimits^{{T}}}}} \right) }}\\ {}&{=\text{ }tr{ \left( {\sqrt{{V \Sigma \mathop{{}}\nolimits^{{T}}U\mathop{{}}\nolimits^{{T}}U \Sigma V\mathop{{}}\nolimits^{{T}}}}} \right) }}\\ {}&{=\text{ }tr{ \left( {\sqrt{{V \Sigma \mathop{{}}\nolimits^{{2}}V\mathop{{}}\nolimits^{{T}}}}} \right) }\text{ }{ \left( { \Sigma \mathop{{}}\nolimits^{{T}}= \Sigma } \right) }}\\ {}&{=\text{ }tr{ \left( {\sqrt{{V\mathop{{}}\nolimits^{{T}}V \Sigma \mathop{{}}\nolimits^{{2}}}}} \right) }}\\ {}&{=\text{ }tr{ \left( { \Sigma } \right) }} \end{array}}$

凸性的证明

根据可知信息，矩阵诱导范数是凸的，即：

令 ${f\mathop{{}}\nolimits_{{x}}{ \left( {A} \right) }\text{ }=\text{ }{ \left\Vert {Ax} \right\Vert }\mathop{{}}\nolimits_{{p}}\text{ }{ \left( {p \ge 1} \right) }}$ , 则 ${f\mathop{{}}\nolimits_{{x}}}$ 凸，故 ${{ \left\Vert {A} \right\Vert }\mathop{{}}\nolimits_{{p}}\text{ }=\text{ }\mathop{{sup}}\limits_{{{ \left\Vert {x} \right\Vert }\mathop{{}}\nolimits_{{p}}=1}}\text{ }f\mathop{{}}\nolimits_{{x}}{ \left( {A} \right) }}$ 凸，同时 ${{ \left\Vert {A} \right\Vert }\mathop{{}}\nolimits_{{2}}}$ 由于 ${{ \left\Vert {A} \right\Vert }\mathop{{}}\nolimits_{{*}}}$ 和 ${{ \left\Vert {A} \right\Vert }\mathop{{}}\nolimits_{{2}}}$ 是对偶范数，故 ${{ \left\Vert {A} \right\Vert }\mathop{{}}\nolimits_{{*}}}$ 凸（ ${{ \left\Vert {A} \right\Vert }\mathop{{}}\nolimits_{{*}}\text{ }=\text{ }\mathop{{sup}}\limits_{{{ \left\Vert {X} \right\Vert }\mathop{{}}\nolimits_{{2}}=1}}\text{ }tr{ \left( {{A\mathop{{}}\nolimits^{{T}}X}} \right) }}$ ）。

梯度的求解

基于上述 S.V.D 假设，可以得出结论：

${\frac{{ \partial { \left\Vert {X} \right\Vert }\mathop{{}}\nolimits_{{*}}}}{{ \partial X}}\text{ }=\text{ }\frac{{ \partial tr{ \left( { \Sigma } \right) }}}{{ \partial X}}\text{ }=\text{ }\frac{{tr{ \left( { \partial \Sigma } \right) }}}{{ \partial X}}}$

因此需要解出 ${ \partial \Sigma }$ ，考虑 ${X\text{ }=\text{ }U \Sigma V\mathop{{}}\nolimits^{{T}}}$ ，故有：

${\begin{array}{*{20}{l}} {}&{ \partial X}&{=\text{ }{ \left( { \partial U} \right) } \Sigma V\mathop{{}}\nolimits^{{T}}\text{ }+\text{ }U{ \left( { \partial \Sigma } \right) }V\mathop{{}}\nolimits^{{T}}\text{ }+\text{ }U \Sigma { \left( { \partial V\mathop{{}}\nolimits^{{T}}} \right) }}\\ { \Rightarrow }&{ \partial \Sigma }&{=\text{ }U\mathop{{}}\nolimits^{{T}}{ \left( { \partial X} \right) }V\text{ }-\text{ }U\mathop{{}}\nolimits^{{T}}{ \left( { \partial U} \right) } \Sigma \text{ }-\text{ } \Sigma { \left( { \partial V\mathop{{}}\nolimits^{{T}}} \right) }V}\\ {}&{}&{=U\mathop{{}}\nolimits^{{T}}{ \left( { \partial X} \right) }V\text{ }\text{ }\text{ }\text{ }{ \left( {-U\mathop{{}}\nolimits^{{T}}{ \left( { \partial U} \right) } \Sigma – \Sigma { \left( { \partial V\mathop{{}}\nolimits^{{T}}} \right) }V\text{ }=\text{ }0} \right) }} \end{array}}$

所以：

${\frac{{ \partial { \left\Vert {X} \right\Vert }\mathop{{}}\nolimits_{{*}}}}{{ \partial X}}\text{ }=\text{ }\frac{{tr{ \left( { \partial \Sigma } \right) }}}{{ \partial X}}\text{ }=\text{ }\frac{{tr{ \left( {U\mathop{{}}\nolimits^{{T}}{ \left( { \partial X} \right) }V} \right) }}}{{ \partial X}}\text{ }=\text{ }\frac{{tr{ \left( {VU\mathop{{}}\nolimits^{{T}}{ \left( { \partial X} \right) }} \right) }}}{{ \partial X}} \text{ }=\text{ }{ \left( {VU\mathop{{}}\nolimits^{{T}}} \right) }\mathop{{}}\nolimits^{{T}}\text{ }=\text{ }UV\mathop{{}}\nolimits^{{T}}}$