随机化奇异值分解

$A\mathrm{\Omega }$ 的每一列都是 $A$ 各列的一个随机线性组合。若某些左奇异方向的伸缩量较大，它们往往也在这些组合中较明显。收集 $k+p$ 个组合而非仅 $k$ 个，为目标子空间提供额外余量；正交化随后去掉尺度和重复方向，让 $Q$ 只表达子空间本身。

一旦固定 $Q$，大矩阵中能由该空间解释的全部信息就是 $B=Q^{\mathsf{T}}A$。SVD 在较小的坐标系统中挑选最有价值的 $k$ 个方向，再用 $Q$ 搬回原来的输出空间。这个截断步骤对固定空间是最优的；若采样空间本身遗漏了重要方向，后续 SVD 无法补回。

图中的数值来自下面的固定算例。它把“找空间”与“空间内截断”分开，同时保留两层误差的实际大小；箭头不表示每次随机抽样都会取得这些数值。

一个可完整复算的五阶例子 ​

取标准基 $e_1,\dots ,e_5$，设

并指定以下便于算术的采样矩阵：

这是确定性演示，不是用于验证高斯抽样表现的试验。直接相乘得到

四列两两正交，故 $r=4$。第二遍压缩得到

$B$ 的行也两两正交，所以 $B{B}^{\mathsf{T}}=\mathrm{diag}(1025/68,9,4,1)$。其降序奇异值为 $\sqrt{1025/68},3,2,1$；可取 $\tilde{U}=I_4$，对应右奇异向量依次为

保留前两项便得到完整的秩二近似

采样空间的正交补由单位向量 $w=(-e_1+4e_5)/\sqrt{17}$ 张成。因此 $I-P=w{w}^{\mathsf{T}}$，并且

空间内部再丢掉奇异值 $2,1$，损失 $2^2+1^2=5$。两项相加给出

直接从矩阵 $A-{\hat{A}}_2$ 求平方和也得到同一结果。全空间内的最佳秩二近似则是 $A_2=\mathrm{diag}(4,3,0,0,0)$，误差平方为 $2^2+1^2+(1/2{)}^2=21/4=5.25$。差距来自把 $e_1$ 与 $e_5$ 混成了 $q$：$Q$ 的列空间并不包含 $e_1$。而四秩近似 $QB$ 的误差平方仅为 $20/17$，不能把这个较小数字当作最终秩二误差。

采样秩不足意味着什么 ​

对于任意给定的 $\mathrm{\Omega }$，$r<k$ 只说明样本不足以张成 $k$ 维空间，不说明 $A$ 的秩小于 $k$。例如 $A=I_3$、$k=2$、$p=0$，指定 $\mathrm{\Omega }=(e_1,e_1)$，则 $r=1$，输出 $e_1{e}_1^{\mathsf{T}}$，仍遗漏两个方向。准确重构至少要求 $\mathrm{col}(A)\subseteq \mathrm{col}(Q)$，最终秩截断还要求 $\mathrm{rank}A\le k$。

独立高斯抽样额外保证 $\mathrm{rank}(A\mathrm{\Omega })=min(\mathrm{rank}A,\ell )$ 几乎处处成立：在 $A$ 的非零右奇异子空间中，投影后的高斯矩阵仍为独立标准高斯矩阵，而其适当最大阶子式是非零多项式，取零的概率为零。因此若 $\mathrm{rank}A\le k$，基本算法在精确算术下几乎必然重构 $A$。浮点中的数值秩由容差决定，这一精确秩结论不会自动决定该容差。

为什么两种误差平方可以相加 ​

对任意 $C\in {\mathbb{R}}^{r\times n}$，写成

左边第一项的每一列都在 $\mathrm{col}(Q)$ 的正交补中，第二项每一列都在该空间中。更明确地，其 Frobenius 内积为

因为 $(I-P)Q=0$。又由 $Q^{\mathsf{T}}Q=I_r$，有 $\Vert Q(B-C){\Vert }_F=\Vert B-C{\Vert }_F$，故

第一项与 $C$ 无关。截断 SVD 的最佳低秩逼近定理说明，秩至多为 $k$ 的 $C$ 中，$B_k$ 使第二项最小，值为 $\sum _{j>k}{\sigma }_j(B{)}^2$。因此既得到了前述恒等式，也证明了 $Q{B}_k$ 在所有列空间包含于 $\mathrm{col}(Q)$、秩至多为 $k$ 的矩阵中最优：每个这样的矩阵 $X$ 都有 $X=QC$、$C=Q^{\mathsf{T}}X$，且 $\mathrm{rank}C=\mathrm{rank}X$。这一限制空间内的最优性，并不声称它等于全空间最佳近似 $A_k$。

高斯抽样的期望保证 ​

令全空间最优误差为 ${\tau }_k=(\sum _{j>k}{\sigma }_j(A{)}^2{)}^{1/2}$。Halko–Martinsson–Tropp 的 Theorem 10.5 对固定实矩阵、$k\ge 2$、$p\ge 2$、$k+p\le min(m,n)$ 及独立标准高斯 $\mathrm{\Omega }$ 给出投影误差的期望公理库期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分，概括加权平均与总体质量平衡。界

该定理证明中的平方误差估计还给出

后一个式子不能由前一个式子简单平方推出；它来自论文 Theorem 9.1 的确定性界和 Propositions 10.1–10.2 对高斯矩阵及其伪逆的二阶矩估计。这里引用这一概率分析，下面单独推导最终秩 $k$ 输出的保证。

由于 $Q^{\mathsf{T}}{A}_k$ 的秩至多为 $k$，可将它作为 $B$ 的低秩候选。利用截断最优性及正交投影不增范数，得到

将此代入确定性的平方和分解，再对随机样本取期望，便得到本页推导的保守估计

最后一步使用 $\mathbb{E}Z\le \sqrt{\mathbb{E}{Z}^2}$。这两个式子针对最终截断，与 Theorem 10.5 针对投影的常数不同。期望描述重复抽样的平均表现，不保证某一次输出满足同一个上界；需要逐次判断时，应计算或估计该次残差，并明确诊断的精度。

计算成本与使用条件 ​

对稠密矩阵，两次矩阵乘法分别形成 $A\mathrm{\Omega }$ 和 $Q^{\mathsf{T}}A$，每次成本为 $O(mn\ell )$；正交化、小矩阵 SVD 和提升左因子合计为 $O((m+n){\ell }^2)$。总成本为 $O(mn\ell +(m+n){\ell }^2)$，当 $\ell \ll min(m,n)$ 时才体现低秩计算的优势。$Q$ 和 $B$ 需要 $O((m+n)\ell )$ 存储；显式形成输出矩阵另需 $O(mn)$ 存储。

这一版本必须能第二次访问 $A$。只允许单遍读取时，无法直接沿用 $B=Q^{\mathsf{T}}A$ 这一步；结构化随机变换、单遍算法各有自己的误差分析。奇异值衰减慢时，可考虑交替乘 $A,A^{\mathsf{T}}$ 并在中间正交化的子空间迭代，但这里的成本与定理均针对上述基本算法。

有限精度实现应使用稳定的正交化，检查 $\Vert Q^{\mathsf{T}}Q-I\Vert$，并核对重构残差。精确算术中可由 $\Vert A{\Vert }_F^2-\sum _{j\le k}{\sigma }_j(B{)}^2$ 计算最终误差平方；当误差很小时，两个接近的数相减可能损失有效位数，应改为直接计算残差或采用另有误差控制的估计。小残差和重复抽样的一致性是有用诊断，严格的单次证书则还需相应数值误差界。