如何在分块矩阵中计算伪逆? - 问题详细说明
矩阵的伪逆
已知样本集合 S = { ( x i , y i ) ∣ i = 1 , 2 , … , N } S=\{(x_i, y_i)|i=1,2,\ldots,N\} S={(xi,yi)∣i=1,2,…,N}, x ∈ R d , y ∈ R l x\in R^d, y\in R^{l} x∈Rd,y∈Rl。
特征矩阵 X ∈ R N × d X\in R^{N\times d} X∈RN×d,输出矩阵为 Y ∈ R N × l Y\in R^{N \times l} Y∈RN×l,需要学习的矩阵为 W ∈ R d × l W\in R^{d\times l} W∈Rd×l。
根据原问题:
Y
=
X
W
Y = XW
Y=XW
可得:
W
=
X
†
Y
W = X^\dagger Y
W=X†Y
其中
X
†
X^\dagger
X† 表示
X
X
X 的伪逆。
当 X X X列满秩时i, X † = ( X ⊤ X ) − 1 X T X^\dagger = (X^\top X)^{-1}X^T X†=(X⊤X)−1XT;否则根据岭回归算法, X † = ( X ⊤ X + β I ) − 1 X T X^\dagger = (X^\top X + \beta I)^{-1}X^T X†=(X⊤X+βI)−1XT。
增量学习
当我们有了数据 X X X和标签 Y Y Y,求出了 W = X † Y W= X^\dagger Y W=X†Y,系统就可以运行了:来了新的输入 x ∈ R d x\in R^d x∈Rd,计算输出 y = x W y = xW y=xW。
现在突然要给原数据增加一个维度,即新增一种特征,使得新的特征矩阵变成 X + = [ X ∣ a ] ∈ R N × ( d + 1 ) X_{+}= [X|a] \in R^{N \times (d+1)} X+=[X∣a]∈RN×(d+1)。
这样一来原来算好的 W W W 就不能用了,只能重新算过 W + = X + † Y W_+ = X_+^\dagger Y W+=X+†Y 。
问题就在于计算 X + † X_+^\dagger X+†,如果你直接用岭回归计算,不叫增量学习。
有没有办法利用之前的计算结果 X † X^\dagger X† 来计算新的 X + † X_+^\dagger X+† 呢?这就是我接下来要介绍的内容:分块矩阵的伪逆。
????
我们现在唯一知道的就是: I d + 1 = X + † X + = X + † [ X ∣ a ] I_{d+1} = X_+^\dagger X_+ = X_+^\dagger [X|a] Id+1=X+†X+=X+†[X∣a]
已知
X
+
†
∈
R
(
d
+
1
)
×
N
X_+^\dagger\in R^{(d+1)\times N}
X+†∈R(d+1)×N,不妨假设
X
+
†
=
[
A
b
⊤
]
(
d
+
1
)
×
N
X_+^\dagger = \left[ \begin{array}{l} A \\ b^\top \end{array} \right]_{(d+1)\times N}
X+†=[Ab⊤](d+1)×N
其中
A
∈
R
d
×
N
,
b
∈
R
N
×
1
A\in R^{d\times N}, b\in R^{N \times 1}
A∈Rd×N,b∈RN×1。因为
A
A
A和
X
†
X^\dagger
X†的维数是相同的,不妨假设
A
=
X
†
−
C
A = X^\dagger -C
A=X†−C。
现在
X
+
†
=
[
X
†
−
C
b
⊤
]
(
d
+
1
)
×
N
X_+^\dagger = \left[ \begin{array}{l} X^\dagger -C \\ b^\top \end{array} \right]_{(d+1)\times N}
X+†=[X†−Cb⊤](d+1)×N
现在问题转化成求出合适的 C , b C, b C,b
根据伪逆的定义,
X
+
†
X
+
=
I
X_+^\dagger X_+ = I
X+†X+=I即
[
X
†
−
C
b
⊤
]
[
X
a
]
=
[
X
†
X
−
C
X
X
†
a
−
C
a
b
⊤
X
b
⊤
a
]
=
I
\left[ \begin{array}{l} X^\dagger -C \\ b^\top \end{array} \right] \left[ \begin{array}{l} X &a \end{array} \right] = \left[ \begin{array}{l} X^\dagger X -CX & X^\dagger a-Ca \\ b^\top X & b^\top a \end{array} \right]= I
[X†−Cb⊤][Xa]=[X†X−CXb⊤XX†a−Cab⊤a]=I
得出以下结论:
X
†
X
−
C
X
=
I
⇒
C
X
=
0
(
1
)
X
†
a
−
C
a
=
0
(
2
)
b
⊤
X
=
0
(
3
)
b
⊤
a
=
1
(
4
)
\begin{array}{lr} X^\dagger X -CX = I \Rightarrow CX=0& (1)\\ X^\dagger a-Ca = 0 & (2)\\ b^\top X = 0 & (3)\\ b^\top a = 1 & (4) \end{array}
X†X−CX=I⇒CX=0X†a−Ca=0b⊤X=0b⊤a=1(1)(2)(3)(4)
由(1)(3)可知,
∀
C
=
c
b
⊤
,
c
∈
R
d
\forall C=cb^\top, c\in R^d
∀C=cb⊤,c∈Rd,只要(3)满足,就有(1)满足。
把
C
=
c
b
⊤
C = cb^\top
C=cb⊤ 带入(2),并利用条件(4),可得:
X
†
a
−
c
b
⊤
a
=
X
†
a
−
c
=
0
⇒
c
=
X
†
a
X^\dagger a-cb^\top a = X^\dagger a-c=0 \Rightarrow c=X^\dagger a
X†a−cb⊤a=X†a−c=0⇒c=X†a
到这里我们已经成功了一半,因为
C
C
C 已经解出来了:
C
=
X
†
a
b
⊤
C = X^\dagger a b^\top
C=X†ab⊤
行百里者半九十,做出一半和啥也没做是一样的!我们继续来求 b b b。
我们现有的条件是等式(3)(4),你能想到答案了吗?
不能?
好吧,现在看着这张图告诉我,满足
b
⊤
X
=
0
(
3
)
b
⊤
a
=
1
(
4
)
\begin{array}{lr} b^\top X = 0 & (3)\\ b^\top a = 1 & (4) \end{array}
b⊤X=0b⊤a=1(3)(4) 的
b
b
b 是什么?
b
=
r
r
⊤
r
,
其中
r
=
a
−
X
X
†
a
b = \frac{r}{r^\top r}, \quad \text{其中} \quad r = a-XX^\dagger a
b=r⊤rr,其中r=a−XX†a
懂了吧!
那你要是问我: r = 0 r=0 r=0 怎么办?
r = 0 r=0 r=0 说明 a a a 正好落在 X X X 的列空间里,那么你把 X X X 扩展成 X + = [ X ∣ a ] X_+=[X | a] X+=[X∣a] 的意义何在?
最后,
W
+
=
X
+
†
Y
=
[
W
−
d
b
T
Y
b
⊤
Y
]
W_+ = X_+^\dagger Y=\left[ \begin{array}{l} W-db^TY \\ b^\top Y \end{array} \right]
W+=X+†Y=[W−dbTYb⊤Y]
先算
b
⊤
Y
b^\top Y
b⊤Y, 再算
W
+
W_+
W+,效率奇高。
上一篇: 在R语言中如何求解矩阵的逆矩阵?
下一篇: 用Unity制作卡通风格的游戏画面