矩阵分解(Matrix Decomposition / Matrix Factorization)是将一个矩阵拆解为多个更简单矩阵的乘积或和的过程。通过分解,原本难以直接处理的矩阵运算(如求逆、解线性方程组、特征值计算)可以被转化成对简单结构的操作,极大提升数值稳定性和计算效率。在机器学习、优化算法(尤其是 Preconditioner 预处理器)、信号处理、推荐系统等领域,矩阵分解都是最核心的数学工具之一。
直接处理一个大矩阵通常面临三个问题:
计算复杂度高 :对一个 n × n n \times nn × n 矩阵求逆的复杂度为 O ( n 3 ) O(n^3)O ( n 3 ) ,当 n = 10 5 n=10^5n = 1 0 5 时,这意味着一台现代 CPU 需要数周才能完成一次求逆
数值不稳定性 :直接求解 A x = b Ax=bA x = b 时,如果 A AA 的条件数很大(病态矩阵),微小输入误差会导致巨大输出偏差
存储开销大 :稠密矩阵的存储为 O ( n 2 ) O(n^2)O ( n 2 ) ,对于高维数据难以承受
矩阵分解通过揭示矩阵的内部结构来解决这些问题。不同类型的分解适用于不同的矩阵性质和不同的应用场景。
分解类型
适用范围
时间复杂度
核心用途
LU 分解
任意方阵
O ( n 3 ) O(n^3)O ( n 3 )
解线性方程组、求逆
Cholesky 分解
对称正定矩阵
O ( 1 3 n 3 ) O(\frac{1}{3}n^3)O ( 3 1 n 3 )
更高效地求解正定系统
QR 分解
任意矩阵
O ( m n 2 ) O(mn^2)O ( m n 2 )
最小二乘、特征值计算
特征值分解
可对角化方阵
O ( n 3 ) O(n^3)O ( n 3 )
主成分分析、谱聚类
SVD
任意矩阵
O ( m n 2 ) O(mn^2)O ( m n 2 )
降维、降噪、推荐系统
LU 分解将一个方阵 A AA 分解为下三角矩阵 L LL 和上三角矩阵 U UU 的乘积:
A = L U A = LU
A = LU
其中 L LL 是单位下三角矩阵(对角线元素为 1),U UU 是上三角矩阵。
考虑矩阵:
A = ( 2 1 1 4 3 3 2 4 9 ) A = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 2 & 4 & 9 \end{pmatrix}
A = 2 4 2 1 3 4 1 3 9
步骤 1:消元
第一行乘以 2 减去第二行:R 2 ← R 2 − 2 R 1 R_2 \leftarrow R_2 - 2R_1R 2 ← R 2 − 2 R 1 ,得到 l 21 = 2 l_{21}=2l 21 = 2
第一行乘以 1 减去第三行:R 3 ← R 3 − 1 R 1 R_3 \leftarrow R_3 - 1R_1R 3 ← R 3 − 1 R 1 ,得到 l 31 = 1 l_{31}=1l 31 = 1
中间结果矩阵:
A ( 1 ) = ( 2 1 1 0 1 1 0 3 8 ) A^{(1)} = \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 3 & 8 \end{pmatrix}
A ( 1 ) = 2 0 0 1 1 3 1 1 8
步骤 2:继续消元
第二行乘以 3 减去第三行:R 3 ← R 3 − 3 R 1 R_3 \leftarrow R_3 - 3R_1R 3 ← R 3 − 3 R 1 ,得到 l 32 = 3 l_{32}=3l 32 = 3
最终上三角矩阵:
U = ( 2 1 1 0 1 1 0 0 5 ) U = \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 5 \end{pmatrix}
U = 2 0 0 1 1 0 1 1 5
下三角矩阵 L LL 由消元乘数构成:
L = ( 1 0 0 2 1 0 1 3 1 ) L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 3 & 1 \end{pmatrix}
L = 1 2 1 0 1 3 0 0 1
验证:L U = A LU = ALU = A 成立。
求解 A x = b Ax=bA x = b 时,先将 A = L U A=LUA = LU 代入:
L U x = b LUx = b
LU x = b
分两步求解:
前向替换:解 L y = b Ly = bL y = b (O ( n 2 ) O(n^2)O ( n 2 ) )
后向替换:解 U x = y Ux = yU x = y (O ( n 2 ) O(n^2)O ( n 2 ) )
具体示例 :对于上述 A AA 和 b = ( 4 , 10 , 15 ) T b = (4, 10, 15)^Tb = ( 4 , 10 , 15 ) T :
步骤 1 — 解 L y = b Ly = bL y = b :
( 1 0 0 2 1 0 1 3 1 ) ( y 1 y 2 y 3 ) = ( 4 10 15 ) \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 3 & 1 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} = \begin{pmatrix} 4 \\ 10 \\ 15 \end{pmatrix}
1 2 1 0 1 3 0 0 1 y 1 y 2 y 3 = 4 10 15
前向代入:y 1 = 4 y_1 = 4y 1 = 4 , y 2 = 10 − 2 × 4 = 2 y_2 = 10 - 2 \times 4 = 2y 2 = 10 − 2 × 4 = 2 , y 3 = 15 − 1 × 4 − 3 × 2 = 5 y_3 = 15 - 1 \times 4 - 3 \times 2 = 5y 3 = 15 − 1 × 4 − 3 × 2 = 5
步骤 2 — 解 U x = y Ux = yU x = y :
( 2 1 1 0 1 1 0 0 5 ) ( x 1 x 2 x 3 ) = ( 4 2 5 ) \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 5 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 4 \\ 2 \\ 5 \end{pmatrix}
2 0 0 1 1 0 1 1 5 x 1 x 2 x 3 = 4 2 5
后向代入:x 3 = 5 / 5 = 1 x_3 = 5/5 = 1x 3 = 5/5 = 1 , x 2 = 2 − 1 = 1 x_2 = 2 - 1 = 1x 2 = 2 − 1 = 1 , x 1 = ( 4 − 1 × 1 − 1 × 1 ) / 2 = 1 x_1 = (4 - 1 \times 1 - 1 \times 1)/2 = 1x 1 = ( 4 − 1 × 1 − 1 × 1 ) /2 = 1
最终解:x = ( 1 , 1 , 1 ) T x = (1, 1, 1)^Tx = ( 1 , 1 , 1 ) T ,验证 A x = ( 4 , 10 , 15 ) T = b Ax = (4, 10, 15)^T = bA x = ( 4 , 10 , 15 ) T = b ✅
多次求解同一系数矩阵 :一旦分解完成,每次仅需 O ( n 2 ) O(n^2)O ( n 2 ) 的前向/后向替换。对于 k kk 次求解,总复杂度 O ( n 3 + k n 2 ) O(n^3 + kn^2)O ( n 3 + k n 2 ) ,远优于直接求逆的 O ( k n 3 ) O(kn^3)O ( k n 3 )
矩阵求逆 :对 A AA 做 LU 分解后,每列求解依次得到逆矩阵的各列
行列式计算 :det ( A ) = det ( L ) ⋅ det ( U ) = 1 × ∏ i = 1 n u i i \det(A) = \det(L) \cdot \det(U) = 1 \times \prod_{i=1}^n u_{ii}det ( A ) = det ( L ) ⋅ det ( U ) = 1 × ∏ i = 1 n u ii ,即对角元乘积
如果 A AA 是对称正定矩阵(SPD),则可以分解为:
A = L L T A = LL^T
A = L L T
其中 L LL 是下三角矩阵(对角线元素为正)。相比 LU 分解,Cholesky 利用了对称性,计算量只有 LU 的一半。
假设 A AA 是一个 3 × 3 3 \times 33 × 3 对称正定矩阵:
A = ( a 11 a 12 a 13 a 12 a 22 a 23 a 13 a 23 a 33 ) A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33} \end{pmatrix}
A = a 11 a 12 a 13 a 12 a 22 a 23 a 13 a 23 a 33
Cholesky 分解的递推公式为:
l j j = a j j − ∑ k = 1 j − 1 l j k 2 l_{jj} = \sqrt{a_{jj} - \sum_{k=1}^{j-1} l_{jk}^2}
l j j = a j j − k = 1 ∑ j − 1 l j k 2
l i j = 1 l j j ( a i j − ∑ k = 1 j − 1 l i k l j k ) , i > j l_{ij} = \frac{1}{l_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik} l_{jk} \right), \quad i > j
l ij = l j j 1 ( a ij − k = 1 ∑ j − 1 l ik l j k ) , i > j
A = ( 4 2 2 2 5 3 2 3 6 ) A = \begin{pmatrix} 4 & 2 & 2 \\ 2 & 5 & 3 \\ 2 & 3 & 6 \end{pmatrix}
A = 4 2 2 2 5 3 2 3 6
步骤 1 :l 11 = 4 = 2 l_{11} = \sqrt{4} = 2l 11 = 4 = 2 ,l 21 = 2 / 2 = 1 l_{21} = 2/2 = 1l 21 = 2/2 = 1 ,l 31 = 2 / 2 = 1 l_{31} = 2/2 = 1l 31 = 2/2 = 1
步骤 2 :l 22 = 5 − 1 2 = 4 = 2 l_{22} = \sqrt{5 - 1^2} = \sqrt{4} = 2l 22 = 5 − 1 2 = 4 = 2 ,l 32 = ( 3 − 1 × 1 ) / 2 = 1 l_{32} = (3 - 1 \times 1)/2 = 1l 32 = ( 3 − 1 × 1 ) /2 = 1
步骤 3 :l 33 = 6 − 1 2 − 1 2 = 4 = 2 l_{33} = \sqrt{6 - 1^2 - 1^2} = \sqrt{4} = 2l 33 = 6 − 1 2 − 1 2 = 4 = 2
最终分解:
L = ( 2 0 0 1 2 0 1 1 2 ) L = \begin{pmatrix} 2 & 0 & 0 \\ 1 & 2 & 0 \\ 1 & 1 & 2 \end{pmatrix}
L = 2 1 1 0 2 1 0 0 2
验证 L L T = A LL^T = AL L T = A ✅
求解最小二乘问题 :正规方程 X T X β = X T y X^T X \beta = X^T yX T X β = X T y 中的 X T X X^T XX T X 是 SPD,可用 Cholesky 高效求解
Preconditioner 构建 :不完全 Cholesky 分解(Incomplete Cholesky)是共轭梯度法中最常用的预处理器之一,它在分解时忽略某些小元素来保持稀疏性
蒙特卡洛模拟 :对协方差矩阵做 Cholesky 分解,可以从独立正态样本生成相关正态样本
指标
LU 分解
Cholesky 分解
适用条件
任意可逆方阵
对称正定矩阵
计算量
2 3 n 3 \frac{2}{3}n^33 2 n 3 FLOPS
1 3 n 3 \frac{1}{3}n^33 1 n 3 FLOPS
存储
同时存 L 和 U
只存 L(对称性)
数值稳定性
通常需要选主元
无需选主元(天然稳定)
QR 分解将一个 m × n m \times nm × n 矩阵 A AA (m ≥ n m \geq nm ≥ n )分解为正交矩阵 Q QQ 和上三角矩阵 R RR 的乘积:
A = Q R A = QR
A = QR
其中 Q T Q = I Q^T Q = IQ T Q = I (Q QQ 的列是标准正交向量),R RR 是 n × n n \times nn × n 上三角矩阵。
以 3 × 3 3 \times 33 × 3 矩阵为例,原始列向量为 a 1 , a 2 , a 3 a_1, a_2, a_3a 1 , a 2 , a 3 :
步骤 1 :q 1 = a 1 ∥ a 1 ∥ q_1 = \frac{a_1}{\|a_1\|}q 1 = ∥ a 1 ∥ a 1 ,r 11 = ∥ a 1 ∥ r_{11} = \|a_1\|r 11 = ∥ a 1 ∥
步骤 2 :q 2 ′ = a 2 − ( a 2 ⋅ q 1 ) q 1 q_2' = a_2 - (a_2 \cdot q_1)q_1q 2 ′ = a 2 − ( a 2 ⋅ q 1 ) q 1 ,q 2 = q 2 ′ ∥ q 2 ′ ∥ q_2 = \frac{q_2'}{\|q_2'\|}q 2 = ∥ q 2 ′ ∥ q 2 ′
步骤 3 :q 3 ′ = a 3 − ( a 3 ⋅ q 1 ) q 1 − ( a 3 ⋅ q 2 ) q 2 q_3' = a_3 - (a_3 \cdot q_1)q_1 - (a_3 \cdot q_2)q_2q 3 ′ = a 3 − ( a 3 ⋅ q 1 ) q 1 − ( a 3 ⋅ q 2 ) q 2 ,q 3 = q 3 ′ ∥ q 3 ′ ∥ q_3 = \frac{q_3'}{\|q_3'\|}q 3 = ∥ q 3 ′ ∥ q 3 ′
数值示例 :
A = ( 1 1 0 1 0 1 0 1 1 ) A = \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}
A = 1 1 0 1 0 1 0 1 1
∥ a 1 ∥ = 1 2 + 1 2 + 0 2 = 2 \|a_1\| = \sqrt{1^2 + 1^2 + 0^2} = \sqrt{2}∥ a 1 ∥ = 1 2 + 1 2 + 0 2 = 2 ,所以 q 1 = ( 1 2 , 1 2 , 0 ) T q_1 = (\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0)^Tq 1 = ( 2 1 , 2 1 , 0 ) T
a 2 ⋅ q 1 = 1 ⋅ 1 2 + 0 ⋅ 1 2 + 1 ⋅ 0 = 1 2 a_2 \cdot q_1 = 1 \cdot \frac{1}{\sqrt{2}} + 0 \cdot \frac{1}{\sqrt{2}} + 1 \cdot 0 = \frac{1}{\sqrt{2}}a 2 ⋅ q 1 = 1 ⋅ 2 1 + 0 ⋅ 2 1 + 1 ⋅ 0 = 2 1
q 2 ′ = ( 1 , 0 , 1 ) T − 1 2 ⋅ ( 1 2 , 1 2 , 0 ) T = ( 1 2 , − 1 2 , 1 ) T q_2' = (1, 0, 1)^T - \frac{1}{\sqrt{2}} \cdot (\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0)^T = (\frac{1}{2}, -\frac{1}{2}, 1)^Tq 2 ′ = ( 1 , 0 , 1 ) T − 2 1 ⋅ ( 2 1 , 2 1 , 0 ) T = ( 2 1 , − 2 1 , 1 ) T
∥ q 2 ′ ∥ = ( 1 2 ) 2 + ( − 1 2 ) 2 + 1 2 = 3 2 = 6 2 \|q_2'\| = \sqrt{(\frac{1}{2})^2 + (-\frac{1}{2})^2 + 1^2} = \sqrt{\frac{3}{2}} = \frac{\sqrt{6}}{2}∥ q 2 ′ ∥ = ( 2 1 ) 2 + ( − 2 1 ) 2 + 1 2 = 2 3 = 2 6
q 2 = ( 1 6 , − 1 6 , 2 6 ) T q_2 = (\frac{1}{\sqrt{6}}, -\frac{1}{\sqrt{6}}, \frac{2}{\sqrt{6}})^Tq 2 = ( 6 1 , − 6 1 , 6 2 ) T
依此类推得到完整的 QR 分解。
经典 Gram-Schmidt 在数值上不稳定。修正 Gram-Schmidt 在每个正交化步骤中使用已经更新过的向量:
def modified_gram_schmidt(A):
m, n = A.shape
Q = A.copy().astype(float)
R = np.zeros((n, n))
for i in range(n):
R[i, i] = np.linalg.norm(Q[:, i])
Q[:, i] = Q[:, i] / R[i, i]
for j in range(i+1, n):
R[i, j] = Q[:, i] @ Q[:, j]
Q[:, j] = Q[:, j] - R[i, j] * Q[:, i]
return Q, R
最小二乘问题 (最稳定方法):求解 min ∥ A x − b ∥ 2 \min \|Ax - b\|_2min ∥ A x − b ∥ 2 时,QR 分解不要求 A T A A^T AA T A 正定,且数值稳定性优于正规方程法。转化为 R x = Q T b Rx = Q^T bR x = Q T b
特征值计算 :QR 算法是计算稠密矩阵全特征值的最常用方法
信号处理 :自适应滤波中的 QR-RLS 算法
对于可对角化的方阵 A ∈ R n × n A \in \mathbb{R}^{n \times n}A ∈ R n × n ,特征值分解为:
A = V Λ V − 1 A = V \Lambda V^{-1}
A = V Λ V − 1
其中 Λ = diag ( λ 1 , … , λ n ) \Lambda = \text{diag}(\lambda_1, \dots, \lambda_n)Λ = diag ( λ 1 , … , λ n ) 是特征值组成的对角矩阵,V = [ v 1 , … , v n ] V = [v_1, \dots, v_n]V = [ v 1 , … , v n ] 是对应特征向量组成的矩阵。
几何上,特征值分解将一个线性变换分解为三个步骤:变换到特征向量基(V − 1 V^{-1}V − 1 )、在各个特征方向上缩放(Λ \LambdaΛ )、再变换回原始基(V VV )。
A = ( 4 1 2 3 ) A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}
A = ( 4 2 1 3 )
求解特征值:det ( A − λ I ) = ( 4 − λ ) ( 3 − λ ) − 2 = λ 2 − 7 λ + 10 = 0 \det(A - \lambda I) = (4-\lambda)(3-\lambda) - 2 = \lambda^2 - 7\lambda + 10 = 0det ( A − λ I ) = ( 4 − λ ) ( 3 − λ ) − 2 = λ 2 − 7 λ + 10 = 0
特征值:λ 1 = 5 \lambda_1 = 5λ 1 = 5 ,λ 2 = 2 \lambda_2 = 2λ 2 = 2
特征向量:
对于 λ 1 = 5 \lambda_1 = 5λ 1 = 5 :( A − 5 I ) v 1 = 0 (A - 5I)v_1 = 0( A − 5 I ) v 1 = 0 ,即 ( − 1 1 2 − 2 ) v 1 = 0 \begin{pmatrix} -1 & 1 \\ 2 & -2 \end{pmatrix}v_1 = 0( − 1 2 1 − 2 ) v 1 = 0 ,解得 v 1 = ( 1 , 1 ) T v_1 = (1, 1)^Tv 1 = ( 1 , 1 ) T
对于 λ 2 = 2 \lambda_2 = 2λ 2 = 2 :( A − 2 I ) v 2 = 0 (A - 2I)v_2 = 0( A − 2 I ) v 2 = 0 ,即 ( 2 1 2 1 ) v 2 = 0 \begin{pmatrix} 2 & 1 \\ 2 & 1 \end{pmatrix}v_2 = 0( 2 2 1 1 ) v 2 = 0 ,解得 v 2 = ( 1 , − 2 ) T v_2 = (1, -2)^Tv 2 = ( 1 , − 2 ) T
验证:
V Λ V − 1 = ( 1 1 1 − 2 ) ( 5 0 0 2 ) 1 − 3 ( − 2 − 1 − 1 1 ) = ( 4 1 2 3 ) = A V\Lambda V^{-1} = \begin{pmatrix} 1 & 1 \\ 1 & -2 \end{pmatrix} \begin{pmatrix} 5 & 0 \\ 0 & 2 \end{pmatrix} \frac{1}{-3} \begin{pmatrix} -2 & -1 \\ -1 & 1 \end{pmatrix} = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix} = A
V Λ V − 1 = ( 1 1 1 − 2 ) ( 5 0 0 2 ) − 3 1 ( − 2 − 1 − 1 1 ) = ( 4 2 1 3 ) = A
如果 A AA 是对称矩阵,则 V VV 是正交矩阵(V − 1 = V T V^{-1} = V^TV − 1 = V T ),特征值分解简化为:
A = V Λ V T A = V \Lambda V^T
A = V Λ V T
这是谱定理的核心结论,也是 PCA(主成分分析)的数学基础。
主成分分析 :对协方差矩阵做特征值分解,将前 k kk 个最大特征值对应的特征向量作为主成分方向
谱聚类 :对图的拉普拉斯矩阵做特征值分解,实现非线性聚类
动力系统稳定性 :线性系统 x t + 1 = A x t x_{t+1} = Ax_tx t + 1 = A x t 的稳定性由 A AA 的最大特征值决定
动力系统示例 :
x t + 1 = ( 0.8 0.1 0.1 0.9 ) x t x_{t+1} = \begin{pmatrix} 0.8 & 0.1 \\ 0.1 & 0.9 \end{pmatrix} x_t
x t + 1 = ( 0.8 0.1 0.1 0.9 ) x t
特征值 λ 1 = 0.97 \lambda_1 = 0.97λ 1 = 0.97 ,λ 2 = 0.73 \lambda_2 = 0.73λ 2 = 0.73 ,两者都小于 1,系统是稳定的。如果任何特征值的模大于 1,系统就会发散。
并非所有矩阵都可对角化。例如 Jordan 块 ( 1 1 0 1 ) \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}( 1 0 1 1 ) 只有一个特征向量,无法进行特征值分解。此时需要更复杂的 Jordan 标准形或使用 SVD。
SVD 是矩阵分解中最通用、最强有力的工具。对于任意矩阵 A ∈ R m × n A \in \mathbb{R}^{m \times n}A ∈ R m × n ,SVD 将其分解为:
A = U Σ V T A = U \Sigma V^T
A = U Σ V T
其中:
U ∈ R m × m U \in \mathbb{R}^{m \times m}U ∈ R m × m 是正交矩阵(左奇异向量)
V ∈ R n × n V \in \mathbb{R}^{n \times n}V ∈ R n × n 是正交矩阵(右奇异向量)
Σ ∈ R m × n \Sigma \in \mathbb{R}^{m \times n}Σ ∈ R m × n 是对角矩阵(奇异值 σ 1 ≥ σ 2 ≥ ⋯ ≥ σ min ( m , n ) ≥ 0 \sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_{\min(m,n)} \geq 0σ 1 ≥ σ 2 ≥ ⋯ ≥ σ m i n ( m , n ) ≥ 0 )
几何上,A AA 的 SVD 将一个向量变换分解为:旋转/反射(V T V^TV T )、在各方向上拉伸(Σ \SigmaΣ )、再旋转/反射(U UU )。
对于 A T A A^T AA T A 和 A A T A A^TA A T :
A T A = V Σ T Σ V T ( A T A 的特征值分解) A^T A = V \Sigma^T \Sigma V^T \quad \text{($A^T A$ 的特征值分解)}
A T A = V Σ T Σ V T ( A T A 的特征值分解)
A A T = U Σ Σ T U T ( A A T 的特征值分解) A A^T = U \Sigma \Sigma^T U^T \quad \text{($A A^T$ 的特征值分解)}
A A T = U Σ Σ T U T ( A A T 的特征值分解)
奇异值 σ i \sigma_iσ i 是 A T A A^T AA T A 特征值的平方根。这使得 SVD 可以看作特征值分解对非对称、非方阵的自然推广。
A = ( 3 1 1 3 0 0 ) A = \begin{pmatrix} 3 & 1 \\ 1 & 3 \\ 0 & 0 \end{pmatrix}
A = 3 1 0 1 3 0
步骤 1 :计算 A T A = ( 10 6 6 10 ) A^T A = \begin{pmatrix} 10 & 6 \\ 6 & 10 \end{pmatrix}A T A = ( 10 6 6 10 )
步骤 2 :求解 A T A A^T AA T A 的特征值和特征向量
特征方程:det ( A T A − λ I ) = ( 10 − λ ) 2 − 36 = 0 \det(A^T A - \lambda I) = (10 - \lambda)^2 - 36 = 0det ( A T A − λ I ) = ( 10 − λ ) 2 − 36 = 0
特征值:λ 1 = 16 \lambda_1 = 16λ 1 = 16 ,λ 2 = 4 \lambda_2 = 4λ 2 = 4
奇异值:σ 1 = 16 = 4 \sigma_1 = \sqrt{16} = 4σ 1 = 16 = 4 ,σ 2 = 4 = 2 \sigma_2 = \sqrt{4} = 2σ 2 = 4 = 2
特征向量(V VV 的列):
λ 1 = 16 \lambda_1 = 16λ 1 = 16 :v 1 = ( 1 2 , 1 2 ) T v_1 = (\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})^Tv 1 = ( 2 1 , 2 1 ) T
λ 2 = 4 \lambda_2 = 4λ 2 = 4 :v 2 = ( − 1 2 , 1 2 ) T v_2 = (-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})^Tv 2 = ( − 2 1 , 2 1 ) T
步骤 3 :计算 U UU 的左奇异向量
u i = 1 σ i A v i u_i = \frac{1}{\sigma_i} A v_iu i = σ i 1 A v i
u 1 = 1 4 A ( 1 2 , 1 2 ) T = 1 4 ( 4 2 , 4 2 , 0 ) T = ( 1 2 , 1 2 , 0 ) T u_1 = \frac{1}{4} A (\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})^T = \frac{1}{4} (\frac{4}{\sqrt{2}}, \frac{4}{\sqrt{2}}, 0)^T = (\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0)^Tu 1 = 4 1 A ( 2 1 , 2 1 ) T = 4 1 ( 2 4 , 2 4 , 0 ) T = ( 2 1 , 2 1 , 0 ) T
u 2 = 1 2 A ( − 1 2 , 1 2 ) T = 1 2 ( − 2 2 , 2 2 , 0 ) T = ( − 1 2 , 1 2 , 0 ) T u_2 = \frac{1}{2} A (-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})^T = \frac{1}{2} (-\frac{2}{\sqrt{2}}, \frac{2}{\sqrt{2}}, 0)^T = (-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}, 0)^Tu 2 = 2 1 A ( − 2 1 , 2 1 ) T = 2 1 ( − 2 2 , 2 2 , 0 ) T = ( − 2 1 , 2 1 , 0 ) T
u 3 u_3u 3 可通过扩展正交基得到:u 3 = ( 0 , 0 , 1 ) T u_3 = (0, 0, 1)^Tu 3 = ( 0 , 0 , 1 ) T
最终分解:
A = ( 1 2 − 1 2 0 1 2 1 2 0 0 0 1 ) ( 4 0 0 2 0 0 ) ( 1 2 1 2 − 1 2 1 2 ) T A = \begin{pmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 4 & 0 \\ 0 & 2 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{pmatrix}^T
A = 2 1 2 1 0 − 2 1 2 1 0 0 0 1 4 0 0 0 2 0 ( 2 1 − 2 1 2 1 2 1 ) T
SVD 最重要的应用之一是低秩近似。根据 Eckart-Young 定理,矩阵 A AA 的秩 k kk 最佳近似由前 k kk 个奇异值及其对应向量给出:
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
压缩效果示例 :
原始矩阵 A AA 大小 1000 × 1000 1000 \times 10001000 × 1000 ,需要 10 6 10^61 0 6 个元素
取 k = 50 k=50k = 50 的近似需要存储:1000 × 50 + 50 + 50 × 1000 ≈ 10 5 1000 \times 50 + 50 + 50 \times 1000 \approx 10^51000 × 50 + 50 + 50 × 1000 ≈ 1 0 5 个元素
压缩率:10 × 10 \times10 ×
以一张灰度图片为例,它本身就是 m × n m \times nm × n 的矩阵。取不同 k kk 值的重建效果:
k kk (保留奇异值数)
存储占比
视觉效果
1
0.2%
可辨轮廓
10
2%
清晰轮廓,细节模糊
50
10%
接近原图
100
20%
人眼几乎无法区分
全秩
100%
原始图像
推荐系统 :Netflix Prize 的获奖算法基于矩阵分解(SVD),将用户-物品评分矩阵分解为用户特征矩阵和物品特征矩阵
降维 :PCA 可以通过 SVD 高效实现(对数据中心化后做 SVD)
降噪 :将小于某个阈值的小奇异值置零,可以滤除噪声
计算矩阵伪逆 :A + = V Σ + U T A^+ = V \Sigma^+ U^TA + = V Σ + U T ,其中 Σ + \Sigma^+Σ + 是将非零奇异值取倒数
Preconditioner 构建 :SVD 可以分析矩阵的奇异值分布,指导预处理器设计
Preconditioner 预处理器是迭代求解线性系统时加速收敛的关键技术。其核心思想是将原始系统 A x = b Ax=bA x = b 转换为等价系统 M − 1 A x = M − 1 b M^{-1}Ax = M^{-1}bM − 1 A x = M − 1 b ,使得 M − 1 A M^{-1}AM − 1 A 的条件数更小。
分解类型
预处理器名称
原理
优缺点
LU
ILU (不完全 LU)
在 LU 分解中忽略某些填充元,保持稀疏性
通用性好,但对 SPD 矩阵不如 Cholesky 高效
Cholesky
IC (不完全 Cholesky)
在不完全 Cholesky 分解的基础上,只保留非零模式的元素
对 SPD 矩阵非常高效,是 CG 法的经典选择
SVD
频谱预处理
基于 SVD 分析矩阵的奇异值分布,针对性地压缩频谱
理论优美,但计算 SVD 的成本较高
QR
—
QR 可用于分析矩阵的数值秩
较少直接用作预处理器
对于共轭梯度法,收敛速度受矩阵条件数 κ = σ max σ min \kappa = \frac{\sigma_{\max}}{\sigma_{\min}}κ = σ m i n σ m a x 的影响:
∥ x k − x ∥ A ≤ 2 ( κ − 1 κ + 1 ) k ∥ x 0 − x ∥ A \|x_k - x\|_A \leq 2 \left( \frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1} \right)^k \|x_0 - x\|_A
∥ x k − x ∥ A ≤ 2 ( κ + 1 κ − 1 ) k ∥ x 0 − x ∥ A
数值对比 :
设想求解一个 1000 × 1000 1000 \times 10001000 × 1000 的线性系统:
条件数 κ \kappaκ
收敛因子
达到 10 − 6 10^{-6}1 0 − 6 误差需要迭代次数
10 2 10^21 0 2
0.818
≈ 70
10 3 10^31 0 3
0.939
≈ 220
10 4 10^41 0 4
0.980
≈ 700
10 6 10^61 0 6 (使用预处理器后降至 10 2 10^21 0 2 )
0.818
≈ 70(vs 无预处理时约 2200 次)
import numpy as np
from scipy.sparse.linalg import LinearOperator
from scipy.linalg import cho_factor, cho_solve
def incomplete_cholesky(A):
"""简化的不完全 Cholesky 分解(丢弃绝对值小于阈值的元素)"""
n = A.shape[0]
L = np.tril(A).copy()
threshold = 1e-3
for j in range(n):
L[j, j] = np.sqrt(L[j, j])
for i in range(j+1, n):
if np.abs(L[i, j]) > threshold:
L[i, j] /= L[j, j]
for k in range(j+1, i+1):
if np.abs(L[i, k]) > threshold:
L[i, k] -= L[i, j] * L[k, j]
else:
L[i, j] = 0 # 丢弃小元素
return L
# 使用不完全 Cholesky 作为预处理器
# M = L @ L^T,求解 Mz = r 只需要两次三角求解
以协同过滤推荐系统为例,用户-物品评分矩阵通常是大规模、稀疏的。矩阵分解在其中扮演核心角色。
方法
数学基础
计算复杂度
预测准确度
可解释性
SVD
奇异值分解
O ( min ( m , n ) 3 ) O(\min(m,n)^3)O ( min ( m , n ) 3 ) ,需要对缺失值填充
中等
较好
FunkSVD (隐语义模型)
梯度下降优化
O ( k ⋅ nnz ) O(k \cdot \text{nnz})O ( k ⋅ nnz ) ,k kk 为隐因子数
好
中等
ALS (交替最小二乘)
QR/Cholesky 交替优化
O ( k 3 + k ⋅ nnz ) O(k^3 + k \cdot \text{nnz})O ( k 3 + k ⋅ nnz )
好
中等
NMF (非负矩阵分解)
非负约束分解
O ( k ⋅ nnz ) O(k \cdot \text{nnz})O ( k ⋅ nnz )
较好(非负数据)
好
数据集 :Netflix Prize 包含约 1 亿条评分,48 万用户,1.7 万部电影。设置隐因子数 k = 50 k=50k = 50 :
SVD 需要先填充缺失值(约 48 × 1.7 × 10 5 = 8.16 × 10 6 48 \times 1.7 \times 10^5 = 8.16 \times 10^648 × 1.7 × 1 0 5 = 8.16 × 1 0 6 个评分),导致存储爆炸
FunkSVD 只处理已有评分(约 10 8 10^81 0 8 个),每个 epoch 更新参数 2 k × 10 8 = 10 10 2k \times 10^8 = 10^{10}2 k × 1 0 8 = 1 0 10 次操作
ALS 每轮交替求解需要解 k × k k \times kk × k 的最小二乘问题,可使用 Cholesky 加速
分解
条件
输出
复杂度
关键应用
LU
可逆方阵
L LL (下三角),U UU (上三角)
O ( 2 n 3 / 3 ) O(2n^3/3)O ( 2 n 3 /3 )
解方程组、求逆
Cholesky
对称正定矩阵
L LL (下三角)
O ( n 3 / 3 ) O(n^3/3)O ( n 3 /3 )
正规方程、预处理器
QR
任意矩阵
Q QQ (正交),R RR (上三角)
O ( 2 m n 2 ) O(2mn^2)O ( 2 m n 2 )
最小二乘、特征值
特征值分解
可对角化方阵
V VV (特征向量),Λ \LambdaΛ (特征值)
O ( n 3 ) O(n^3)O ( n 3 )
PCA、谱聚类
SVD
任意矩阵
U UU 、Σ \SigmaΣ 、V T V^TV T
O ( m n 2 ) O(mn^2)O ( m n 2 )
降维、降噪、推荐
参考资料 :
Golub & Van Loan, Matrix Computations (4th ed.), Johns Hopkins University Press, 2013
Trefethen & Bau, Numerical Linear Algebra , SIAM, 1997
李航,《统计学习方法》(第 2 版),清华大学出版社,2019