次高斯復(fù)隨機(jī)矩陣的算子范數(shù)估計

范俊輝,莊智濤

（華北水利水電大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,河南 鄭州 450046）

隨機(jī)矩陣最早由數(shù)學(xué)家Wishart 提出,是指元素為隨機(jī)變量的矩陣,文獻(xiàn)[1-3]介紹了有關(guān)隨機(jī)矩陣的基礎(chǔ)知識。 隨機(jī)矩陣?yán)碚撝饕芯侩S機(jī)矩陣特征值（或奇異值） 的概率行為,其研究結(jié)果已經(jīng)應(yīng)用于許多領(lǐng)域,如計算數(shù)學(xué)、機(jī)器學(xué)習(xí)、優(yōu)化理論等。 次高斯分布是應(yīng)用中常見的一類重要分布,文獻(xiàn)[4-6]介紹了次高斯和次指數(shù)實隨機(jī)變量,并給出了一些實隨機(jī)變量的集中不等式。 Vershynin[7]給出了次高斯實隨機(jī)矩陣的算子范數(shù)估計。 上述研究都是在實空間中進(jìn)行的,并未給出復(fù)空間中的情況,而在相位恢復(fù)[8-10]、Fourier 光學(xué)[11]等領(lǐng)域,復(fù)隨機(jī)矩陣的應(yīng)用更加廣泛,因此研究次高斯復(fù)隨機(jī)矩陣的算子范數(shù)估計具有重要意義。

本研究首先將實隨機(jī)變量的性質(zhì)推廣到復(fù)隨機(jī)變量,然后在此基礎(chǔ)上給出次高斯和次指數(shù)復(fù)隨機(jī)變量的集中不等式,最后利用ε-網(wǎng)技術(shù)對次高斯復(fù)隨機(jī)矩陣的算子范數(shù)進(jìn)行估計。

1 復(fù)隨機(jī)變量的集中不等式

本節(jié)將給出次高斯和次指數(shù)復(fù)隨機(jī)變量的定義,將次高斯和次指數(shù)實隨機(jī)變量的性質(zhì)推廣到次高斯和次指數(shù)復(fù)隨機(jī)變量上去,并在此基礎(chǔ)上證明Bernstein 不等式和Hoeffding 不等式。 下面給出次高斯和次指數(shù)復(fù)隨機(jī)變量的定義。

定義1一個復(fù)隨機(jī)變量Z=X+ iY（X、Y都是實隨機(jī)變量） 的次高斯范數(shù)為若Z的次高斯范數(shù)是有限的,則稱它是次高斯的。

定義2一個復(fù)隨機(jī)變量Z的次指數(shù)范數(shù)為若Z的次指數(shù)范數(shù)是有限的,則稱它是次指數(shù)的。

文獻(xiàn)[7] 介紹了次高斯和次指數(shù)實隨機(jī)變量的性質(zhì):在R 中獨(dú)立的次高斯隨機(jī)變量X1,X2,…,Xn的和還是次高斯的,且一個隨機(jī)變量X是次高斯的當(dāng)且僅當(dāng)X2是次指數(shù)的,且兩個次高斯隨機(jī)變量X、Y的乘積是次指數(shù)的,且下面的引理說明了復(fù)隨機(jī)變量和它實部與虛部之間的關(guān)系。

引理1一個復(fù)隨機(jī)變量Z是次高斯的當(dāng)且僅當(dāng)它的實部X和虛部Y都是次高斯的,并且有

引理2一個復(fù)隨機(jī)變量Z是次指數(shù)的當(dāng)且僅當(dāng)它的實部X與虛部Y都是次指數(shù)的,并且有

證明假設(shè)Z是次指數(shù)隨機(jī)變量,記所以有‖X‖ψ1≤a=‖Z‖ψ1,類似的有‖Y‖ψ1≤a=‖Z‖ψ1。 假設(shè)X、Y是次指

數(shù)隨機(jī)變量,記‖X‖ψ1=a,‖Y‖ψ1=b,則有再利用不等式因為ex是一個凸函數(shù),所以有

由定義2 可以得到‖Z‖ψ1≤a+b= ‖X‖ψ1+ ‖Y‖ψ1。

上面利用次高斯和次指數(shù)實隨機(jī)變量的性質(zhì),證明了復(fù)隨機(jī)變量的次高斯和次指數(shù)性與它的實部和虛部的次高斯和次指數(shù)性是等價的,接下來把這些性質(zhì)應(yīng)用到復(fù)隨機(jī)變量上。

引理3設(shè)Z1,Z2,…,Zn為獨(dú)立零均值的次高斯復(fù)隨機(jī)變量,那么也是次高斯復(fù)隨機(jī)變量,并且有其中C是一個絕對常數(shù)。

引理4一個復(fù)隨機(jī)變量Z是次高斯的當(dāng)且僅當(dāng)Z2是次指數(shù)的,并且有設(shè)Z1、Z2是次高斯復(fù)隨機(jī)變量,那么Z1Z2是次指數(shù)的,并且有

文獻(xiàn)[7] 給出了次高斯和次指數(shù)實隨機(jī)變量的集中不等式,設(shè)X1,X2,…,Xn為獨(dú)立零均值的次高斯實隨機(jī)變量,則存在絕對常數(shù)c,使得對任意t ＞0,都有

設(shè)X1,X2,…,Xn為獨(dú)立零均值的次指數(shù)實隨機(jī)變量,則存在絕對常數(shù)c,使得對任意的t ＞0,都有

在此基礎(chǔ)上,證明復(fù)隨機(jī)變量的集中不等式即Hoeffding 不等式和Bernstein 不等式。

定理1設(shè)Z1,Z2,…,Zn為獨(dú)立零均值的次高斯復(fù)隨機(jī)變量,則存在絕對常數(shù)c,使得對任意t ＞0,都有

證明令ξi=Xi（1 ≤i≤n） ,ξi=Yi（n+ 1 ≤i≤2n） ,將不等式兩邊同時取平方并代入ξi,可得

定理2設(shè)Z1,Z2,…,Zn為獨(dú)立零均值次指數(shù)復(fù)隨機(jī)變量,則存在絕對常數(shù)c,使得對任意t ＞0,都有

證明令ξi=Xi（1 ≤i≤n） ,ξi=Yi（n+ 1 ≤i≤2n） 。

最后,將ξi代入式（10） 并使用引理2 得到

2 復(fù)隨機(jī)向量的性質(zhì)

本節(jié)將討論復(fù)隨機(jī)向量的性質(zhì)。 首先介紹各向同性隨機(jī)向量的定義和性質(zhì),然后在次高斯實隨機(jī)向量的基礎(chǔ)上定義次高斯復(fù)隨機(jī)向量并討論其性質(zhì)。 下面給出各向同性隨機(jī)向量的定義。

定義3設(shè)Z是Cn中的隨機(jī)向量,In表示單位矩陣,ZH表示Z的共軛轉(zhuǎn)置。 若Z滿足EZZH=In,則稱它是各向同性的。

接下來給出各向同性隨機(jī)向量的充分必要條件及其性質(zhì)。

引理5Z是Cn中各向同性隨機(jī)向量的充分必要條件,對于任意的z∈Cn都有

證明假設(shè)EZZH=In,等式兩邊同時左乘zH右乘z,可得假設(shè)因此,EZZH=In。

引理6設(shè)Z是Cn中各向同性隨機(jī)向量,則有另外,如果Z和是Cn中兩個獨(dú)立的各向同性隨機(jī)向量,則有

證明首先證明第一個性質(zhì)。 因為看作1×1 的矩陣,所以由tr（ZHZ） =tr（ZZH） 和跡的線性性質(zhì),可得最后由各向同性的定義,可得接下來證明第二個性質(zhì)。 首先固定,然后關(guān)于取條件期望,記作。 由全期望公式可得

前一節(jié)里已經(jīng)介紹了次高斯復(fù)隨機(jī)變量,現(xiàn)在把它推廣到高維空間上去。 文獻(xiàn)[7] 定義了次高斯實隨機(jī)向量:一個實隨機(jī)向量X∈Rn的次高斯范數(shù)在此基礎(chǔ)上,定義次高斯復(fù)隨機(jī)向量。

定義4一個復(fù)隨機(jī)向量Z=X+ iY的次高斯范數(shù)為如果Z的實部X與虛部Y都是次高斯實隨機(jī)向量,則稱Z是一個次高斯復(fù)隨機(jī)向量。

對于一個實隨機(jī)向量X來說,如果對任意的x∈Rn,〈X,x〉 都是次高斯隨機(jī)變量,則稱X為次高斯實隨機(jī)向量。 下面的定理3 表明這一性質(zhì)對于復(fù)隨機(jī)向量同樣成立。

定理3一個復(fù)隨機(jī)向量Z=X+iY是次高斯的當(dāng)且僅當(dāng)對任意的z∈Cn,〈Z,z〉都是次高斯隨機(jī)變量。

證明首先證明充分性。 假設(shè)Z是次高斯復(fù)隨機(jī)向量,則X、Y都是次高斯隨機(jī)向量。 記z=a+ib,把內(nèi)積展開得到

然后證明必要性。 假設(shè)〈Z,z〉 是次高斯隨機(jī)變量,令zi=（0,0,…,1,0,…,0） ,可得Zi=Xi+iYi都是次高斯的。 因此,X、Y都是次高斯隨機(jī)向量,由定義3 可知Z是次高斯復(fù)隨機(jī)向量。

3 次高斯復(fù)隨機(jī)矩陣的算子范數(shù)估計

本節(jié)將利用ε-網(wǎng)技術(shù),給出次高斯復(fù)隨機(jī)矩陣的算子范數(shù)估計。 首先介紹ε-網(wǎng)。 設(shè)（T,d） 是一個度量空間,K是T的一個子集,ε ＞0,如果對任意的x∈K都存在x0∈N使得d（x,x0） ≤ε,則稱N是K的一個ε-網(wǎng)。 若N是K的所有ε-網(wǎng)中元素數(shù)目最小的集合,則稱N的元素數(shù)目是K的覆蓋數(shù),記作N（K,d,ε） 。如果度量空間（T,d） 的子集N中所有不同的點(diǎn)x、y都有d（x,y）＞ε,則稱N是ε-分離的。 集合K?T的ε-分離子集的最大可能數(shù)目稱為K的填充數(shù),記作P（K,d,ε） 。 特別地,若N是K的一個極大ε-分離子集,那么N是K的一個ε-網(wǎng)。 并且,對于任何集合K?T和任意ε ＞0,都有P（K,d,2ε） ≤N（K,d,ε） ≤P（K,d,ε） 。 設(shè)A和B是度量空間（T,d） 的子集,記A+B∶={a+b∶a∈A,b∈B}。 下面的引理說明了覆蓋數(shù)和度量空間中體積的關(guān)系。

引理7[7]設(shè)K是度量空間（T,d） 的一個子集,則對于任意的ε ＞0,都有

因為Cn同構(gòu)于R2n,所以很容易得到復(fù)單位球的覆蓋數(shù)與維數(shù)n呈指數(shù)關(guān)系。

引理8對于任意ε ＞0,Cn中的單位球Bn2的覆蓋數(shù)滿足

接下來將利用ε-網(wǎng)計算一個矩陣的算子范數(shù)。

引理9[7]設(shè)A是一個m×n復(fù)矩陣,ε∈[0,1） 。 令N是Sn-1上任意一個ε-網(wǎng),則

因為矩陣的算子范數(shù)除由向量的范數(shù)導(dǎo)出外,還可以由向量的內(nèi)積導(dǎo)出,所以可以在ε-網(wǎng)上用向量的內(nèi)積導(dǎo)出矩陣的算子范數(shù)。

引理10設(shè)A是一個m×n（m?n） 復(fù)矩陣,ε∈[0,1/2） ,令N、M分別是Sn-1和Sm-1上任意一個ε-網(wǎng),則有

如果m=n,且A是Hermitian 矩陣,則有

證明首先證明式（17） 。 因為接下來證明上界,首先固定兩個向量x∈Sn-1,y∈Sm-1滿足然后選擇x0∈N,y0∈M,使得利用內(nèi)積的性質(zhì)和三角不等式, 可得

文獻(xiàn)[7] 給出了帶有獨(dú)立次高斯元素的實隨機(jī)矩陣算子范數(shù)的集中不等式,現(xiàn)將這個結(jié)論應(yīng)用到復(fù)隨機(jī)矩陣上,給出復(fù)隨機(jī)矩陣算子范數(shù)的一個上界估計。

定理4設(shè)A是一個m×n復(fù)隨機(jī)矩陣,它的每一個元素Ai,j都是獨(dú)立零均值的次高斯復(fù)隨機(jī)變量,則對于任意的t ＞0,都有成立的概率至少為1- 2exp（-t2） 。 其中,C是一個較大的絕對常數(shù)。

證明令N、M分別是Sn-1和Sm-1的1/4-網(wǎng)。 由引理8,可得由引理10,矩陣A的算子范數(shù)可以利用ε-網(wǎng)來控制:

然后,固定x∈N,y∈M,則是獨(dú)立的次高斯復(fù)隨機(jī)變量的和。 由引理3,可得將它表示成概率的形式,即對任意的u ＞0,有

接下來,對任意的x、y,估計它們的一致上界。 假設(shè)事件發(fā)生,那么就存在x∈N,成立,因此

令C≥ln 18/c1,可得

下面將改進(jìn)定理4 的結(jié)果。 首先,給出復(fù)隨機(jī)矩陣更加精確的雙側(cè)界。 然后,將復(fù)隨機(jī)矩陣每個元素是獨(dú)立的放寬到每個行向量是獨(dú)立的。

定理5設(shè)A是一個m×n復(fù)隨機(jī)矩陣,它的每一行Ai是Cn中各向同性獨(dú)立零均值的次高斯復(fù)隨機(jī)向量,則對于任意t ＞0,都有成立的概率至少為1- 2exp（-t2） 。 其中,δ=C是一個較大的絕對常數(shù)。

證明首先令N是Sn-1上的1/4-網(wǎng),則由引理10,可得然后,固定x∈N并將表示為隨機(jī)變量和的形式,即由于Ai是各向同性獨(dú)立的次高斯隨機(jī)向量且是次高斯隨機(jī)變量且從而有X2i- 1 是獨(dú)立零均值的次指數(shù)隨機(jī)變量。 由引理4,可以得到現(xiàn)在使用推論3,對任意的ε ＞0,都有令ε=CK2max（δ,δ2） 且C≥1,則將δ代入并利用不等式（a+b）2≥a2+b2（a≥0,b≥0） ,可得接下來,對任意的x估計它們的一致上界。 假設(shè)事件發(fā)生,那么就存在x∈N使得成立,因此

令C≥ln 18/c1,可得

令si（A） 是矩陣Am×n（m?n） 的奇異值,并按非遞增順序（s1（A） ≥…≥sn（A） ≥0） 排列。 接下來,給出隨機(jī)矩陣A的全部譜（奇異值） 的一個雙側(cè)界估計。

推論1設(shè)A是一個m×n（m?n） 復(fù)隨機(jī)矩陣,它的每一行Ai是Cn中各向同性獨(dú)立零均值的次高斯隨機(jī)向量,則對于任意t ＞0,都有成立的概率至少為1- 2exp（-t2） 。 其中是滿足定理5 的絕對常數(shù)且CK2≥1。

證明由定理5 可知因為由于CK2≥1,所以1+CK2max（δ,δ2） ≤1+CK2（2δ,δ2） ≤1+2CK2δ+（CK2δ）2=（1+CK2δ）2。 因此,s2i（A） ≤m（1+CK2δ）2,將δ代入可以得到si（A）若CK2max（δ,δ2） ≥1,下界顯然成立。 若CK2max（δ,δ2）＜1,則有1-CK2max（δ,δ2） ≥1-CK2δ≥1- 2CK2δ+（CK2δ）2= （1-CK2δ）2。 因此,s2i（A） ≥m（1-CK2δ）2,將δ代入可得si（A）

4 數(shù)值實驗

本節(jié)通過數(shù)值算例展示定理5 和推論1 的有效性。 在數(shù)值實驗中,使用復(fù)高斯隨機(jī)矩陣A∈Cm×n,其中隨機(jī)矩陣的每個元素都是獨(dú)立同分布的標(biāo)準(zhǔn)復(fù)高斯隨機(jī)變量,即ak,l～N（0,1/2） +iN（0,1/2） 。 取t從0.1到3.0,步長為0.1。 對于每個t,做1 000 次實驗,從而得到實驗的經(jīng)驗概率。

算例1驗證定理5 的準(zhǔn)確性。 在實驗中,分別選擇n= 50,m= 500 和n= 50,m= 1 000。 令C= 3.9,對于每個t,當(dāng)算子范數(shù)滿足定理5 的不等式時,記實驗有效次數(shù)加1,并稱實驗有效次數(shù)與1 000 的比值為定理5 的不等式成立的經(jīng)驗概率Pt。

圖1 展示了算例1 理論概率下界1- 2exp（-t2） （虛線） 與經(jīng)驗概率Pt（實線） 在[0,3.0] 上的值,結(jié)果顯示理論概率下界是一個良好的估計。

圖1 算例1Fig.1 Example 1

算例2驗證推論1 的有效性。 同樣考慮n= 50,m= 500 和n= 50,m= 1 000 兩種情況。 令C= 1.8,當(dāng)隨機(jī)矩陣A的奇異值滿足推論1 的不等式時,記實驗有效次數(shù)加1,并稱實驗有效次數(shù)與1 000的比值為推論1 不等式成立的經(jīng)驗概率Pt。

圖2 展示了算例2 理論概率下界1- 2exp（-t2） （虛線） 與經(jīng)驗概率Pt（實線） 在[0,3.0] 上的值,結(jié)果顯示理論概率下界是一個良好的估計。

圖2 算例2Fig.2 Example 2

5 結(jié)語

本研究將實空間中的次高斯和次指數(shù)分布的性質(zhì)應(yīng)用到復(fù)空間中,并利用這些性質(zhì)證明了復(fù)隨機(jī)變量的Hoeffding 不等式和Bernstein 不等式。 此外,利用ε-網(wǎng)技術(shù)給出了次高斯復(fù)隨機(jī)矩陣算子范數(shù)的一個雙側(cè)界估計。