為什麼核範數能凸近似矩陣的秩？為什麼核範數是凸的？

01-07

第一問：nuclear norm 是奇異值的和，rank是非零奇異值的個數。nuclear norm能近似rank就跟 $ell_1$ norm能近似 $ell_0$ norm一樣。

第二問：

1) 首先矩陣誘導範數是凸的：令 $f_x(A)=|Ax|_p (pge 1)$ ，則 $f_x$ 凸，故 $|A|_p=sup_{x,|x|_p=1}f_x(A)$ 凸。特別地， $|A|_2$ 凸（即奇異值的最大值）。

2) 因為 $|A|_*$ 是 $|A|_2$ 的對偶範數（一個是和，一個是最大值，就和 $ell_1$ norm跟 $ell_infty$ norm之間的關係一樣），所以 $|A|_*$ 凸。實際上， $|A|_*=sup_{X,|X|_2=1} mathrm{tr}A^mathrm{T}X$ 。故跟1) 同理， $|A|_*$ 凸。

簡單說一下，如果想搞清楚細節，參考Rockafellar的Convex Analysis

結論： $lVert cdot Vert_*$ 是在一定意義下，rank的最佳凸估計/凸鬆弛（convex relaxation）。

下面第一部分解釋是是什麼意義下的最佳，第二部分解釋為什麼nuclear norm是rank的convex relaxation。

========第一部分========

（將要涉及到的一些概念：extended-valued function, epigraph, lower semicontinuous, convex conjugate）

Let $F: R^n ightarrow (-infty, infty]$ .

The convex conjugate $F^*$ is lower semicontinuous.
The biconjugate $F^{**}$ is the largest lower semicontinuous convex function satisfying $F^{**}(x) leq F(x)$ for all $x in R^n$ .

而lower semicontinuous和 $mathbf{epi}(F)$ close等價。

所以，biconjugate就相當於對原函數的epigraph $mathbf{epi}(F)$ 做convex hull（滿足凸性），然後再做closure（閉集）所得到的函數。一般來說，一個函數的biconjugate稱為這個函數的convex relaxation。

========第二部分========

比如我們RPCA里，我們對sparse部分的penalty應該是 $lVert cdot Vert_0$ ，在 $lVert x Vert_{infty} leq 1$ 的條件下（重要）， $lVert x Vert_0$ 的biconjugate就是 $lVert x Vert_1$ 。

proof: denote $F(x) = lVert x Vert_0$ ，

$F^*(mu) = sup_x langle mu, x angle - lVert x Vert_0 = sum_i ( lvert mu_i vert - 1)_+$ ，

$F^{**}(x) = sup_{mu} langle x, mu angle - sum_i ( lvert mu_i vert - 1)_+ = lVert x Vert_1$

其實矩陣的nuclear norm是rank的convex relaxation可以看作是上面的推論。說一下idea，一個m*n的矩陣 $M$ ，有奇異值分解（SVD） $M = U Sigma V^T$ 。把 $Sigma$ 對角線元素（共 $min(m, n)$ 個）當作一個向量 $x$ 。 $mathrm{rank}(M) = lVert x Vert_0$ ， $lVert M Vert_* = lVert x Vert_1$ 。因為奇異值本身都大於等於0，所以nuclear norm等於奇異值直接求和。當然，這裡 $lVert M Vert_*$ 是 $mathrm{rank}(M)$ 的convex relaxation還需要一個前提條件，就是 $M$ 所有的奇異值都小於等於1（在 $lVert x Vert_{infty} leq 1$ 的條件下 $lVert x Vert_1$ 才是 $lVert x Vert_0$ 的biconjugate）。

核範數只是在L無窮球上是rank的凸包