UA MATH567 高维统计II 随机向量7 Grothendieck不等式

UA MATH567 高维统计II 随机向量7 Grothendieck不等式

上一讲我们介绍了用半正定规划近似一个整数规划的方法，要证明这种近似与原整数规划解的大小关系，我们需要Grothendieck不等式，所以这一讲我们证明这个不等式：

Grothendieck不等式
$A$是$m\times n$的实矩阵，$x_i,y_j\in \{-1,1\}$，假设$|{\sum }_{i,j}{A}_{ij}{x}_i{y}_j|\le 1$，则$\forall H$(Hilbert space)，$\forall 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$$

证明
首先我们分析一下这个不等式的条件，$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|$$

如果$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$是一个线性函数，它的最优解一定是角点解，所以$x_i,y_j\in \{-1,1\}$，$|{\sum }_{i,j}{A}_{ij}{x}_i{y}_j|\le 1$；

与之类似，我们可以分析一下结论，$\forall H$(Hilbert space)，$\forall 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$$

等价于$\forall H$(Hilbert space)，$\forall 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 (先证明一个更弱的结果，即$K$与$A$相关)

引入$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}|$$

假设$\{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\sim N(0,I_N)$，$N=n+m$，定义$U_i=⟨g,u_i⟩,V_j=⟨g,v_j⟩$，则$U_i,V_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}$$

---

第四步，计算
$$\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}$$

先分析一下第三项，根据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}$$

第二项与之类似，所以
$$K(A)\le R^2+\frac{6K(A)}{R}$$

注意到这时的$K(A)$就和$A$没有关系了，于是我们记为$K$，考虑$R$的不同取值，我们可以得到$K$的不同的上界。

总结

以上是生活随笔为你收集整理的UA MATH567 高维统计II 随机向量7 Grothendieck不等式的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。