上一篇 我们看到 PCA 的核心计算就是 SVD——对中心化数据矩阵 X ~ = U Σ V T \tilde{X} = U\Sigma V^T X ~ = U Σ V T k k k
精确 SVD 的代价 ：对一个 m × n m \times n m × n O ( m n min ( m , n ) ) O(mn\min(m,n)) O ( mn min ( m , n )) 480,000 × 17,000 480{,}000 \times 17{,}000 480 , 000 × 17 , 000 480,000 × 17,000 × 17,000 ≈ 1.4 × 10 14 480{,}000 \times 17{,}000 \times 17{,}000 \approx 1.4 \times 10^{14} 480 , 000 × 17 , 000 × 17 , 000 ≈ 1.4 × 1 0 14 k k k
核心思想 ：既然我们只要前 k k k 随机投影 将矩阵压缩到一个远小于原始维度的子空间，然后在这个小子空间里做精确 SVD？只要随机投影足够好——即它大致保持了矩阵的”重要方向”——最终结果就接近精确的截断 SVD。
这就是随机化 SVD （Randomized SVD）的思想。它的理论基础是一个看似违反直觉但异常深刻的结论：随机投影几乎保持距离 ——Johnson-Lindenstrauss 引理。
Johnson-Lindenstrauss 引理
直觉
JL 引理：随机投影几乎保持所有距离 原始空间 ℝᵈ (d 可能很大) d₁₂ f(x) = Ωx/√k Ω: 随机高斯矩阵 投影空间 ℝᵏ (k ≥ 8 ln N / ε²) d'₁₂ (1−ε)‖xᵢ−xⱼ‖² ≤ ‖f(xᵢ)−f(xⱼ)‖² ≤ (1+ε)‖xᵢ−xⱼ‖² 想象你有 N N N R d \mathbb{R}^d R d d d d k = 50 k = 50 k = 50
但 Johnson-Lindenstrauss（JL）引理告诉我们一个惊人的事实：只要目标维度 k k k ln N \ln N ln N 随机 线性投影就能同时保持所有点对之间的距离 ，失真不超过 ε \varepsilon ε
注意这里的关键词：
随机 ：不需要精心设计投影矩阵，随机高斯矩阵就够了同时 ：不是保持某一对点的距离，而是所有 ( N 2 ) \binom{N}{2} ( 2 N ) 与 d d d ：目标维度只取决于点数 N N N ε \varepsilon ε d d d
严格陈述
引理 （Johnson & Lindenstrauss, 1984）：给定 0 < ε < 1 0 < \varepsilon < 1 0 < ε < 1 N N N x 1 , … , x N ∈ R d \mathbf{x}_1, \ldots, \mathbf{x}_N \in \mathbb{R}^d x 1 , … , x N ∈ R d
k ≥ 8 ln N ε 2 k \geq \frac{8\ln N}{\varepsilon^2} k ≥ ε 2 8 l n N
则随机线性映射 f ( x ) = 1 k Ω x f(\mathbf{x}) = \frac{1}{\sqrt{k}}\Omega\mathbf{x} f ( x ) = k 1 Ω x Ω ∈ R k × d \Omega \in \mathbb{R}^{k \times d} Ω ∈ R k × d N ( 0 , 1 ) \mathcal{N}(0, 1) N ( 0 , 1 ) 所有 1 ≤ i , j ≤ N 1 \leq i, j \leq N 1 ≤ i , j ≤ N ( N 2 ) \binom{N}{2} ( 2 N )
( 1 − ε ) ∥ x i − x j ∥ 2 ≤ ∥ f ( x i ) − f ( x j ) ∥ 2 ≤ ( 1 + ε ) ∥ x i − x j ∥ 2 (1 - \varepsilon)\|\mathbf{x}_i - \mathbf{x}_j\|^2 \leq \|f(\mathbf{x}_i) - f(\mathbf{x}_j)\|^2 \leq (1 + \varepsilon)\|\mathbf{x}_i - \mathbf{x}_j\|^2 ( 1 − ε ) ∥ x i − x j ∥ 2 ≤ ∥ f ( x i ) − f ( x j ) ∥ 2 ≤ ( 1 + ε ) ∥ x i − x j ∥ 2
注意：经典陈述用”存在线性映射”，但证明是构造性 的——你不需要搜索这个映射，随机生成 Ω \Omega Ω
“随机投影”是什么？ 就是矩阵乘法 y = 1 k Ω x \mathbf{y} = \frac{1}{\sqrt{k}}\Omega\mathbf{x} y = k 1 Ω x x ∈ R d \mathbf{x} \in \mathbb{R}^d x ∈ R d y ∈ R k \mathbf{y} \in \mathbb{R}^k y ∈ R k k ≪ d k \ll d k ≪ d Ω \Omega Ω R d \mathbb{R}^d R d y i = 1 k ω i T x y_i = \frac{1}{\sqrt{k}}\boldsymbol{\omega}_i^T\mathbf{x} y i = k 1 ω i T x x \mathbf{x} x k k k k k k 1 / k 1/\sqrt{k} 1/ k ∥ y ∥ 2 \|\mathbf{y}\|^2 ∥ y ∥ 2 ∥ x ∥ 2 \|\mathbf{x}\|^2 ∥ x ∥ 2
逐项理解各参数：
ε \varepsilon ε ε = 0.1 \varepsilon = 0.1 ε = 0.1 N N N k k k ln N \ln N ln N ( N 2 ) < N 2 / 2 \binom{N}{2} < N^2/2 ( 2 N ) < N 2 /2 对数的 ：点数翻 10 10 10 k k k 8 ln 10 / ε 2 ≈ 18 / ε 2 8\ln 10 / \varepsilon^2 \approx 18/\varepsilon^2 8 ln 10/ ε 2 ≈ 18/ ε 2 k ≥ 8 ln N / ε 2 k \geq 8\ln N / \varepsilon^2 k ≥ 8 ln N / ε 2 d d d N = 1,000,000 N = 1{,}000{,}000 N = 1 , 000 , 000 ε = 0.1 \varepsilon = 0.1 ε = 0.1 k ≥ 8 × ln ( 10 6 ) / 0.01 ≈ 11,053 k \geq 8 \times \ln(10^6) / 0.01 \approx 11{,}053 k ≥ 8 × ln ( 1 0 6 ) /0.01 ≈ 11 , 053
1 / k 1/\sqrt{k} 1/ k ∥ Ω x ∥ 2 \|\Omega\mathbf{x}\|^2 ∥Ω x ∥ 2 k ∥ x ∥ 2 k\|\mathbf{x}\|^2 k ∥ x ∥ 2 k k k 相对 失真不受全局缩放影响（集中不等式控制的是 ∥ Ω x ∥ 2 / ( k ∥ x ∥ 2 ) \|\Omega\mathbf{x}\|^2/(k\|\mathbf{x}\|^2) ∥Ω x ∥ 2 / ( k ∥ x ∥ 2 ) 1 / k 1/\sqrt{k} 1/ k 绝对数值 上近似原始距离，就加上它。加 1 / k 1/\sqrt{k} 1/ k E [ ∥ f ( x ) ∥ 2 ] = ∥ x ∥ 2 \mathbb{E}[\|f(\mathbf{x})\|^2] = \|\mathbf{x}\|^2 E [ ∥ f ( x ) ∥ 2 ] = ∥ x ∥ 2
证明思路
完整证明超出本文范围，但核心思路值得一看。关键在于一个集中不等式 （concentration inequality）：
对单个向量 x \mathbf{x} x f ( x ) = 1 k Ω x f(\mathbf{x}) = \frac{1}{\sqrt{k}}\Omega\mathbf{x} f ( x ) = k 1 Ω x ∥ f ( x ) ∥ 2 \|f(\mathbf{x})\|^2 ∥ f ( x ) ∥ 2 k k k
Pr [ ∣ ∥ f ( x ) ∥ 2 − ∥ x ∥ 2 ∣ > ε ∥ x ∥ 2 ] ≤ 2 exp ( − k ε 2 8 ) \Pr\Big[\big|\|f(\mathbf{x})\|^2 - \|\mathbf{x}\|^2\big| > \varepsilon\|\mathbf{x}\|^2\Big] \leq 2\exp\!\Big(-\frac{k\varepsilon^2}{8}\Big) Pr [ ∥ f ( x ) ∥ 2 − ∥ x ∥ 2 > ε ∥ x ∥ 2 ] ≤ 2 exp ( − 8 k ε 2 )
将 x \mathbf{x} x x i − x j \mathbf{x}_i - \mathbf{x}_j x i − x j ( N 2 ) < N 2 / 2 \binom{N}{2} < N^2/2 ( 2 N ) < N 2 /2
Pr [ 存在某对距离失真超过 ε ] < N 2 exp ( − k ε 2 8 ) \Pr[\text{存在某对距离失真超过 } \varepsilon] < N^2 \exp\!\Big(-\frac{k\varepsilon^2}{8}\Big) Pr [ 存在某对距离失真超过 ε ] < N 2 exp ( − 8 k ε 2 )
令右边 < 1 < 1 < 1 k > 8 ln N / ε 2 k > 8\ln N / \varepsilon^2 k > 8 ln N / ε 2
深层含义 ：JL 引理的力量在于它的通用性 。不需要对数据做任何假设（无需低秩、无需稀疏、无需特殊分布），只要目标维度足够大，随机投影就能保持距离。这为随机化算法提供了坚实的理论基础。
可视化
用下面的交互组件亲手体验 JL 引理。我们生成 d = 50 d = 50 d = 50 k k k ( 1 ± ε ) (1 \pm \varepsilon) ( 1 ± ε )
试试：先用很小的 k k k k k k
Johnson-Lindenstrauss 引理：随机投影保持距离
高维点对 → 随机投影到低维 → 对比成对距离
0.0 3.5 6.9 10.4 13.9 17.4 0.0 3.5 6.9 10.4 13.9 17.4 原始距离（高维） 投影距离（低维） 理想保持线 y = x (1±ε) 容差带 (ε=0.3) 超出容差带 距离保持统计
原始维度 d: 50 投影维度 k k: 8 < 303 (JL 理论下界) 落入容差带的点对: 345/435 (79.3%) 最大失真: 63.6% 平均失真: 19.0%
从 JL 到随机化 SVD
JL 引理保证了随机投影保持距离。但随机化 SVD 需要更强的性质：随机投影不仅要保持距离，还要捕获矩阵的主要列空间 。这正是 Halko、Martinsson 和 Tropp（2011）在其里程碑论文中系统发展的理论。
关键洞察
设 A ∈ R m × n A \in \mathbb{R}^{m \times n} A ∈ R m × n A k = U k Σ k V k T A_k = U_k\Sigma_k V_k^T A k = U k Σ k V k T U k ∈ R m × k U_k \in \mathbb{R}^{m \times k} U k ∈ R m × k A A A k k k
目标 ：找到一个 m × k m \times k m × k Q Q Q Q Q Q U k U_k U k Q Q T QQ^T Q Q T Q Q Q A k = U k Σ k V k T = U k ( U k T A ) A_k = U_k\Sigma_kV_k^T = U_k(U_k^TA) A k = U k Σ k V k T = U k ( U k T A ) A A A U k U_k U k Q Q T A ≈ U k U k T A = A k QQ^TA \approx U_kU_k^TA = A_k Q Q T A ≈ U k U k T A = A k Q Q Q Q Q Q
随机投影的作用 ：取随机矩阵 Ω ∈ R n × ( k + p ) \Omega \in \mathbb{R}^{n \times (k+p)} Ω ∈ R n × ( k + p ) p p p
Y = A Ω ∈ R m × ( k + p ) Y = A\Omega \in \mathbb{R}^{m \times (k+p)} Y = A Ω ∈ R m × ( k + p )
每一列 Y j = A ω j Y_j = A\boldsymbol{\omega}_j Y j = A ω j A A A A A A k k k σ 1 ≥ ⋯ ≥ σ k \sigma_1 \geq \cdots \geq \sigma_k σ 1 ≥ ⋯ ≥ σ k σ k + 1 , … \sigma_{k+1}, \ldots σ k + 1 , … k k k Y Y Y
Halko-Martinsson-Tropp 算法
Halko-Martinsson-Tropp 算法：两阶段流水线
阶段 1：构建近似列空间 A m×n Ω n×(k+p) 随机 Y=AΩ m×(k+p) Q (QR) m×(k+p) × Q 阶段 2：小空间精确分解 B=QᵀA (k+p)×n SVD(B) 精确 SVD U=QÛ,Σ,Vᵀ 近似截断 SVD 总复杂度 O(mn(k+p))，远优于全 SVD O(mn·min(m,n)) 算法步骤
输入 ：矩阵 A ∈ R m × n A \in \mathbb{R}^{m \times n} A ∈ R m × n k k k p p p p = 5 p = 5 p = 5 10 10 10
阶段 1——构建近似列空间 ：
生成随机测试矩阵 Ω ∈ R n × ( k + p ) \Omega \in \mathbb{R}^{n \times (k+p)} Ω ∈ R n × ( k + p ) Ω i j ∼ N ( 0 , 1 ) \Omega_{ij} \sim \mathcal{N}(0,1) Ω ij ∼ N ( 0 , 1 )
计算采样矩阵 Y = A Ω ∈ R m × ( k + p ) Y = A\Omega \in \mathbb{R}^{m \times (k+p)} Y = A Ω ∈ R m × ( k + p )
对 Y Y Y Y = Q R Y = QR Y = QR Q ∈ R m × ( k + p ) Q \in \mathbb{R}^{m \times (k+p)} Q ∈ R m × ( k + p )
阶段 2——在小空间中精确分解 ：
4. 计算小矩阵 B = Q T A ∈ R ( k + p ) × n B = Q^T A \in \mathbb{R}^{(k+p) \times n} B = Q T A ∈ R ( k + p ) × n B B B B = U ^ Σ V T B = \hat{U}\Sigma V^T B = U ^ Σ V T U = Q U ^ U = Q\hat{U} U = Q U ^
输出 ：A ≈ U Σ V T A \approx U\Sigma V^T A ≈ U Σ V T k k k k k k
逐步解读
每一步在做什么？
步骤 1-2 （随机采样）：Y = A Ω Y = A\Omega Y = A Ω A A A k + p k+p k + p p p p p p p p = 5 ∼ 10 p = 5 \sim 10 p = 5 ∼ 10
步骤 3 （QR 分解）：将 Y Y Y Q Q Q Q Q Q Y Y Y
步骤 4 （换基降维）：B = Q T A B = Q^T A B = Q T A A A A Q Q Q 坐标 （( k + p ) × n (k+p) \times n ( k + p ) × n Q Q T A QQ^TA Q Q T A Q T A Q^TA Q T A Q Q Q
步骤 5-6 （精确 SVD + 恢复）：在小空间中做精确 SVD 代价很低。U = Q U ^ U = Q\hat{U} U = Q U ^
伪代码
function RandomizedSVD(A, k, p=5): n = cols(A) # 阶段 1: 构建近似列空间 Omega = randn(n, k+p) # 随机高斯矩阵 Y = A @ Omega # m × (k+p) Q, _ = qr(Y) # 正交化 # 阶段 2: 小空间精确 SVD B = Q.T @ A # (k+p) × n U_hat, Sigma, Vt = svd(B) # 精确 SVD U = Q @ U_hat # 恢复到原空间 # 截断到秩 k return U[:, :k], Sigma[:k], Vt[:k, :] 幂迭代加速
幂迭代：放大奇异值间距 原始 σᵢ σ₁ σ₂ σ₃ σ₄ σ₅ σ₆ 间距×1.3 1 次幂迭代 σᵢ³ σ₁ σ₂ σ₃ σ₄ σ₅ σ₆ 间距×2.1 2 次幂迭代 σᵢ⁵ σ₁ σ₂ σ₃ σ₄ σ₅ σ₆ 间距×3.3 幂迭代将 σₖ/σₖ₊₁ 的间距从 r 放大到 r²ᵠ⁺¹ —— 使随机采样更容易区分前 k 个方向
当奇异值衰减缓慢时（即 σ k \sigma_k σ k σ k + 1 \sigma_{k+1} σ k + 1 幂迭代 （power iteration）可以放大奇异值之间的差距。
思路：将步骤 2 中的 Y = A Ω Y = A\Omega Y = A Ω
Y = ( A A T ) q A Ω Y = (AA^T)^q A\Omega Y = ( A A T ) q A Ω
其中 q q q q = 1 q = 1 q = 1 2 2 2 A A A σ i \sigma_i σ i ( A A T ) q A (AA^T)^q A ( A A T ) q A σ i 2 q + 1 \sigma_i^{2q+1} σ i 2 q + 1 σ k / σ k + 1 = 1.1 \sigma_k / \sigma_{k+1} = 1.1 σ k / σ k + 1 = 1.1 ( 1.1 ) 3 ≈ 1.33 (1.1)^3 \approx 1.33 ( 1.1 ) 3 ≈ 1.33 ( 1.1 ) 5 ≈ 1.61 (1.1)^5 \approx 1.61 ( 1.1 ) 5 ≈ 1.61 k k k
复杂度分析
步骤 操作 复杂度 Y = A Ω Y = A\Omega Y = A Ω 矩阵乘法 O ( m n ( k + p ) ) O(mn(k+p)) O ( mn ( k + p )) Y = Q R Y = QR Y = QR QR 分解 O ( m ( k + p ) 2 ) O(m(k+p)^2) O ( m ( k + p ) 2 ) B = Q T A B = Q^TA B = Q T A 矩阵乘法 O ( m n ( k + p ) ) O(mn(k+p)) O ( mn ( k + p )) SVD of B B B 精确 SVD O ( ( k + p ) 2 n ) O((k+p)^2 n) O (( k + p ) 2 n ) U = Q U ^ U = Q\hat{U} U = Q U ^ 矩阵乘法 O ( m ( k + p ) 2 ) O(m(k+p)^2) O ( m ( k + p ) 2 )
总计 ：O ( m n ( k + p ) ) O(mn(k+p)) O ( mn ( k + p ))
与精确 SVD 对比 ：
精确全 SVD：O ( m n min ( m , n ) ) O(mn\min(m,n)) O ( mn min ( m , n ))
截断 SVD（Lanczos/ARPACK）：O ( m n k ) O(mnk) O ( mnk )
随机化 SVD：O ( m n ( k + p ) ) O(mn(k+p)) O ( mn ( k + p )) 一次 pass （计算 Y = A Ω Y = A\Omega Y = A Ω
对于 Netflix 矩阵（m = 480,000 m = 480{,}000 m = 480 , 000 n = 17,000 n = 17{,}000 n = 17 , 000 k = 50 k = 50 k = 50 p = 10 p = 10 p = 10
全 SVD：∼ 1.4 × 10 14 \sim 1.4 \times 10^{14} ∼ 1.4 × 1 0 14
随机化 SVD：∼ 480,000 × 17,000 × 60 ≈ 4.9 × 10 11 \sim 480{,}000 \times 17{,}000 \times 60 \approx 4.9 \times 10^{11} ∼ 480 , 000 × 17 , 000 × 60 ≈ 4.9 × 1 0 11
加速约 300 倍 ，且以极高概率给出几乎相同的前 50 个奇异值和奇异向量。
误差界
随机化 SVD 的理论保证来自 Halko et al.（2011, Theorem 10.5, 10.6）。
期望误差
设 A A A A k = U k Σ k V k T A_k = U_k\Sigma_k V_k^T A k = U k Σ k V k T Eckart-Young 最佳近似 ），则随机化 SVD 的输出 A ~ k \tilde{A}_k A ~ k
E ∥ A − A ~ k ∥ F ≤ ( 1 + k p − 1 ) 1 / 2 ⋅ ( ∑ j > k σ j 2 ) 1 / 2 \mathbb{E}\|A - \tilde{A}_k\|_F \leq \left(1 + \frac{k}{p-1}\right)^{1/2} \cdot \left(\sum_{j>k}\sigma_j^2\right)^{1/2} E ∥ A − A ~ k ∥ F ≤ ( 1 + p − 1 k ) 1/2 ⋅ ( ∑ j > k σ j 2 ) 1/2
逐项理解：
( ∑ j > k σ j 2 ) 1 / 2 = ∥ A − A k ∥ F \left(\sum_{j>k}\sigma_j^2\right)^{1/2} = \|A - A_k\|_F ( ∑ j > k σ j 2 ) 1/2 = ∥ A − A k ∥ F ( 1 + k / ( p − 1 ) ) 1 / 2 (1 + k/(p-1))^{1/2} ( 1 + k / ( p − 1 ) ) 1/2 p = k p = k p = k 2 \sqrt{2} 2 p = 5 ∼ 10 p = 5 \sim 10 p = 5 ∼ 10
Spectral 范数误差
对于谱范数（Art. 4 范数与条件数 中定义的 ∥ ⋅ ∥ 2 \|\cdot\|_2 ∥ ⋅ ∥ 2
E ∥ A − A ~ k ∥ 2 ≤ ( 1 + k p − 1 ) σ k + 1 + e k + p p ( ∑ j > k σ j 2 ) 1 / 2 \mathbb{E}\|A - \tilde{A}_k\|_2 \leq \left(1 + \sqrt{\frac{k}{p-1}}\right)\sigma_{k+1} + \frac{e\sqrt{k+p}}{p}\left(\sum_{j>k}\sigma_j^2\right)^{1/2} E ∥ A − A ~ k ∥ 2 ≤ ( 1 + p − 1 k ) σ k + 1 + p e k + p ( ∑ j > k σ j 2 ) 1/2
当奇异值快速衰减（σ k + 1 ≪ σ k \sigma_{k+1} \ll \sigma_k σ k + 1 ≪ σ k σ k + 1 \sigma_{k+1} σ k + 1
直觉总结
随机化 SVD 的核心交易 ：用 O ( m n ( k + p ) ) O(mn(k+p)) O ( mn ( k + p )) ( 1 + δ ) (1+\delta) ( 1 + δ ) δ \delta δ p p p
数值例子
让我们用一个小例子验证算法的正确性。
设 A ∈ R 6 × 4 A \in \mathbb{R}^{6 \times 4} A ∈ R 6 × 4
A = [ 3 1 0 2 1 0 ] [ 1 0 1 0 ] ⏟ σ 1 ≈ large + [ 0 1 2 0 1 2 ] [ 0 1 0 1 ] ⏟ σ 2 ≈ medium + 0.01 ⋅ noise ⏟ σ 3 , σ 4 ≈ 0 A = \underbrace{\begin{bmatrix}3\\1\\0\\2\\1\\0\end{bmatrix}\begin{bmatrix}1&0&1&0\end{bmatrix}}_{\sigma_1 \approx \text{large}} + \underbrace{\begin{bmatrix}0\\1\\2\\0\\1\\2\end{bmatrix}\begin{bmatrix}0&1&0&1\end{bmatrix}}_{\sigma_2 \approx \text{medium}} + \underbrace{0.01 \cdot \text{noise}}_{\sigma_3, \sigma_4 \approx 0} A = σ 1 ≈ large 3 1 0 2 1 0 [ 1 0 1 0 ] + σ 2 ≈ medium 0 1 2 0 1 2 [ 0 1 0 1 ] + σ 3 , σ 4 ≈ 0 0.01 ⋅ noise
假设我们只想要前 k = 2 k = 2 k = 2 p = 2 p = 2 p = 2 Ω ∈ R 4 × 4 \Omega \in \mathbb{R}^{4 \times 4} Ω ∈ R 4 × 4
计算 Y = A Ω Y = A\Omega Y = A Ω ：Y Y Y 6 × 4 6 \times 4 6 × 4 A A A Y Y Y QR 分解 ：Q Q Q 小空间 SVD ：B = Q T A B = Q^T A B = Q T A 4 × 4 4 \times 4 4 × 4 截断 ：取前 k = 2 k = 2 k = 2 A ~ 2 \tilde{A}_2 A ~ 2 A 2 A_2 A 2
关键观察：A A A
实践要点
何时用随机化 SVD
矩阵巨大但只需前 k k k ：这是最常见的场景。k ≪ min ( m , n ) k \ll \min(m,n) k ≪ min ( m , n ) 矩阵只能做矩阵-向量乘法 （如稀疏矩阵、隐式矩阵）：随机化 SVD 只需要 A Ω A\Omega A Ω A T Q A^T Q A T Q A A A Streaming / single-pass ：数据按行/按块到达，每次更新 Y Y Y
主流实现
库 函数 备注 scikit-learn TruncatedSVD(algorithm='randomized')默认算法 scipy scipy.sparse.linalg.svds支持稀疏矩阵 Facebook (Meta) fbpca.pca专为大规模优化 cuML (RAPIDS) cuml.decomposition.TruncatedSVDGPU 加速
scikit-learn 的 TruncatedSVD 和 PCA 默认使用随机化 SVD（algorithm='randomized'），而非精确分解。绝大多数用户在调用 PCA(n_components=50) 时，实际执行的就是本文描述的 Halko-Martinsson-Tropp 算法。
总结与展望
本文建立了两个核心工具：
Johnson-Lindenstrauss 引理 ：N N N O ( ln N / ε 2 ) O(\ln N / \varepsilon^2) O ( ln N / ε 2 ) ( 1 ± ε ) (1 \pm \varepsilon) ( 1 ± ε ) 随机化 SVD （Halko-Martinsson-Tropp, 2011）：通过随机投影将矩阵压缩到 k + p k + p k + p O ( m n min ( m , n ) ) O(mn\min(m,n)) O ( mn min ( m , n )) O ( m n ( k + p ) ) O(mn(k+p)) O ( mn ( k + p )) p p p
关键公式回顾：
JL 维度要求 ：k ≥ 8 ln N / ε 2 k \geq 8\ln N / \varepsilon^2 k ≥ 8 ln N / ε 2 随机投影 ：f ( x ) = 1 k Ω x f(\mathbf{x}) = \frac{1}{\sqrt{k}}\Omega\mathbf{x} f ( x ) = k 1 Ω x Ω i j ∼ N ( 0 , 1 ) \Omega_{ij} \sim \mathcal{N}(0,1) Ω ij ∼ N ( 0 , 1 ) 核心步骤 ：Y = A Ω → Q = orth ( Y ) → B = Q T A → SVD ( B ) Y = A\Omega \to Q = \text{orth}(Y) \to B = Q^TA \to \text{SVD}(B) Y = A Ω → Q = orth ( Y ) → B = Q T A → SVD ( B ) 误差界 ：E ∥ A − A ~ k ∥ F ≤ ( 1 + k / ( p − 1 ) ) 1 / 2 ∥ A − A k ∥ F \mathbb{E}\|A - \tilde{A}_k\|_F \leq (1 + k/(p-1))^{1/2}\|A - A_k\|_F E ∥ A − A ~ k ∥ F ≤ ( 1 + k / ( p − 1 ) ) 1/2 ∥ A − A k ∥ F
随机化 SVD 是 Part 1 “拆”阶段从精确分解走向可扩展分解的关键一步。后续的应用文章——矩阵补全 、NMF 、Robust PCA ——中的大规模计算几乎都依赖随机化技术加速核心的 SVD 步骤。更远处，Part 3 “汇”中 LoRA 的低秩适配和 Efficient Attention 的低秩近似，同样植根于”大矩阵有低秩结构，可以用少量随机采样捕获”这一洞察。