Pseudo Inverse 伪逆
背景
当
A
A
A为满秩方阵时，方程
A
x
=
b
Ax=b
Ax=b有解
x
=
A
−
1
b
x=A^{-1}b
x=A−1b
当
A
A
A不为满秩方阵时，方程无解，但是我们希望求得近似解
x
′
=
arg min
∥
A
x
−
b
∥
=
A
+
b
x'=\argmin\|Ax-b\|=A^+b
x′=argmin∥Ax−b∥=A+b，其中
A
+
A^+
A+为伪逆矩阵
行/列满秩的情形
列满秩
当
A
A
A为列满秩矩阵时，
A
T
A
A^TA
ATA可逆，
A
T
(
A
x
−
b
)
=
0
⟺
A
T
A
x
=
A
T
b
A^T(Ax-b)=0\iff A^TAx=A^Tb
AT(Ax−b)=0⟺ATAx=ATb有唯一解
x
=
(
A
T
A
)
−
1
A
T
b
x=(A^TA)^{-1}A^Tb
x=(ATA)−1ATb，伪逆矩阵为
A
+
=
(
A
T
A
)
−
1
A
T
A^+=(A^TA)^{-1}A^T
A+=(ATA)−1AT
行满秩
这其实是列满秩的对偶情形，把“矩阵左乘列向量”调换为“矩阵右乘行向量”（如果想要几何理解，那就同时把几何意义也迁移过来），推导如上：
欲求
x
′
=
arg min
x
∥
x
T
A
−
b
T
∥
x'=\argmin_x\|x^TA-b^T\|
x′=xargmin∥xTA−bT∥
这样的
x
x
x满足
(
x
T
A
−
b
T
)
A
T
=
0
(x^TA-b^T)A^T=0
(xTA−bT)AT=0
解得
x
T
=
b
T
A
T
(
A
A
T
)
−
1
x^T=b^TA^T(AA^T)^{-1}
xT=bTAT(AAT)−1
因此伪逆矩阵为
A
+
=
A
T
(
A
A
T
)
−
1
A^+=A^T(AA^T)^{-1}
A+=AT(AAT)−1
一般矩阵的情形
满秩分解表示
A
T
(
A
x
−
b
)
=
0
⟺
A
T
A
x
=
A
T
b
A^T(Ax-b)=0\iff A^TAx=A^Tb
AT(Ax−b)=0⟺ATAx=ATb 有多解，我们希望找出其中模长最小的解
考虑
A
A
A的满秩分解
A
=
F
G
A=FG
A=FG
注：满秩分解
设A
∈
C
r
m
×
n
A\in C_r^{m\times n}
A∈Crm×n，则存在列满秩矩阵
B
∈
C
r
m
×
r
B\in C_r^{m\times r}
B∈Crm×r，行满秩矩阵
C
∈
C
r
r
×
n
C\in C_r^{r\times n}
C∈Crr×n，使得
A
=
B
C
A=BC
A=BC
可以证明：
（1）B的列向量为A的列空间的一组基
（2）C的行向量为A的行空间的一组基
首先考虑
b
b
b到
A
A
A的列空间的投影
b
′
=
F
(
F
T
F
)
−
1
F
T
b
b'=F(F^TF)^{-1}F^Tb
b′=F(FTF)−1FTb
因此只需求解方程
A
x
=
b
′
Ax=b'
Ax=b′
这次方程是有解的，且解可能不唯一
假如我们已经知道一个特解
x
0
x_0
x0，那么
x
0
x_0
x0到
A
A
A的行空间的投影
x
′
=
G
T
(
G
G
T
)
−
1
G
x
0
x'=G^T(GG^T)^{-1}Gx_0
x′=GT(GGT)−1Gx0就是模长最小的解（特解不用具体找，我们只需要知道它存在就行了）
A
x
0
=
b
′
F
G
x
0
=
F
(
F
T
F
)
−
1
F
T
b
(
F
T
F
)
−
1
F
T
F
G
x
0
=
(
F
T
F
)
−
1
F
T
F
(
F
T
F
)
−
1
F
T
b
G
x
0
=
(
F
T
F
)
−
1
F
T
b
\begin{aligned} Ax_0 & = b' \\ FGx_0 & = F(F^TF)^{-1}F^Tb \\ (F^TF)^{-1}F^TFGx_0 & = (F^TF)^{-1}F^TF(F^TF)^{-1}F^Tb \\ Gx_0 & = (F^TF)^{-1}F^Tb \\ \end{aligned}
Ax0FGx0(FTF)−1FTFGx0Gx0=b′=F(FTF)−1FTb=(FTF)−1FTF(FTF)−1FTb=(FTF)−1FTb
注：从第二行到第四行，实际在干的工作是，等式左右同时乘以
F
F
F的伪逆
F
+
F^+
F+。
注意F
F
F是列满秩矩阵，因此
F
+
=
(
F
T
F
)
−
1
F
T
F^+=(F^TF)^{-1}F^T
F+=(FTF)−1FT
因此
x
′
=
G
T
(
G
G
T
)
−
1
G
x
0
=
G
T
(
G
G
T
)
−
1
(
F
T
F
)
−
1
F
T
b
\begin{aligned} x' & = G^T(GG^T)^{-1}Gx_0 \\ & = G^T(GG^T)^{-1}(F^TF)^{-1}F^Tb \end{aligned}
x′=GT(GGT)−1Gx0=GT(GGT)−1(FTF)−1FTb
因此
A
+
=
G
T
(
G
G
T
)
−
1
(
F
T
F
)
−
1
F
T
A^+ = G^T(GG^T)^{-1}(F^TF)^{-1}F^T
A+=GT(GGT)−1(FTF)−1FT
参考资料
SVD表示
对于矩阵
A
∈
M
m
×
n
A\in M_{m\times n}
A∈Mm×n, 存在正交方阵
U
∈
M
n
×
n
,
V
∈
M
n
×
n
U\in M_{n\times n}, V \in M_{n\times n}
U∈Mn×n,V∈Mn×n，对角矩阵
Σ
∈
M
m
×
n
\Sigma \in M_{m\times n}
Σ∈Mm×n，满足：
A
=
U
Σ
V
A=U\Sigma V
A=UΣV
注：
在几何推导版本的SVD中，U
U
U和
V
V
V不是方阵，那就补齐一些元素把他们变成正交方阵，这些补齐的元素没有用，因为都会被
Σ
\Sigma
Σ中的0项给消去。当
U
U
U和
V
V
V为正交方阵时，有良好的性质，便于推导。
目标依然是寻找
x
′
=
arg min
∥
A
x
−
b
∥
x'=\argmin\|Ax-b\|
x′=argmin∥Ax−b∥
∥
A
x
−
b
∥
2
=
∥
U
Σ
V
T
x
−
b
∥
2
=
×
∥
U
T
∥
2
=
1
∥
Σ
V
T
x
−
U
T
b
∥
2
=
∑
i
=
1
r
(
σ
i
(
V
T
x
)
i
−
(
U
T
b
)
i
)
2
+
∑
i
=
r
+
1
n
(
U
T
b
)
i
2
\begin{aligned} \|Ax-b\|_2 & = \|U\Sigma V^Tx-b\|^2 \\ & \xlongequal{\times \|U^T\|^2=1} \|\Sigma V^Tx-U^Tb\|^2 \\ & = \sum_{i=1}^r\left( \sigma_i(V^Tx)_i - (U^Tb)_i \right)^2 + \sum_{i=r+1}^n(U^Tb)_i^2 \\ \end{aligned}
∥Ax−b∥2=∥UΣVTx−b∥2×∥UT∥2=1∥ΣVTx−UTb∥2=i=1∑r(σi(VTx)i−(UTb)i)2+i=r+1∑n(UTb)i2
当
σ
i
(
V
T
x
)
i
=
(
U
T
b
)
i
,
i
=
1
,
⋯
,
r
\sigma_i(V^Tx)_i = (U^Tb)_i,\quad i = 1,\cdots,r
σi(VTx)i=(UTb)i,i=1,⋯,r时，上式取最小值
即当
(
V
T
x
)
i
=
1
σ
i
(
U
T
b
)
i
(V^Tx)_i = \dfrac{1}{\sigma_i} (U^Tb)_i
(VTx)i=σi1(UTb)i时
即当
V
T
x
=
Σ
+
U
T
b
V^Tx=\Sigma^+U^Tb
VTx=Σ+UTb时
即当
x
=
V
Σ
+
U
T
b
x=V\Sigma^+U^Tb
x=VΣ+UTb时
其中
Σ
+
=
[
1
σ
1
0
⋯
0
0
1
σ
2
⋯
0
⋮
⋮
⋱
0
0
0
⋯
1
σ
r
0
]
∈
M
n
×
m
\Sigma^+ = \begin{bmatrix} \dfrac{1}{\sigma_1} & 0 & \cdots & 0 \\ 0 & \dfrac{1}{\sigma_2} & \cdots & 0 \\ \vdots & \vdots & \ddots & 0 \\ 0 & 0 & \cdots & \dfrac{1}{\sigma_r} \\ &&&&0 \end{bmatrix} \in M_{n\times m}
Σ+=⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡σ110⋮00σ21⋮0⋯⋯⋱⋯000σr10⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤∈Mn×m
因此：
A
+
=
V
Σ
+
U
T
A^+=V\Sigma^+U^T
A+=VΣ+UT
如果用几何推导版本的SVD，也可以写成：
A
+
=
V
D
−
1
U
T
A^+=VD^{-1}U^T
A+=VD−1UT