UA MATH567 高維統(tǒng)計(jì)專題2 Low-rank矩陣及其估計(jì)2 Rank Minimization與Nuclear Norm

上一講我們已經(jīng)提到了用rank-minimization對(duì)參數(shù)矩陣進(jìn)行估計(jì)的建模方法，這一講我們討論無(wú)噪聲情況下的rank-minimization問(wèn)題：

$$\begin{gathered} \underset{\Theta }{\min }rank(\Theta ) \\ s.t.y=\mathcal{X}(\Theta ) \end{gathered}$$

同時(shí)，通過(guò)SVD我們知道
$$rank(\Theta )={\Vert \sigma (\Theta )\Vert }_0$$

也就是rank-minimization等價(jià)于奇異值的$L_0$-norm minimization；高維統(tǒng)計(jì)專題1中我們證明過(guò)$L_0$-norm minimization是NP-hard problem，所以與高維統(tǒng)計(jì)專題1中的做法類似，我們要找rank-minimization的一個(gè)convex relaxation以保證優(yōu)化在實(shí)踐中可解。經(jīng)過(guò)專題1的討論，很自然我們就能想到用$L_1$-norm近似$L_0$-norm：
$${\Vert \sigma (\Theta )\Vert }_1=\sum {\sigma }_i(\Theta )$$

按這個(gè)定義，我們可以構(gòu)造參數(shù)矩陣$\Theta$的一個(gè)新的范數(shù)，稱其為Nuclear Norm：
$${\Vert \Theta \Vert }_{?}=\sum {\sigma }_i(\Theta )$$

如果$\Theta$對(duì)稱半正定，也可以稱之為Trace Norm，因?yàn)榇藭r(shí)
$${\Vert \Theta \Vert }_{?}=\sum {\sigma }_i(\Theta )=\sum {\lambda }_i(\Theta )=tr(\Theta )$$

---

定理 Nuclear Norm是一個(gè)矩陣范數(shù)，并且它是算子范數(shù)的對(duì)偶范數(shù)

說(shuō)明
假設(shè)$X$是賦范線性空間，$K$是一個(gè)數(shù)域，$f:X\to K$是一個(gè)線性函數(shù)，則$f\in X^{?}$，下面的范數(shù)是對(duì)偶空間$X^{?}$上的范數(shù)
$$\Vert f\Vert =\underset{\Vert x\Vert =1,x\in X}{\sup }|f(x)|$$

也被稱為是$X$上范數(shù)的對(duì)偶范數(shù)。

證明
用$\Vert ?\Vert$表示矩陣的算子范數(shù)，則需要說(shuō)明$?M,N\in {\mathbb{R}}^{d_1\times d_2}$，
$$\begin{gathered} {\Vert M\Vert }_{?}=\underset{\Vert N\Vert \le 1}{\sup }?M,N? \\ \Vert M\Vert =\underset{{\Vert N\Vert }_{?}\le 1}{\sup }?M,N? \end{gathered}$$

引入正交矩陣$U\in O(d_1),V\in O(d_2)$，則${\mathbb{R}}^{d_1\times d_2}$中矩陣的內(nèi)積滿足
$$?M,N?=?UMV,UMV?$$

這是因?yàn)?br /> $$\begin{gathered} ?UMV,UMV?=tr(UMV(UNV{)}^T) \\ =tr(UM{N}^T{U}^T)=tr(U{U}^{T}M{N}^T)=tr(M{N}^T)=?M,N? \end{gathered}$$

對(duì)Nuclear Norm與Operator Norm也有類似性質(zhì)，即orthogonal-invariant。對(duì)$M$做complete version SVD：$M=U\Sigma V^T$，然后在$?M,N?$中左乘$U^T$右乘$V$將$M$變成只含奇異值的對(duì)角陣$\Sigma$，并記$\tilde{N}=U^{T}NV$，不妨假設(shè)$d_1\ge d_2$，則
$$\underset{\Vert N\Vert \le 1}{\sup }?M,N?=\underset{\Vert \tilde{N}\Vert \le 1}{\sup }?\Sigma ,\tilde{N}?=\sum _{i=1}^{d_2}{\sigma }_i={\Vert M\Vert }_{?}$$

上式成立的關(guān)鍵是第二個(gè)等號(hào)：

$\ge$: 取$\tilde{N}=\left[\begin{array}{c}{I}_{d_2}\\ 0\end{array}\right]$，則$?\Sigma ,\tilde{N}?={\sum }_{i=1}^{d_2}{\sigma }_i$，因此${\sup }_{\Vert \tilde{N}\Vert \le 1}?\Sigma ,\tilde{N}?$至少應(yīng)該不小于${\sum }_{i=1}^{d_2}{\sigma }_i$

$\le$: 因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$\Vert \tilde{N}\Vert \le 1$，于是它的列向量的$L_2$-norm不會(huì)大于1，所以$|{\tilde{N}}_{ii}|\le 1$，$?\Sigma ,\tilde{N}?={\sum }_{i=1}^{d_2}{\sigma }_i{\tilde{N}}_{ii}\le {\sum }_{i=1}^{d_2}{\sigma }_i$

類似地，
$$\begin{gathered} \underset{{\Vert N\Vert }_{?}\le 1}{\sup }?M,N?=\underset{{\Vert \tilde{N}\Vert }_{?}\le 1}{\sup }?\Sigma ,\tilde{N}? \\ =\Vert \Sigma \Vert \underset{{\Vert \tilde{N}\Vert }_{?}\le 1}{\sup }?\Sigma /\Vert \Sigma \Vert ,\tilde{N}?=\Vert M\Vert \underset{{\Vert \tilde{N}\Vert }_{?}\le 1}{\sup }?\Sigma /\Vert \Sigma \Vert ,\tilde{N}? \end{gathered}$$

我們需要說(shuō)明
$$\underset{{\Vert \tilde{N}\Vert }_{?}\le 1}{\sup }?\Sigma /\Vert \Sigma \Vert ,\tilde{N}?=1$$

$\ge 1$: 這兩個(gè)矩陣第一個(gè)對(duì)角元都是1就可以得到內(nèi)積為1的結(jié)果

$\le 1$: $?\Sigma /\Vert \Sigma \Vert ,\tilde{N}?={\sum }_{i=1}^{d_2}\frac{{\sigma }_i}{{\sigma }_1}{\tilde{N}}_{ii}\le {\sum }_{i=1}^{d_2}|{\tilde{N}}_{ii}|\le {\Vert \tilde{N}\Vert }_{?}\le 1$

證畢

評(píng)注 用定義驗(yàn)證Nuclear norm是范數(shù)需要正定、正齊次、三角不等式，前兩個(gè)都是直接得到的，這里簡(jiǎn)單推導(dǎo)一下三角不等式：
$$\begin{gathered} {\Vert M+M^{\prime }\Vert }_{?}=\underset{\Vert N\Vert \le 1}{\sup }?M+M^{\prime },N? \\ \le \underset{\Vert N\Vert \le 1}{\sup }?M,N?+\underset{\Vert N\Vert \le 1}{\sup }?M^{\prime },N?={\Vert M\Vert }_{?}+{\Vert M^{\prime }\Vert }_{?} \end{gathered}$$

---

現(xiàn)在我們就可以把rank-minimization替換為nuclear norm minimization了，這是一個(gè)凸優(yōu)化問(wèn)題

$$\begin{gathered} \underset{\Theta }{\min }{\Vert \Theta \Vert }_{?} \\ s.t.y=\mathcal{X}(\Theta ),\mathcal{X}:{\mathbb{R}}^{d_1\times d_2}\to {\mathbb{R}}^n \end{gathered}$$

其中$\mathcal{X}$是一個(gè)三階張量，它作用在$\Theta$上得到一個(gè)$n$維向量，也可以用張量的二點(diǎn)積來(lái)表示
$$\mathcal{X}(\Theta )=(?X_1,\Theta ?,?,?X_n,\Theta ?{)}^T=\mathcal{X}:\Theta$$

需要注意的是nuclear norm minimization是rank-minimization的convex relaxation，與$L_1$-norm作為$L_0$-norm的relaxation類似，在角點(diǎn)解處二者相等，所以可以得到一樣的sparse solution，這個(gè)性質(zhì)以下面的定理為基礎(chǔ)：

定理 在用算子范數(shù)定義的單位球$B_{op}=\{M:\Vert M\Vert \le 1\}$中，$\Vert M_{?}\Vert$是$rank(M)$的凸包絡(luò)。

評(píng)注 因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$rank(M)$是奇異值的0范數(shù)，nuclear norm是1范數(shù)，而$L_1$-norm是$L_0$-norm的凸包絡(luò)，所以很自然可以發(fā)現(xiàn)nuclear norm就是rank的凸包絡(luò)。嚴(yán)謹(jǐn)?shù)淖C明需要對(duì)任意凸函數(shù)$f$，說(shuō)明$f(M)\le rank(M),?M\in B_{op}$ $?$ $f(M)\le {\Vert M\Vert }_{?}$，完整證明過(guò)程可以閱讀Wright and Ma 2020年那本高維數(shù)據(jù)分析的section 4.3.3

總結(jié)

以上是生活随笔為你收集整理的UA MATH567 高维统计专题2 Low-rank矩阵及其估计2 Rank Minimization与Nuclear Norm的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。