矩陣的核範數的導數是什麼？

01-07

矩陣的核範數是奇異值的和，那麼核範數的導數是什麼？如下我這樣證明對嗎？
由於 $U Sigma V^T$ 不一定是方陣，是不是應該用特徵值分解而不是奇異值分解？

仔細看了現有的答案， @又紅又正 @朴正歡和題主都給出了一些形式推導， @Sleor Chen 給出了簡要思路， @蕊蕊給出了準確答案，但是沒有推導。我這裡基於矩陣核範數的變分表示（Variational representation），對這些答案的不足和聯繫做一個澄清，並給出一個比較易懂的解釋。

首先需要澄清的是次微分subdifferential的概念問題。先說次梯度subgradient, 向量 $m{g}$ 稱為函數 $f(m{x})$ 在 $m{x}$ 處的次梯度，如果滿足次梯度不等式 $f(m{y}) ge f(m{x}) + m{g}^T(m{y-x}) :: forall m{y}$ 。所有滿足次梯度不等式的向量 $m{g}$ 組成的集合稱之為次微分 $partial f(m{x}) =left{ m{g}:f(m{y}) ge f(m{x}) + m{g}^T(m{y-x}) :: forall m{y} ight}$ 。注意兩點。第一，這裡次梯度和次微分的定義是對所有的函數都適用的，而不僅僅是凸函數。當然，對於非凸函數，在某些點 $m{x}$ 處，次梯度不存在，次微分為空集。第二，由於次梯度不等式關於向量 $m{g}$ 是線性的，所以次微分是一個凸集。題主的問題是要計算subdifferential，也就是所有的subgradient，而前述基於形式推導的方法都只能給出部分的subgradient。

要給出subdifferential的完整表示，藉助核範數的變分表示更方便。首先給出一個非常簡單的次微分引理。考慮max-type表示的凸函數 $f(m{x})=max_{m{s}in S} m{s}^Tm{x}$ (其實就是支撐函數)，這裡集合 $S$ 可以是任意有界集合，離散的，連續的，非凸的都行。將 $f(m{x})$ 看作是關於變數 $m{s}$ 的最大化問題的最優值，對應的解集記作 $S(m{x})$ ，那麼在一定條件下，函數 $f(m{x})$ 在 $m{x}$ 處的subdifferential是 $S(m{x})$ 的凸包絡（convex hull) 。對於矩陣核範數 $left lVert m{W} ight Vert_*$ ，很顯然有變分表示 $left lVert m{W} ight Vert_*=max_{m{U}^Tm{U}=m{I},m{V}^Tm{V}=m{I}} tr(m{U}^Tm{WV})$ 。所以計算矩陣核範數的subdifferential，就是分析這個最大化問題的解集及其凸包絡，這其實就是要表示所有SVD！其答案就是 @蕊蕊給出來的表示。由於變分表示里關於 $m{W}$ 是線性的，這就證明了核範數是凸函數。再用剛才的次微分引理可以得到，只有在SVD分解唯一( $m{UV}^T$ 唯一)的時候，矩陣核範數是differential，此時唯一的subgradient就是gradient。

更進一步來說，這個問題其實涉及到核範數的變分表示問題的隱藏凸性。因為對於大多數非光滑的凸函數，完整的表示subdifferential幾乎是不可能的。核範數的變分表示問題明明是非凸問題，它的解集是非凸的，而解集的凸包絡居然是可以參數化表示的！這背後有一個重要的數學結論Fan』s theorem [1](懶的敲了，直接粘圖吧)

套用這個結論(k=n)，可以得到對稱矩陣的核範數的變分表示問題的隱藏凸問題及其最優條件（其實就是寫變分表示問題的KKT條件)，這就給出了subdifferential的表示。而更一般矩陣的核範數再用對稱矩陣等價表示一遍就可以了，詳情見[2]。

[1] Overton M L, Womersley R S. On the Sum of the Largest Eigenvalues of a Symmetric Matrix[J]. Siam Journal on Matrix Analysis Applications, 1992, 13(1):41-45.

[2] Overton M L, Womersley R S. Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices[J]. Mathematical Programming, 1993, 62(1-3):321-357.

更新一下，讀了 @子元提供的鏈接，看明白了最關鍵的一步是把 $W=USigma V^T$ 帶入

$d[mathrm{tr}(Sigma)]=mathrm{tr}[dU(W)^TWV(W)+U(W)^TdWV(W)+U(W)^TWdV(W)]$

得到

$d[mathrm{tr}(Sigma)]=mathrm{tr}[dU(W)^TU(W)Sigma+U(W)^TdWV(W)+Sigma V(W)^TdV(W)]$

然後注意到 $d(U^T U)=dU^TU+U^TdU=0$

令 $A=dU^T U$ , 則 $A+A^T=0$

因此 $mathrm{tr}(ASigma)=frac{1}{2} mathrm{tr}(ASigma+Sigma^TA^T)=frac{1}{2} mathrm{tr}[(A+A^T)Sigma]=0$

同理 $mathrm{tr}[Sigma V(W)^TdV(W)]=0$

因此最後的結論是對的。

----------------------------------------------------------------------------------------------------------------------------

不對。因為svd中的 $U$ 和 $V$ 都是都是 $W$ 的函數，因此事實上 $Sigma=U(W)^TWV(W)$ , 根據chain rule, $d[mathrm{tr}(Sigma)]=mathrm{tr}[dU(W)^TWV(W)+U(W)^TdWV(W)+U(W)^TWdV(W)]$

然後可以進一步寫成

$d[mathrm{tr}(Sigma)]=mathrm{tr}[U(W)^TdWV(W)+Wd{V(W)U(W)^T}]$

如果 $W$ 是symmetric matrix, 那麼有 $V(W)U(W)^T=I$ ,因此 $d{V(W)U(W)^T}=0$

這種情況下你的證明是對的。

一般情況下我還沒有想到如何證明，不過我想這個問題肯定已經被研究過了，你可以查些相關的paper。

這個證明當然回答了這個問題的一部分。首先我們要考慮矩陣W的秩以及矩陣是不是方陣。

1）如果W是滿秩的方陣。那麼由W左右奇異向量組成的矩陣U,V擴展成了 $mathbb{R}^{d imes d}$ ，這時候你的結論是成立的。

2）如果不是（方陣，並且不是行或者列）滿秩的，很顯然null space是不為0的，這時候我找一個 $W_ot$ ，它滿足左右奇異向量分別在U,V的null space, 根據nuclear norm的凸性，我們很容易驗證 $UV+W_ot$ 是一個次梯度方向.

我想了想可以從另一個方面來理解這個問題。你考慮一個objective $f(x)$ 是continuous nonsmooth的凸優化問題，自變數 $x$ 在n維歐氏空間的一個subspace里，spanned by orthonormal basis $R(f)={v_1,ldots,v_d}$ , $0<d<n$ . 很顯然次梯度是由兩部分組成的，一部分在 $R(f)$ ,另一部分在 $R_ot(f)$ . 這剛好能和2）對應起來。