UA MATH567 高维统计专题2 Low-rank矩阵及其估计2 Rank Minimization与Nuclear Norm
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)題:
min?Θrank(Θ)s.t.y=X(Θ)\min_{\Theta} \ \ rank(\Theta) \\ s.t. \ \ y=\mathcal{X}(\Theta)Θmin???rank(Θ)s.t.??y=X(Θ)
同時(shí),通過(guò)SVD我們知道
rank(Θ)=∥σ(Θ)∥0rank(\Theta)=\left\| \sigma(\Theta) \right\|_0rank(Θ)=∥σ(Θ)∥0?
也就是rank-minimization等價(jià)于奇異值的L0L_0L0?-norm minimization;高維統(tǒng)計(jì)專題1中我們證明過(guò)L0L_0L0?-norm minimization是NP-hard problem,所以與高維統(tǒng)計(jì)專題1中的做法類似,我們要找rank-minimization的一個(gè)convex relaxation以保證優(yōu)化在實(shí)踐中可解。經(jīng)過(guò)專題1的討論,很自然我們就能想到用L1L_1L1?-norm近似L0L_0L0?-norm:
∥σ(Θ)∥1=∑σi(Θ)\left\| \sigma(\Theta)\right\|_1=\sum \sigma_i(\Theta)∥σ(Θ)∥1?=∑σi?(Θ)
按這個(gè)定義,我們可以構(gòu)造參數(shù)矩陣Θ\ThetaΘ的一個(gè)新的范數(shù),稱其為Nuclear Norm:
∥Θ∥?=∑σi(Θ)\left\| \Theta \right\|_*=\sum \sigma_i(\Theta)∥Θ∥??=∑σi?(Θ)
如果Θ\ThetaΘ對(duì)稱半正定,也可以稱之為Trace Norm,因?yàn)榇藭r(shí)
∥Θ∥?=∑σi(Θ)=∑λi(Θ)=tr(Θ)\left\| \Theta \right\|_*=\sum \sigma_i(\Theta)=\sum \lambda_i(\Theta)=tr(\Theta)∥Θ∥??=∑σi?(Θ)=∑λi?(Θ)=tr(Θ)
定理 Nuclear Norm是一個(gè)矩陣范數(shù),并且它是算子范數(shù)的對(duì)偶范數(shù)
說(shuō)明
假設(shè)XXX是賦范線性空間,KKK是一個(gè)數(shù)域,f:X→Kf:X \to Kf:X→K是一個(gè)線性函數(shù),則f∈X?f \in X^*f∈X?,下面的范數(shù)是對(duì)偶空間X?X^*X?上的范數(shù)
∥f∥=sup?∥x∥=1,x∈X∣f(x)∣\left\| f \right\|=\sup_{\left\|x \right\|=1,x \in X}|f(x)|∥f∥=∥x∥=1,x∈Xsup?∣f(x)∣
也被稱為是XXX上范數(shù)的對(duì)偶范數(shù)。
證明
用∥?∥\left\| \cdot \right\|∥?∥表示矩陣的算子范數(shù),則需要說(shuō)明?M,N∈Rd1×d2\forall M,N \in \mathbb{R}^{d_1 \times d_2}?M,N∈Rd1?×d2?,
∥M∥?=sup?∥N∥≤1?M,N?∥M∥=sup?∥N∥?≤1?M,N?\left\| M\right\|_*=\sup_{\left\| N \right\| \le 1}\langle M,N \rangle \\ \left\| M\right\|=\sup_{\left\|N \right\|_* \le 1} \langle M,N \rangle∥M∥??=∥N∥≤1sup??M,N?∥M∥=∥N∥??≤1sup??M,N?
引入正交矩陣U∈O(d1),V∈O(d2)U \in O(d_1),V \in O(d_2)U∈O(d1?),V∈O(d2?),則Rd1×d2\mathbb{R}^{d_1 \times d_2}Rd1?×d2?中矩陣的內(nèi)積滿足
?M,N?=?UMV,UMV?\langle M,N \rangle=\langle UMV,UMV\rangle?M,N?=?UMV,UMV?
這是因?yàn)?br /> ?UMV,UMV?=tr(UMV(UNV)T)=tr(UMNTUT)=tr(UUTMNT)=tr(MNT)=?M,N?\langle UMV,UMV\rangle=tr(UMV(UNV)^T) \\ = tr(UMN^TU^T)=tr(UU^TMN^T)=tr(MN^T)=\langle M,N \rangle?UMV,UMV?=tr(UMV(UNV)T)=tr(UMNTUT)=tr(UUTMNT)=tr(MNT)=?M,N?
對(duì)Nuclear Norm與Operator Norm也有類似性質(zhì),即orthogonal-invariant。對(duì)MMM做complete version SVD:M=UΣVTM=U\Sigma V^TM=UΣVT,然后在?M,N?\langle M,N\rangle?M,N?中左乘UTU^TUT右乘VVV將MMM變成只含奇異值的對(duì)角陣Σ\SigmaΣ,并記N~=UTNV\tilde N=U^TNVN~=UTNV,不妨假設(shè)d1≥d2d_1 \ge d_2d1?≥d2?,則
sup?∥N∥≤1?M,N?=sup?∥N~∥≤1?Σ,N~?=∑i=1d2σi=∥M∥?\sup_{\left\| N \right\| \le 1}\langle M,N \rangle = \sup_{\left\| \tilde N \right\| \le 1} \langle \Sigma ,\tilde N \rangle=\sum_{i=1}^{d_2} \sigma_i = \left\| M\right\|_*∥N∥≤1sup??M,N?=∥N~∥≤1sup??Σ,N~?=i=1∑d2??σi?=∥M∥??
上式成立的關(guān)鍵是第二個(gè)等號(hào):
≥\ge≥: 取N~=[Id20]\tilde N=\left[ \begin{matrix} I_{d_2} \\ 0 \end{matrix} \right]N~=[Id2??0?],則?Σ,N~?=∑i=1d2σi\langle \Sigma ,\tilde N \rangle=\sum_{i=1}^{d_2} \sigma_i?Σ,N~?=∑i=1d2??σi?,因此sup?∥N~∥≤1?Σ,N~?\sup_{\left\| \tilde N \right\| \le 1} \langle \Sigma ,\tilde N \ranglesup∥N~∥≤1??Σ,N~?至少應(yīng)該不小于∑i=1d2σi\sum_{i=1}^{d_2} \sigma_i∑i=1d2??σi?
≤\le≤: 因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">∥N~∥≤1\left\| \tilde N \right\| \le 1∥∥∥?N~∥∥∥?≤1,于是它的列向量的L2L_2L2?-norm不會(huì)大于1,所以∣N~ii∣≤1|\tilde N_{ii}| \le 1∣N~ii?∣≤1,?Σ,N~?=∑i=1d2σiN~ii≤∑i=1d2σi\langle \Sigma ,\tilde N \rangle =\sum_{i=1}^{d_2} \sigma_i\tilde N_{ii}\le \sum_{i=1}^{d_2} \sigma_i?Σ,N~?=∑i=1d2??σi?N~ii?≤∑i=1d2??σi?
類似地,
sup?∥N∥?≤1?M,N?=sup?∥N~∥?≤1?Σ,N~?=∥Σ∥sup?∥N~∥?≤1?Σ/∥Σ∥,N~?=∥M∥sup?∥N~∥?≤1?Σ/∥Σ∥,N~?\sup_{\left\| N \right\|_* \le 1}\langle M,N \rangle = \sup_{\left\| \tilde N \right\|_* \le 1} \langle \Sigma ,\tilde N \rangle \\ =\left\| \Sigma \right\| \sup_{\left\| \tilde N \right\|_* \le 1} \langle \Sigma/\left\| \Sigma \right\| ,\tilde N \rangle = \left\| M \right\| \sup_{\left\| \tilde N \right\|_* \le 1} \langle \Sigma/\left\| \Sigma \right\| ,\tilde N \rangle∥N∥??≤1sup??M,N?=∥N~∥??≤1sup??Σ,N~?=∥Σ∥∥N~∥??≤1sup??Σ/∥Σ∥,N~?=∥M∥∥N~∥??≤1sup??Σ/∥Σ∥,N~?
我們需要說(shuō)明
sup?∥N~∥?≤1?Σ/∥Σ∥,N~?=1\sup_{\left\| \tilde N \right\|_* \le 1} \langle \Sigma/\left\| \Sigma \right\| ,\tilde N \rangle=1∥N~∥??≤1sup??Σ/∥Σ∥,N~?=1
≥1\ge 1≥1: 這兩個(gè)矩陣第一個(gè)對(duì)角元都是1就可以得到內(nèi)積為1的結(jié)果
≤1\le 1≤1: ?Σ/∥Σ∥,N~?=∑i=1d2σiσ1N~ii≤∑i=1d2∣N~ii∣≤∥N~∥?≤1\langle \Sigma/\left\| \Sigma \right\| ,\tilde N \rangle=\sum_{i=1}^{d_2}\frac{\sigma_i}{\sigma_1}\tilde N_{ii} \le \sum_{i=1}^{d_2} |\tilde N_{ii}|\le\left\| \tilde N \right\|_* \le 1?Σ/∥Σ∥,N~?=∑i=1d2??σ1?σi??N~ii?≤∑i=1d2??∣N~ii?∣≤∥∥∥?N~∥∥∥???≤1
證畢
評(píng)注 用定義驗(yàn)證Nuclear norm是范數(shù)需要正定、正齊次、三角不等式,前兩個(gè)都是直接得到的,這里簡(jiǎn)單推導(dǎo)一下三角不等式:
∥M+M′∥?=sup?∥N∥≤1?M+M′,N?≤sup?∥N∥≤1?M,N?+sup?∥N∥≤1?M′,N?=∥M∥?+∥M′∥?\left\|M+M' \right\|_* = \sup_{\left\| N \right\| \le 1}\langle M+M',N \rangle \\ \le \sup_{\left\| N \right\| \le 1}\langle M,N \rangle+\sup_{\left\| N \right\| \le 1}\langle M',N \rangle=\left\|M \right\|_*+\left\|M' \right\|_*∥M+M′∥??=∥N∥≤1sup??M+M′,N?≤∥N∥≤1sup??M,N?+∥N∥≤1sup??M′,N?=∥M∥??+∥M′∥??
現(xiàn)在我們就可以把rank-minimization替換為nuclear norm minimization了,這是一個(gè)凸優(yōu)化問(wèn)題
min?Θ∥Θ∥?s.t.y=X(Θ),X:Rd1×d2→Rn\min_{\Theta} \ \ \left\| \Theta \right\|_*\\ s.t. \ \ y=\mathcal{X}(\Theta),\mathcal{X}:\mathbb{R}^{d_1 \times d_2 } \to \mathbb{R}^nΘmin???∥Θ∥??s.t.??y=X(Θ),X:Rd1?×d2?→Rn
其中X\mathcal{X}X是一個(gè)三階張量,它作用在Θ\ThetaΘ上得到一個(gè)nnn維向量,也可以用張量的二點(diǎn)積來(lái)表示
X(Θ)=(?X1,Θ?,?,?Xn,Θ?)T=X:Θ\mathcal{X}(\Theta)=(\langle X_1,\Theta \rangle,\cdots , \langle X_n, \Theta\rangle)^T = \mathcal{X}:\Theta X(Θ)=(?X1?,Θ?,?,?Xn?,Θ?)T=X:Θ
需要注意的是nuclear norm minimization是rank-minimization的convex relaxation,與L1L_1L1?-norm作為L0L_0L0?-norm的relaxation類似,在角點(diǎn)解處二者相等,所以可以得到一樣的sparse solution,這個(gè)性質(zhì)以下面的定理為基礎(chǔ):
定理 在用算子范數(shù)定義的單位球Bop={M:∥M∥≤1}B_{op}=\{M:\left\| M \right\| \le 1\}Bop?={M:∥M∥≤1}中,∥M?∥\left\| M_* \right\|∥M??∥是rank(M)rank(M)rank(M)的凸包絡(luò)。
評(píng)注 因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">rank(M)rank(M)rank(M)是奇異值的0范數(shù),nuclear norm是1范數(shù),而L1L_1L1?-norm是L0L_0L0?-norm的凸包絡(luò),所以很自然可以發(fā)現(xiàn)nuclear norm就是rank的凸包絡(luò)。嚴(yán)謹(jǐn)?shù)淖C明需要對(duì)任意凸函數(shù)fff,說(shuō)明f(M)≤rank(M),?M∈Bopf(M) \le rank(M),\forall M \in B_{op}f(M)≤rank(M),?M∈Bop? ?\Rightarrow? f(M)≤∥M∥?f(M) \le \left\|M \right\|_*f(M)≤∥M∥??,完整證明過(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)題。
- 上一篇: UA MATH567 高维统计专题2 L
- 下一篇: UA MATH567 高维统计专题2 L