随机矩阵正交性证明

重写一下证明思路。

先前写过一篇关于随机向量与随机矩阵的文章浅谈随机向量与随机矩阵，在证明随机矩阵的正交性时说得不是很清楚，这里重写一下该思路。

正交矩阵

正交矩阵（Orthogonal matrix）定义为，

$$A^{\top}A = AA^{\top} = I$$

其中$I$​是单位矩阵。单位矩阵本身也是正交矩阵。根据定义，有

$$A^{\top} = A^{-1}$$

正交矩阵的转置等于其逆。正交矩阵$A$与向量$x$的乘积$Ax$​的意义是对向量的旋转变换，例如二维空间的逆时针旋转矩阵

$$\mathcal {R}_{x} = \left[\begin{array}{cc}{\cos \theta} & {-\sin \theta} \\ {\sin \theta} & {\cos \theta}\end{array}\right]$$

三维空间中绕$x$轴旋转，

$$\displaystyle \mathcal {R}_{x}(\theta _{x})= \begin{bmatrix} 1&0&0\\0&\cos {\theta _{x}}&-\sin {\theta _{x}}\\ 0&\sin {\theta _{x}}&\cos {\theta _{x}} \end{bmatrix}$$

随机矩阵正交性证明

对于矩阵$W \in R^{m \times n}, m \ge n$​，满足，

$$W^{\top} W = I \in R^{n \times n}$$

则矩阵是正交矩阵。这里$I \in R^{n \times n}$​是单位矩阵，即对角线元素为$1$​，其他为$0$​。假设$W$​中的每个元素$w_{ij}$​独立采样自正态分布，

$$w_{ij} \sim N(0, \frac{1}{m})$$

或者采样自均匀分布，

$$w_{ij} \sim U[-\sqrt{\frac{3}{m}}, \sqrt{\frac{3}{m}}]$$

构造这样的分布是为满足均值为，

$$\mu = \operatorname{E}\big[w_{ij} \big] = 0$$

方差为，

$$\sigma^2 = \operatorname{Var}(w_{ij}) = \frac{(b-a)^2}{12} = \frac{1}{m}$$

那么满足这样采样的矩阵$W$，满足，

$$A = W^{\top}W \approx I$$

这里用矩阵$A$来表示$W^{\top}W$。为此，只需要证明两点：

• 矩阵$A$的对角线元素接近$1$​
• 矩阵$A$的非对角线元素接近$0$

根据矩阵的乘积，每个元素的取值为，

$$\begin{align} a_{ij} &= (W^{\top}W)_{[i,j]} \newline &= \sum_{k=1}^{m}w_{ki}w_{kj} \end{align}$$

对于非对角线元素，$i \ne j$，有

$$\begin{align} \sum_{k=1}^{m}w_{ki}w_{kj} &= m \times \frac{1}{m} \sum_{k=1}^{m}w_{ki}w_{kj} \newline &\approx m \times E_{w_{ki} \sim p(x), w_{kj} \sim p(y)} \big[ w_{ki}w_{kj} \big] \newline &= m \times E_{w_{ki} \sim p(x)} \big[ w_{ki}\big] \times E_{w_{kj} \sim p(y)} \big[ w_{kj}\big] \newline &= 0 \end{align}$$

也就是说，非对角线的元素几乎接近$0$。这也说明$m$维空间中两个随机向量正交的概率非常大，

$$\boldsymbol{u} \cdot \boldsymbol{v} = \sum_{i=1}^{n} u_{i} \times v_{i} \underset{p}{ \to } 0$$

对于对角线元素，$i = j$，有

$$\begin{align} \sum_{k=1}^{m}w_{ki}w_{kj} &= \sum_{k=1}^{m} w_{k}^2 \newline &= m \times \frac{1}{m} \sum_{k=1}^{m} w_{k}^2 \newline &\approx m \times E_{w_{k} \sim p(x)}\big[w_{k}^2 \big] \newline &= m \times E_{w_{k} \sim p(x)}\big[(w_{k}-\mu + \mu)^2 \big] \newline &= m \times \sigma^2 \newline &= m \times (\frac{1}{\sqrt{m}})^2 \newline &= 1 \end{align}$$

也就是说，对角线的元素几乎接近$1$​​。于是证明了，

$$A = W^{\top}W \approx I$$

事实上，以上过程是在计算如下矩阵，

$$\operatorname {R} _{\mathbf {X} \mathbf {X} }= {\begin{bmatrix} \operatorname {E} [X_{1}X_{1}]&\;\operatorname {E} [X_{1}X_{2}]&\;\cdots &\;\operatorname {E} [X_{1}X_{n}]\\\\\operatorname {E} [X_{2}X_{1}]&\;\operatorname {E} [X_{2}X_{2}]&\;\cdots &\;\operatorname {E} [X_{2}X_{n}]\\\\\vdots &\;\vdots &\;\ddots &\;\vdots \\\\\operatorname {E} [X_{n}X_{1}]&\;\operatorname {E} [X_{n}X_{2}]&\;\cdots &\;\operatorname {E} [X_{n}X_{n}]\\ \end{bmatrix}}$$

这个矩阵称为随机向量$\boldsymbol{X}$的自相关矩阵，其中，

$$\operatorname {E} [X_{i}X_{j}] = \frac{1}{m} \sum_{k=1}^{m}w_{ki}w_{kj},\\ i=1, \dots, n,\;j=1, \dots, n$$

以上推导可以发现，样本$w_{ij}$可以是任意分布$p(x)$，其均值0，方差为$\frac{1}{m}$​的随机向量也成立。这样获得的正交矩阵具有如下性质。

假设，随机投影矩阵$R$满足正交，

$$R \times R^{\top} = I$$

对于矩阵$E$有，

$$\begin{align} E \times E^{\top} &\approx (E\times R) \times (E\times R)^{\top} \\ &= E \times (R \times R^{\top}) \times E^{\top} \end{align}$$

正交变换保持模长不变。

这意味着，从统计角度看，我们给自己贴的标签越多，越找不到与我们相似的人。

编程实现

Python实现如下，

import numpy as np
import matplotlib.pyplot as plt

# 随机矩阵正交-正态分布
n = 100
m = 200 # m > n， 特例 m = n
W = np.random.normal(loc=0, scale=np.sqrt(1/m), size=(m, n))
R = np.dot(W.T, W)
plt.imshow(R)
plt.colorbar()
plt.show()
print(np.square(R - np.eye(n)).mean()) # 0.004896745915966785

# 随机矩阵正交-均匀分布
n = 100
m = 200 # m > n， 特例 m = n
a = np.sqrt(3/m)
W = np.random.uniform(-a, a, size=(m, n))
R = np.dot(W.T, W)
plt.imshow(R)
plt.colorbar()
plt.show()
print(np.square(R - np.eye(n)).mean()) # 0.004967685705694977

实验中的MSE误差均很小。

采样元素为正态分布情况，

采样元素为均匀分布情况，

总结

满足一定采样条件的随机矩阵居然是近似正交矩阵，这一点很违背直觉，因为转置等于逆$A^{\top} = A^{-1}$的性质太难满足了，但是数学和编程实验也证明这一点。

转载请包括本文地址：https://allenwind.github.io/blog/11416
更多文章请参考：https://allenwind.github.io/blog/archives/