HyperAI超神经

Nuclear normIt is the sum of the singular values of the matrix, which is used to constrain the low rank of the matrix. For sparse data, the matrix is low rank and contains a lot of redundant information, which can be used to recover data and extract features.

Nuclear norm definition

The nuclear norm of matrix X is defined as:

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

According to the above formula, the nuclear norm is equivalent to the sum of the matrix eigenvalues. Considering the eigenvalue decomposition of X ${X\text{ }=\text{ }U \Sigma V\mathop{{}}\nolimits^{{T}}}$ , we can draw the following conclusions:

${\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}}$

Proof of Convexity

According to the known information, the matrix induced norm is convex, that is:

Let ${f\mathop{{}}\nolimits_{{x}}{ \left( {A} \right) }\text{ }=\text{ }{ \left\Vert {Ax} \right\Vert }\mathop{{}}\nolimits_{{p}}\text{ }{ \left( {p \ge 1} \right) }}$ , Then ${f\mathop{{}}\nolimits_{{x}}}$ is convex, so ${{ \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) }}$ is convex, and ${{ \left\Vert {A} \right\Vert }\mathop{{}}\nolimits_{{2}}}$ Since ${{ \left\Vert {A} \right\Vert }\mathop{{}}\nolimits_{{*}}}$ and ${{ \left\Vert {A} \right\Vert }\mathop{{}}\nolimits_{{2}}}$ are dual norms, ${{ \left\Vert {A} \right\Vert }\mathop{{}}\nolimits_{{*}}}$ convex ( ${{ \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) }}$ ).

Gradient solution

Based on the above SVD assumptions, we can conclude that:

${\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}}}$

Therefore, we need to solve ${ \partial \Sigma }$ . Consider ${X\text{ }=\text{ }U \Sigma V\mathop{{}}\nolimits^{{T}}}$ , so we have:

${\begin{array}{*{20}{l}} {}&{ \partial }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 }0} \right) }} \end{array}}$

so:

${\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 \right) }}}{{ \partial X}} \text{ }=\text{ }{ \left( {VU\mathop{{}}\nolimits^{{T}}} \right) }\mathop{{}}\nolimits^{{T}}\text{ }=\text{ }UV\mathop{{}}\nolimits^{{T}}}$

Nuclear Norm

Nuclear norm definition

Proof of Convexity

Gradient solution