UA MATH567 高維統(tǒng)計(jì)II 隨機(jī)向量7 Grothendieck不等式

上一講我們介紹了用半正定規(guī)劃近似一個(gè)整數(shù)規(guī)劃的方法，要證明這種近似與原整數(shù)規(guī)劃解的大小關(guān)系，我們需要Grothendieck不等式，所以這一講我們證明這個(gè)不等式：

Grothendieck不等式
$A$是$m\times n$的實(shí)矩陣，$x_i,y_j\in \{?1,1\}$，假設(shè)$|{\sum }_{i,j}{A}_{ij}{x}_i{y}_j|\le 1$，則$?H$(Hilbert space)，$?u_i,v_j\in H$，$\Vert u_i\Vert =\Vert v_j\Vert =1$，
$$|\sum _{i,j}{A}_{i,j}?u_i,v_j?|\le K,K\le 1.783$$

證明
首先我們分析一下這個(gè)不等式的條件，$x_i,y_j\in \{?1,1\}$，$|{\sum }_{i,j}{A}_{ij}{x}_i{y}_j|\le 1$，它等價(jià)于
$$|\sum _{i,j}{A}_{ij}{x}_i{y}_j|\le \max |x_i|\max |y_j|$$

如果$x_i,y_j\in \{?1,1\}$，$|{\sum }_{i,j}{A}_{ij}{x}_i{y}_j|\le 1$成立，顯然
$$|\sum _{i,j}{A}_{ij}{x}_i{y}_j|\le \max |x_i|\max |y_j|$$

如果$|{\sum }_{i,j}{A}_{ij}{x}_i{y}_j|\le \max |x_i|\max |y_j|$成立，則
$$|\sum _{i,j}{A}_{ij}\frac{x_i}{\max |x_i|}\frac{y_j}{\max |y_j|}|\le 1$$

顯然$\frac{x_i}{\max |x_i|},\frac{y_j}{\max |y_j|}$都在$[?1,1]$上取值，注意到${\sum }_{i,j}{A}_{ij}{x}_i{y}_j$是一個(gè)線性函數(shù)，它的最優(yōu)解一定是角點(diǎn)解，所以$x_i,y_j\in \{?1,1\}$，$|{\sum }_{i,j}{A}_{ij}{x}_i{y}_j|\le 1$；

與之類似，我們可以分析一下結(jié)論，$?H$(Hilbert space)，$?u_i,v_j\in H$，$\Vert u_i\Vert =\Vert v_j\Vert =1$，
$$|\sum _{i,j}{A}_{i,j}?u_i,v_j?|\le K,K\le 1.783$$

等價(jià)于$?H$(Hilbert space)，$?u_i,v_j\in H$
$$|\sum _{i,j}{A}_{i,j}?u_i,v_j?|\le K\underset{i}{\max }\Vert u_i\Vert \underset{j}{\max }\Vert v_j\Vert$$

---

第一步，Reduction (先證明一個(gè)更弱的結(jié)果，即$K$與$A$相關(guān))

引入$K(A)$，
$$K(A)=\inf \{K:|\sum _{i,j}{A}_{i,j}?u_i,v_j?|\le K\underset{i}{\max }\Vert u_i\Vert \underset{j}{\max }\Vert v_j\Vert \}$$

顯然
$$K(A)\le \sum |A_{ij}|$$

假設(shè)$\{u_i\},\{v_j\}$是使得$K(A)$成為最小的$u_i,v_j\in H$，從而
$$\sum _{i,j}{A}_{i,j}?u_i,v_j?=K(A)$$

---

第二步，Randomness
定義$g～N(0,I_N)$，$N=n+m$，定義$U_i=?g,u_i?,V_j=?g,v_j?$，則$U_i,V_j$都是標(biāo)準(zhǔn)正態(tài)隨機(jī)變量，
$$E[U_i{V}_j]=?u_i,v_j?$$

所以
$$K(A)=\sum _{i,j}{A}_{i,j}?u_i,v_j?=\sum _{i,j}{A}_{i,j}E[U_i{V}_j]=E\sum _{i,j}{A}_{ij}{U}_i{V}_j$$

---

第三步，Truncation

定義$R>1$，
$$\begin{gathered} U_i=U_i^{?}+U_i^{+}=U_i{1}_{|U_i|\le R}+U_i{1}_{|U_i|>R} \\ {V}_j=V_j^{?}+V_j^{+}=V_j{1}_{|V_j|\le R}+V_j{1}_{|V_j|>R} \end{gathered}$$

顯然$U_i^{?},V_j^{?}$都是有界的，考慮
$${\Vert U_i^{+}\Vert }_2^2\le 2(R+\frac{1}{R})\frac{1}{\sqrt{2\pi }}{e}^{?R^2/2}\le \frac{4}{R^2}$$

同樣的
$${\Vert V_j^{+}\Vert }_2^2\le \frac{4}{R^2}$$

---

第四步，計(jì)算
$$\begin{gathered} K(A)=E\sum _{i,j}{A}_{ij}{U}_i{V}_j=E\sum _{i,j}{A}_{ij}(U_i^{?}+U_i^{+})(V_j^{?}+V_j^{+}) \\ =\sum _{i,j}{A}_{ij}E{U}_i^{?}{V}_j^{?}+\sum _{i,j}{A}_{ij}E{U}_i^{?}{V}_j^{+}+\sum _{i,j}{A}_{ij}E{U}_i^{+}{V}_j^{?}+\sum _{i,j}{A}_{ij}E{U}_i^{+}{V}_j^{+} \end{gathered}$$

先分析一下第三項(xiàng)，根據(jù)Cauchy-Schwarz不等式
$$\begin{gathered} \sum _{i,j}{A}_{ij}E{U}_i^{+}{V}_j^{?}\le \sum _{i,j}{A}_{ij}{\Vert U_i^{+}\Vert }_2{\Vert V_j^{?}\Vert }_2 \\ \le K(A)\max {\Vert U_i^{+}\Vert }_2\max {\Vert V_j^{?}\Vert }_2\le \frac{2K(A)}{R} \end{gathered}$$

第二項(xiàng)與之類似，所以
$$K(A)\le R^2+\frac{6K(A)}{R}$$

注意到這時(shí)的$K(A)$就和$A$沒(méi)有關(guān)系了，于是我們記為$K$，考慮$R$的不同取值，我們可以得到$K$的不同的上界。

總結(jié)

以上是生活随笔為你收集整理的UA MATH567 高维统计II 随机向量7 Grothendieck不等式的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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