投影矩阵、最小二乘法和SVD分解

磨菜刀的老花匠 2016-09-17

展开全文

投影矩阵广泛地应用在数学相关学科的各种证明中，但是由于其概念比较抽象，所以比较难理解。这篇文章主要从最小二乘法的推导导出投影矩阵，并且应用SVD分解，写出常用的几种投影矩阵的形式。

问题的提出

已知有一个这样的方程组：

A x = b

其中，

A \in R^{m \times n}, x, b \in R^{n}

当 $m = n$ 时，且 $r a n k (A) = n$ 时，这是一个适定方程组，有唯一解 $x = A^{- 1} b$
当 $m < n$ 时，或者 $r a n k (A) < n$ 时，这是一个欠定方程组，有无穷多个解。对于这种情况，我们使用 $r a n (A)$ 中与 $b$ 距离最近的向量对应的 $x$ 作为最小二乘解。而相应的 $r a n (A)$ 中的这个向量就是 $b$ 在空间 $r a n (A)$ 中的投影。

最小二乘法

几何解法

如上图所示， $b$ 不在 $r a n (A)$ 中， $A x_{0}$ 是 $r a n (A)$ 空间中对 $b$ 在欧几里得范数下的最好估计。此时

\forall x \in R^{n}, ⟨ A x, b - A x_{0} ⟩ = 0

等价于

x^{T} A^{T} (b - A x_{0}) = 0

由于x的任意性，所以

A^{T} (b - A x_{0}) = 0

整理得

x_{0} = (A^{T} A)^{- 1} A^{T} b = A^{†} b

其中

A^{†} = (A^{T} A)^{- 1} A^{T}

称为A的伪逆。

数值解法

原问题等价于

min | | A x - b | |_{2}^{2}

记 $f (x) = | | A x - b | |_{2}^{2} = (A x - b)^{T} (A x - b) = x^{T} A^{T} A x - 2 b^{T} A x b^{T} b$ ,对x求导得，

\nabla f = 2 (A^{T} A x - A^{T} b) = 0

解得，

x = (A^{T} A)^{- 1} A^{T} b = A^{†} b

投影矩阵

对最小二乘解两边同时乘以A，就是对应的投影向量，即

A x = A (A^{T} A)^{- 1} A^{T} b = P b

那么 $P = A (A^{T} A)^{- 1} A^{T}$ 就是将 $b$ 投影到 $r a n (A)$ 的投影矩阵。因为

P^{T} = A (A^{T} A)^{- 1} A^{T} = P, P^{2} = P

满足投影矩阵的定义。
所以

r a n (A)

对应的投影矩阵为

P = A (A^{T} A)^{- 1} A^{T}

SVD分解下的投影矩阵

秩为r的矩阵A的SVD分解为 $A = U Σ V^{T} \in R^{m \times n}$ 。其中，

U = [U_{r} | {\tilde{U}}_{r}], V = [V_{r} | {\tilde{V}}_{r}]

那么，带入公式可以得到

$V_{r} V_{r}^{T}$ 是 $r a n (A^{T}) = {n u l l (A)}^{⊥}$ 空间的投影矩阵
$U_{r} U_{r}^{T}$ 是 $r a n (A)$ 空间的投影矩阵

对于 $\forall x \in R^{n}$ ,有

⟨ V_{r} V_{r}^{T} x, {\tilde{V}}_{r} {\tilde{V}}_{r}^{T} x ⟩ = x^{T} V_{r} V_{r}^{T} {\tilde{V}}_{r} {\tilde{V}}_{r}^{T} x = 0

所以， ${\tilde{V}}_{r} {\tilde{V}}_{r}^{T}$ 是 $n u l l (A)$ 空间的投影矩阵
同理, ${\tilde{U}}_{r} {\tilde{U}}_{r}^{T}$ 是 $n u l l (A^{T}) = {r a n (A)}^{⊥}$ 空间的投影矩阵