次高斯復隨機矩陣的算子范數估計

范俊輝,莊智濤

（華北水利水電大學 數學與統計學院,河南 鄭州 450046）

隨機矩陣最早由數學家Wishart 提出,是指元素為隨機變量的矩陣,文獻[1-3]介紹了有關隨機矩陣的基礎知識。 隨機矩陣理論主要研究隨機矩陣特征值（或奇異值） 的概率行為,其研究結果已經應用于許多領域,如計算數學、機器學習、優化理論等。 次高斯分布是應用中常見的一類重要分布,文獻[4-6]介紹了次高斯和次指數實隨機變量,并給出了一些實隨機變量的集中不等式。 Vershynin[7]給出了次高斯實隨機矩陣的算子范數估計。 上述研究都是在實空間中進行的,并未給出復空間中的情況,而在相位恢復[8-10]、Fourier 光學[11]等領域,復隨機矩陣的應用更加廣泛,因此研究次高斯復隨機矩陣的算子范數估計具有重要意義。

本研究首先將實隨機變量的性質推廣到復隨機變量,然后在此基礎上給出次高斯和次指數復隨機變量的集中不等式,最后利用ε-網技術對次高斯復隨機矩陣的算子范數進行估計。

1 復隨機變量的集中不等式

本節將給出次高斯和次指數復隨機變量的定義,將次高斯和次指數實隨機變量的性質推廣到次高斯和次指數復隨機變量上去,并在此基礎上證明Bernstein 不等式和Hoeffding 不等式。 下面給出次高斯和次指數復隨機變量的定義。

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

定義2一個復隨機變量Z的次指數范數為若Z的次指數范數是有限的,則稱它是次指數的。

文獻[7] 介紹了次高斯和次指數實隨機變量的性質:在R 中獨立的次高斯隨機變量X1,X2,…,Xn的和還是次高斯的,且一個隨機變量X是次高斯的當且僅當X2是次指數的,且兩個次高斯隨機變量X、Y的乘積是次指數的,且下面的引理說明了復隨機變量和它實部與虛部之間的關系。

引理1一個復隨機變量Z是次高斯的當且僅當它的實部X和虛部Y都是次高斯的,并且有

引理2一個復隨機變量Z是次指數的當且僅當它的實部X與虛部Y都是次指數的,并且有

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

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

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

上面利用次高斯和次指數實隨機變量的性質,證明了復隨機變量的次高斯和次指數性與它的實部和虛部的次高斯和次指數性是等價的,接下來把這些性質應用到復隨機變量上。

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

引理4一個復隨機變量Z是次高斯的當且僅當Z2是次指數的,并且有設Z1、Z2是次高斯復隨機變量,那么Z1Z2是次指數的,并且有

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

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

在此基礎上,證明復隨機變量的集中不等式即Hoeffding 不等式和Bernstein 不等式。

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

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

定理2設Z1,Z2,…,Zn為獨立零均值次指數復隨機變量,則存在絕對常數c,使得對任意t ＞0,都有

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

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

2 復隨機向量的性質

本節將討論復隨機向量的性質。 首先介紹各向同性隨機向量的定義和性質,然后在次高斯實隨機向量的基礎上定義次高斯復隨機向量并討論其性質。 下面給出各向同性隨機向量的定義。

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

接下來給出各向同性隨機向量的充分必要條件及其性質。

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

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

引理6設Z是Cn中各向同性隨機向量,則有另外,如果Z和是Cn中兩個獨立的各向同性隨機向量,則有

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

前一節里已經介紹了次高斯復隨機變量,現在把它推廣到高維空間上去。 文獻[7] 定義了次高斯實隨機向量:一個實隨機向量X∈Rn的次高斯范數在此基礎上,定義次高斯復隨機向量。

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

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

定理3一個復隨機向量Z=X+iY是次高斯的當且僅當對任意的z∈Cn,〈Z,z〉都是次高斯隨機變量。

證明首先證明充分性。 假設Z是次高斯復隨機向量,則X、Y都是次高斯隨機向量。 記z=a+ib,把內積展開得到

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

3 次高斯復隨機矩陣的算子范數估計

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

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

因為Cn同構于R2n,所以很容易得到復單位球的覆蓋數與維數n呈指數關系。

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

接下來將利用ε-網計算一個矩陣的算子范數。

引理9[7]設A是一個m×n復矩陣,ε∈[0,1） 。 令N是Sn-1上任意一個ε-網,則

因為矩陣的算子范數除由向量的范數導出外,還可以由向量的內積導出,所以可以在ε-網上用向量的內積導出矩陣的算子范數。

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

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

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

文獻[7] 給出了帶有獨立次高斯元素的實隨機矩陣算子范數的集中不等式,現將這個結論應用到復隨機矩陣上,給出復隨機矩陣算子范數的一個上界估計。

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

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

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

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

令C≥ln 18/c1,可得

下面將改進定理4 的結果。 首先,給出復隨機矩陣更加精確的雙側界。 然后,將復隨機矩陣每個元素是獨立的放寬到每個行向量是獨立的。

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

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

令C≥ln 18/c1,可得

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

推論1設A是一個m×n（m?n） 復隨機矩陣,它的每一行Ai是Cn中各向同性獨立零均值的次高斯隨機向量,則對于任意t ＞0,都有成立的概率至少為1- 2exp（-t2） 。 其中是滿足定理5 的絕對常數且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 數值實驗

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

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

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

圖1 算例1Fig.1 Example 1

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

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

圖2 算例2Fig.2 Example 2

5 結語

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