在观看Prof. Gilbert Strang的MIT18.065时（Matrix Methods in Data Analysis, Signal Processing, and Machine Learning | Mathematics | MIT OpenCourseWare）的lecture13时，对于随机矩阵的方差理解出现了疑惑，特此补充证明，以作为记录。
在证明通过范数平方作为采样概率的情况下，估计乘积值结果的方差（估计值与理论值的偏差程度）最小时，使用了一个数作为了估计的方差，这与视频开头时的方差是一个矩阵产生了冲突，使人感到困惑。因此查阅了部分资料并补充说明。
第一点需要声明的是，在后续推导计算中，随机矩阵的均值还是矩阵，随机矩阵的方差是随机矩阵F-范数的方差，即$E\left( CR \right)=AB$，$Var\left( CR \right)=E\left[ \left\| CR-AB \right\|_{F}^{2} \right]$，这样定义的方差$Var\left( CR \right)$与方差仍是矩阵的计算（$Va{{r}_{matrix}}\left( CR \right)=\sum\limits_{k=1}^{n}{{{p}_{k}}{{\left( CR-AB \right)}^{2}}}$），即视频开头展示的1*2的矩阵的例子是相容的。
在进行进一步的理解和理论推导时，需要阐述清楚\[Va{{r}_{matrix}}\left( CR \right)=\sum\limits_{k=1}^{n}{{{p}_{k}}{{\left( CR-AB \right)}^{2}}}\]中的运算${{\left( \bullet \right)}^{2}}$，其中$\bullet $是任意一个矩阵。这里的${{\left( \bullet \right)}^{2}}$并不是矩阵与矩阵相乘，而是每个矩阵元素对应相乘，也就是MATLAB中的.*运算[1]。这样的做法一来可以与[2]的P.148的公式(3)相对应；二来将每个元素平方，这和F-范数的计算联系起来，可以与之后F-范数的定义相一致。
那么就一步步的尝试解释，以1次实验为例，$s$次实验就是将一次抽样的均值方差结果乘以$s$（$s$次独立同分布的结果）：
- 均值：如果有$E\left( CR \right)=\frac{1}{s}AB$，显然有$E\left( C{{R}_{ij}} \right)=\frac{1}{s}AB{_{ij}}$，也就是说如果矩阵CR的均值是AB矩阵，那么有矩阵CR的每一个元素均值是AB矩阵对应元素。
- $Va{{r}_{matrix}}\left( CR \right)$和$Var\left( CR \right)$的关系：
$Va{{r}_{matrix}}\left( CR \right)$得到的是一个矩阵，将$Va{{r}_{matrix}}\left( CR \right)$各个元素加起来，得到的就是$Var\left( CR \right)=E\left[ \left\| CR-\frac{1}{s}AB \right\|_{F}^{2} \right]$。这里可以通过公式推导。\[Va{{r}_{matrix}}\left( CR \right)=\sum\limits_{k=1}^{n}{{{p}_{k}}{{\left( CR-\frac{1}{s}AB \right)}^{2}}}\\=\left[ \begin{matrix}
\sum\limits_{k=1}^{r}{{{p}_{k}}{{\left( C{{R}_{11}}-\frac{1}{s}A{{B}_{11}} \right)}^{2}}} & \sum\limits_{k=1}^{r}{{{p}_{k}}{{\left( C{{R}_{12}}-\frac{1}{s}A{{B}_{12}} \right)}^{2}}} & \cdots & \sum\limits_{k=1}^{r}{{{p}_{k}}{{\left( C{{R}_{1n}}-\frac{1}{s}A{{B}_{1n}} \right)}^{2}}} \\
\sum\limits_{k=1}^{r}{{{p}_{k}}{{\left( C{{R}_{21}}-\frac{1}{s}A{{B}_{21}} \right)}^{2}}} & \sum\limits_{k=1}^{r}{{{p}_{k}}{{\left( C{{R}_{22}}-\frac{1}{s}A{{B}_{22}} \right)}^{2}}} & \cdots & \sum\limits_{k=1}^{r}{{{p}_{k}}{{\left( C{{R}_{2n}}-\frac{1}{s}A{{B}_{2n}} \right)}^{2}}} \\
\vdots & \vdots & \ddots & \vdots \\
\sum\limits_{k=1}^{r}{{{p}_{k}}{{\left( C{{R}_{m1}}-\frac{1}{s}A{{B}_{m1}} \right)}^{2}}} & \sum\limits_{k=1}^{r}{{{p}_{k}}{{\left( C{{R}_{m2}}-\frac{1}{s}A{{B}_{m2}} \right)}^{2}}} & \cdots & \sum\limits_{k=1}^{r}{{{p}_{k}}{{\left( C{{R}_{mn}}-\frac{1}{s}A{{B}_{mn}} \right)}^{2}}} \\
\end{matrix} \right]\]
其中需要注意的是，$A$矩阵是$m\times r$的尺寸，$B$矩阵是$r\times n$的尺寸，并且考虑的是$CR$是一次抽样的情况，也就是$CR=\frac{1}{s{{p}_{i}}}{{\mathbf{a}}_{k}}\mathbf{b}_{k}^{T}$，以${{p}_{k}}$的概率抽样得到，这样也保证了$E\left( CR \right)=\frac{1}{s}AB$（此处作为背景知识，不再证明）。
那么$Va{{r}_{matrix}}\left( CR \right)$各个元素非负，将所有元素加起来即得到\[\sum\limits_{i,j}^{m,n}{\sum\limits_{k=1}^{r}{{{p}_{k}}{{\left( C{{R}_{ij}}-\frac{1}{s}A{{B}_{ij}} \right)}^{2}}}}\]
另一方面，我们去处理\[Var\left( CR \right)=E\left[ \left\| CR-\frac{1}{s}AB \right\|_{F}^{2} \right]\\=E\left[ \left\| \begin{matrix}
C{{R}_{11}}-\frac{1}{s}A{{B}_{11}} & C{{R}_{12}}-\frac{1}{s}A{{B}_{12}} & \cdots & C{{R}_{1n}}-\frac{1}{s}A{{B}_{1n}} \\
C{{R}_{21}}-\frac{1}{s}A{{B}_{21}} & C{{R}_{22}}-\frac{1}{s}A{{B}_{22}} & \cdots & C{{R}_{2n}}-\frac{1}{s}A{{B}_{2n}} \\
\vdots & \vdots & \ddots & \vdots \\
C{{R}_{m1}}-\frac{1}{s}A{{B}_{m1}} & C{{R}_{m2}}-\frac{1}{s}A{{B}_{m2}} & \cdots & C{{R}_{mn}}-\frac{1}{s}A{{B}_{mn}} \\
\end{matrix} \right\|_{F}^{2} \right]\\=E\left[ \sum\limits_{i,j}^{m,n}{{{\left( C{{R}_{ij}}-\frac{1}{s}A{{B}_{ij}} \right)}^{2}}} \right]=\sum\limits_{k=1}^{r}{{{p}_{k}}\sum\limits_{i,j}^{m,n}{{{\left( C{{R}_{ij}}-\frac{1}{s}A{{B}_{ij}} \right)}^{2}}}}\\=\sum\limits_{k=1}^{r}{\sum\limits_{i,j}^{m,n}{{{p}_{k}}}{{\left( C{{R}_{ij}}-\frac{1}{s}A{{B}_{ij}} \right)}^{2}}}\]
可见二者相等，从而验证$Va{{r}_{matrix}}\left( CR \right)$和$Var\left( CR \right)$的关系。 - 那么按照$Var\left( CR \right)=E\left[ \left\| CR-\frac{1}{s}AB \right\|_{F}^{2} \right]$，我们开始计算方差:\[Var\left( CR \right)=E\left[ \left\| CR-\frac{1}{s}AB \right\|_{F}^{2} \right]=E\left[ \sum\limits_{i,j}^{m,n}{{{\left( C{{R}_{ij}}-\frac{1}{s}A{{B}_{ij}} \right)}^{2}}} \right]=\sum\limits_{i,j}^{m,n}{E\left( {{\left( C{{R}_{ij}}-\frac{1}{s}A{{B}_{ij}} \right)}^{2}} \right)}\]
其中$C{{R}_{ij}}-\frac{1}{s}A{{B}_{ij}}$是一个数，并且有$E\left( C{{R}_{ij}} \right)=\frac{1}{s}AB{_{ij}}$，所以有\[E\left( {{\left( C{{R}_{ij}}-\frac{1}{s}A{{B}_{ij}} \right)}^{2}} \right)=Var\left( C{{R}_{ij}} \right)\]
根据随机变量（实数而非矩阵）的公式，有$Var\left( X \right)=E\left( {{X}^{2}} \right)-{{\left( EX \right)}^{2}}$，那么\[\begin{align}
& Var\left( CR \right)=\sum\limits_{i,j}^{m,n}{E\left( {{\left( C{{R}_{ij}}-\frac{1}{s}A{{B}_{ij}} \right)}^{2}} \right)}\\ & =\sum\limits_{i,j}^{m,n}{\left[ E\left( CR_{ij}^{2} \right)-{{\left( E\left( C{{R}_{ij}} \right) \right)}^{2}} \right]} \\ & = \sum\limits_{i,j}^{m,n}{\left[ E\left( CR_{ij}^{2} \right)-\frac{1}{{{s}^{2}}}{{\left( A{{B}_{ij}} \right)}^{2}} \right]} \\
& =\sum\limits_{i,j}^{m,n}{\left( E\left( CR_{ij}^{2} \right) \right)}-\frac{1}{{{s}^{2}}}\sum\limits_{i,j}^{m,n}{{{\left( A{{B}_{ij}} \right)}^{2}}}\\ & =\sum\limits_{i,j}^{m,n}{\left( E\left( CR_{ij}^{2} \right) \right)}-\frac{1}{{{s}^{2}}}\left\| AB \right\|_{F}^{2} \\
\end{align}\]
那么现在就要处理\[\sum\limits_{i,j}^{m,n}{\left( E\left( CR_{ij}^{2} \right) \right)}=E\left( \sum\limits_{i,j}^{m,n}{CR_{ij}^{2}} \right)=E\left( \left\| CR \right\|_{F}^{2} \right)\]
要注意的是，在一次采样中，$CR$以${{p}_{k}}$的概率取得$CR={{\mathbf{a}}_{k}}\mathbf{b}_{k}^{T}$，是一个秩为1的矩阵，也就是说奇异值只有一个不为0。 - 现在，我进行了第二个声明，对于$CR={{\mathbf{a}}_{k}}\mathbf{b}_{k}^{T}$，有$\left\| CR \right\|_{F}^{2}={{\left\| {{a}_{k}} \right\|}^{2}}{{\left\| b_{k}^{T} \right\|}^{2}}$。
这是因为，在奇异值分解中，有如下的形式$A=U\Sigma {{V}^{T}}={{\sigma }_{1}}{{u}_{1}}v_{1}^{T}+{{\sigma }_{2}}{{u}_{2}}v_{2}^{T}+\cdots $。而\[CR=\frac{{{\mathbf{a}}_{k}}}{\left\| {{\mathbf{a}}_{k}} \right\|}\left\| {{\mathbf{a}}_{k}} \right\|\left\| \mathbf{b}_{k}^{T} \right\|\frac{\mathbf{b}_{k}^{T}}{\left\| \mathbf{b}_{k}^{T} \right\|}\]
恰好是只有一个奇异值的矩阵的SVD分解形式，我们可知，$CR$的奇异值是$\left\| {{\mathbf{a}}_{k}} \right\|\left\| \mathbf{b}_{k}^{T} \right\|$和一堆0。
而我们又知道，矩阵的F-范数的平方又等于奇异值的平方和，即$\left\| A \right\|_{F}^{2}=\sigma _{1}^{2}+\sigma _{2}^{2}+\cdots $，所以$\left\| CR \right\|_{F}^{2}={{\left\| {{a}_{k}} \right\|}^{2}}{{\left\| b_{k}^{T} \right\|}^{2}}+{{0}^{2}}+{{0}^{2}}={{\left\| {{a}_{k}} \right\|}^{2}}{{\left\| b_{k}^{T} \right\|}^{2}}$，我的声明得到了证明。
继而回到主线的证明中，$CR=\frac{1}{s{{p}_{k}}}{{\mathbf{a}}_{k}}\mathbf{b}_{k}^{T}$，那么$\left\| CR \right\|_{F}^{2}=\frac{1}{{{s}^{2}}p_{k}^{2}}{{\left\| {{a}_{k}} \right\|}^{2}}{{\left\| b_{k}^{T} \right\|}^{2}}$，这是由平方和范数的线性性质得到的。
继续回到
$$\begin{align}
& Var\left( CR \right)=\sum\limits_{i,j}^{m,n}{\left( E\left( CR_{ij}^{2} \right) \right)}-\frac{1}{{{s}^{2}}}\left\| AB \right\|_{F}^{2} \\ & =E\left( \left\| CR \right\|_{F}^{2} \right)-\frac{1}{{{s}^{2}}}\left\| AB \right\|_{F}^{2} \\ & =E\left( \frac{1}{{{s}^{2}}p_{k}^{2}}{{\left\| {{a}_{k}} \right\|}^{2}}{{\left\| b_{k}^{T} \right\|}^{2}} \right)-\frac{1}{{{s}^{2}}}\left\| AB \right\|_{F}^{2}\\ & =\sum\limits_{k=1}^{r}{{{p}_{k}}\frac{1}{{{s}^{2}}p_{k}^{2}}{{\left\| {{a}_{k}} \right\|}^{2}}{{\left\| b_{k}^{T} \right\|}^{2}}}-\frac{1}{{{s}^{2}}}\left\| AB \right\|_{F}^{2} \\
& =\sum\limits_{k=1}^{r}{\frac{1}{{{s}^{2}}{{p}_{k}}}{{\left\| {{a}_{k}} \right\|}^{2}}{{\left\| b_{k}^{T} \right\|}^{2}}}-\frac{1}{{{s}^{2}}}\left\| AB \right\|_{F}^{2} \\
\end{align}$$
这是1次实验的方差，n次独立同分布的方差要乘以n，也就得到了式(6)，为之后的证明铺平了道路。
[1] C = A .* B multiplies arrays A and B by multiplying corresponding elements. 来源： times
[2] Strang, G. (2019). Linear algebra and learning from data (Vol. 4). Cambridge: Wellesley-Cambridge Press. Linear Algebra and Learning from Data
[3] MIT 18.065—机器学习中的矩阵方法13 随机矩阵乘法 - 知乎