PCA 主成分分析
问题定义:
若原始数据是 d 维的,我们希望找到一个压缩映射 W ∈ R n × d W \in \R^{n \times d} W∈Rn×d 和 一个重建映射 U ∈ R d × n U \in \R^{d \times n} U∈Rd×n,使得压缩数据在解压后与原数据的误差最小: (1) arg min U , W ∑ i = 1 m ∣ ∣ x i − U W x i ∣ ∣ \arg \min_{U,W} \sum_{i=1}^m||x_i - UWx_i||\tag{1} argU,Wmini=1∑m∣∣xi−UWxi∣∣(1)其中,m 为数据量。
引理
若 (U,W) 为上述问题的最优解,则 U 的列是正交归一的( U T U = I n U^TU = I_n UTU=In),且 W = U T W = U^T W=UT。
根据上述引理,原问题变成 (2) arg min U ∈ R d × n ; U T U = I n ∑ i = 1 m ∣ ∣ x i − U U T x i ∣ ∣ \arg \min_{U \in \R^{d \times n}; U^TU = I_n} \sum_{i=1}^m||x_i - UU^Tx_i||\tag{2} argU∈Rd×n;UTU=Inmini=1∑m∣∣xi−UUTxi∣∣(2)
变形
∑
i
=
1
m
∣
∣
x
i
−
U
U
T
x
i
∣
∣
=
∑
i
=
1
m
(
x
i
−
U
U
T
x
i
)
T
(
x
i
−
U
U
T
x
i
)
=
∑
i
=
1
m
(
x
i
T
x
i
−
2
x
i
T
U
U
T
x
i
+
x
i
T
U
U
T
U
U
T
x
i
)
=
∑
i
=
1
m
(
x
i
T
x
i
−
x
i
T
U
U
T
x
i
)
=
∑
i
=
1
m
x
i
T
x
i
−
∑
i
=
1
m
t
r
a
c
e
{
x
i
T
U
U
T
x
i
}
=
∑
i
=
1
m
x
i
T
x
i
−
∑
i
=
1
m
t
r
a
c
e
{
U
U
T
x
i
x
i
T
}
=
∑
i
=
1
m
x
i
T
x
i
−
t
r
a
c
e
{
U
U
T
∑
i
=
1
m
x
i
x
i
T
}
(
记
X
=
∑
i
=
1
m
x
i
x
i
T
)
=
∑
i
=
1
m
x
i
T
x
i
−
t
r
a
c
e
{
U
T
X
U
}
\sum_{i=1}^m||x_i - UU^Tx_i|| \\=\sum_{i=1}^m(x_i - UU^Tx_i)^T(x_i - UU^Tx_i) \\= \sum_{i=1}^m(x_i^Tx_i -2x_i^TUU^Tx_i +x_i^TUU^TUU^Tx_i) \\= \sum_{i=1}^m(x_i^Tx_i -x_i^TUU^Tx_i ) \\= \sum_{i=1}^mx_i^Tx_i - \sum_{i=1}^mtrace\{x_i^TUU^Tx_i \} \\= \sum_{i=1}^mx_i^Tx_i - \sum_{i=1}^mtrace\{UU^Tx_ix_i^T \} \\= \sum_{i=1}^mx_i^Tx_i - trace\{UU^T\sum_{i=1}^mx_ix_i^T \} \\(记 X = \sum_{i=1}^mx_ix_i^T) \\=\sum_{i=1}^mx_i^Tx_i - trace\{U^TXU\}
i=1∑m∣∣xi−UUTxi∣∣=i=1∑m(xi−UUTxi)T(xi−UUTxi)=i=1∑m(xiTxi−2xiTUUTxi+xiTUUTUUTxi)=i=1∑m(xiTxi−xiTUUTxi)=i=1∑mxiTxi−i=1∑mtrace{xiTUUTxi}=i=1∑mxiTxi−i=1∑mtrace{UUTxixiT}=i=1∑mxiTxi−trace{UUTi=1∑mxixiT}(记X=i=1∑mxixiT)=i=1∑mxiTxi−trace{UTXU}所以,问题 (2) 等价于
arg
max
U
∈
R
d
×
n
;
U
T
U
=
I
n
t
r
a
c
e
{
U
T
X
U
}
\arg \max_{U \in \R^{d \times n}; U^TU = I_n} trace\{U^TXU\}
argU∈Rd×n;UTU=Inmaxtrace{UTXU}等价于
arg
max
u
i
⊥
u
j
;
∣
∣
u
i
∣
∣
=
1
∑
i
=
1
n
u
i
T
X
u
i
\arg \max_{u_i \perp u_j; ||u_i||=1}\sum_{i=1}^n u_i^TXu_i
argui⊥uj;∣∣ui∣∣=1maxi=1∑nuiTXui
显然,该问题的最优解为 X 的前 n 大的特征值对应的特征向量。此时,
max
u
i
⊥
u
j
;
∣
∣
u
i
∣
∣
=
1
∑
i
=
1
n
u
i
T
X
u
i
=
∑
i
=
1
n
λ
[
i
]
\max_{u_i \perp u_j; ||u_i||=1}\sum_{i=1}^n u_i^TXu_i \\ =\sum_{i=1}^n \lambda_{[i]}
ui⊥uj;∣∣ui∣∣=1maxi=1∑nuiTXui=i=1∑nλ[i]其中,
λ
[
i
]
\lambda_{[i]}
λ[i] 表示 第 i 大的特征值。
根据 X X T 和 X T X XX^T 和 X^TX XXT和XTX 的特征向量之间的关系,可以做一些优化: