UA MATH567 高維統(tǒng)計(jì)III 隨機(jī)矩陣6 亞高斯矩陣的范數(shù)

在前五講的理論基礎(chǔ)上，我們現(xiàn)在開始正式討論隨機(jī)矩陣。假設(shè)$A$是一個(gè)$m\times n$的隨機(jī)矩陣，它的元素$A_{ij}$是互相獨(dú)立的零均值的亞高斯隨機(jī)變量，關(guān)于它的范數(shù)有下面的結(jié)論

隨機(jī)矩陣的范數(shù) $K={\max }_{i,j}{\Vert A_{ij}\Vert }_{{\psi }_2}$, $?t>0$
$$P(\Vert A\Vert ?K(\sqrt{m}+\sqrt{n}+t))\ge 1?2e^{?t^2}$$

這個(gè)結(jié)果說(shuō)明矩陣$A$的范數(shù)的尾部概率也具有亞高斯性。如果$A$是$n\times n$的對(duì)稱陣，則
$$P(\Vert A\Vert ?K(\sqrt{n}+t))\ge 1?4e^{?t^2}$$

證明

第一步，我們先考慮一下算子范數(shù)，
$$\begin{gathered} \Vert A\Vert =\underset{x\in S^{n?1} \\ y\in S^{m?1}}{\max }?Ax,y? \end{gathered}$$

存在$x\in S^{n?1},y\in S^{m?1}$使得$\Vert A\Vert =?Ax,y?$，假設(shè)$\mathcal{N}$是$S^{n?1}$的一個(gè)$?$-net（根據(jù)第四講的討論，我們總是可以用一個(gè)球框住這樣的集網(wǎng)，因此不失一般性，我們可以構(gòu)造cardinality滿足$|\mathcal{N}|<9^n,|\mathcal{M}|<9^m$的集網(wǎng)），$\mathcal{M}$是$S^{m?1}$的一個(gè)$?$-net，則根據(jù)定義$?x_0\in \mathcal{N},?y_0\in \mathcal{M}$，${\Vert x?x_0\Vert }_2\le ?,{\Vert y?y_0\Vert }_2\le ?$，計(jì)算
$$?A{x}_0,y_0?=?Ax,y?+?A(x?x_0),y?+?A{x}_0,y_0?y?$$

其中第二項(xiàng)滿足
$$\begin{gathered} ?A(x?x_0),y?\ge ?{\Vert A(x?x_0)\Vert }_2{\Vert y\Vert }_2 \\ =?{\Vert A(x?x_0)\Vert }_2\ge ??\Vert A\Vert \end{gathered}$$

類似地，第三項(xiàng)滿足
$$?A{x}_0,y_0?y?\ge ??\Vert A\Vert$$

因此
$$\begin{gathered} \Vert A\Vert \le \frac{1}{1?2?}?A{x}_0,y_0?\le \frac{1}{1?2?}\underset{x\in \mathcal{N} \\ y\in \mathcal{M}}{\max }?Ax,y? \end{gathered}$$

第二步，我們討論隨機(jī)矩陣的二次型，$?x\in \mathcal{N},y\in \mathcal{M}$，
$$?Ax,y?=\sum _{i=1}^n\sum _{j=1}^m{A}_{ij}{x}_i{x}_j$$

于是根據(jù)推廣Hoeffding不等式的第一個(gè)結(jié)論，$?C>0$，
$$\begin{gathered} {\Vert ?Ax,y?\Vert }_{{\psi }_2}\le C\sum _{i=1}^n\sum _{j=1}^m{\Vert A_{ij}{x}_i{x}_j\Vert }_{{\psi }_2} \\ =C\sum _{i=1}^n\sum _{j=1}^m{x}_i^2{y}_j^2{\Vert A_{ij}\Vert }_{{\psi }_2}\le C\sum _{i=1}^n\sum _{j=1}^m{x}_i^2{y}_j^2{K}^2=C{K}^2 \end{gathered}$$

這說(shuō)明$?Ax,y?$是亞高斯的。

第三步，使用亞高斯性，
$$P(?Ax,y?\ge u)\le 2e^{?c{u}^2/K^2},?c>0$$

于是
$$\begin{gathered} P(\underset{x\in \mathcal{N} \\ y\in \mathcal{M}}{\max }?Ax,y?\ge u)\le \sum _{x\in \mathcal{N} \\ y\in \mathcal{M}}P(?Ax,y?\ge u) \\ \le 9^{m+n}2e^{?c{u}^2/K^2}=2e^{(m+n)\log 9?c{u}^2/K^2} \end{gathered}$$

因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$u$可以任意選取，為了使這個(gè)尾部概率盡可能小，我們希望通過(guò)選取$u$使得這個(gè)概率的上界在$m,n$趨于無(wú)窮時(shí)收斂到0，一種可行的選取是
$$\begin{gathered} u=C^{\prime }K(\sqrt{m}+\sqrt{n}+t) \\ {u}^2\ge C^{\prime 2}{K}^2(m+n+t) \end{gathered}$$

其中$C^{\prime }>0$是個(gè)常數(shù)，于是
$$2e^{(m+n)\log 9?c{u}^2/K^2}\ge 2e^{(m+n)\log 9?c{C}^{\prime 2}(m+n)?c{C}^{\prime 2}t}$$

選取$C^{\prime }$使得
$$(m+n)\log 9?c{C}^{\prime 2}(m+n)<0,c{C}^{\prime 2}\ge 1$$

則
$$2e^{(m+n)\log 9?c{C}^{\prime 2}(m+n)?c{C}^{\prime 2}t}\ge 2e^{?2t^2}$$

這樣我們就說(shuō)明了$?C>0$
$$P(\Vert A\Vert \le CK(\sqrt{m}+\sqrt{n}+t))\ge 1?2e^{?t^2}$$

第四步，說(shuō)明對(duì)稱的情況，如果$A^T=A$，我們是不能直接用第三步的結(jié)果的，因?yàn)榍叭降玫降慕Y(jié)論要求$A$的所有分量都是獨(dú)立的，而對(duì)稱的矩陣自帶約束$A_{ij}=A_{ji}$，因此關(guān)于主對(duì)角線對(duì)稱的兩個(gè)元素必定不獨(dú)立。一種拆分方法是我們把對(duì)稱矩陣沿主對(duì)角線拆開：
$$A=A^{+}+A^{?}$$

其中$A^{+}$表示下三角部分(包含主對(duì)角線，上三角部分為0)，$A^{?}$表示上三角部分（不包含主對(duì)角線，主對(duì)角線及下三角部分為0），于是
$$\Vert A\Vert =\Vert A^{+}\Vert +\Vert A^{?}\Vert$$

分別對(duì)$\Vert A^{+}\Vert$與$\Vert A^{?}\Vert$使用前三步的結(jié)論即可。

總結(jié)

以上是生活随笔為你收集整理的UA MATH567 高维统计III 随机矩阵6 亚高斯矩阵的范数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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