网站前段打不开 后台也进不去,重庆建设网官网,蓝色大气企业网站源码,wordpress整合vip解析关于一个小小的PCA的推导 文章目录 关于一个小小的PCA的推导1 谱分解 (spectral decomposition)2 奇异矩阵(singular matrix)3 酉相似(unitary similarity)4 酉矩阵5 共轭变换6 酉等价7 矩阵的迹的计算以及PCA算法推导8 幂等矩阵(idempotent matrix)9 Von Neumanns 迹不等式 [w…关于一个小小的PCA的推导 文章目录 关于一个小小的PCA的推导1 谱分解 (spectral decomposition)2 奇异矩阵(singular matrix)3 酉相似(unitary similarity)4 酉矩阵5 共轭变换6 酉等价7 矩阵的迹的计算以及PCA算法推导8 幂等矩阵(idempotent matrix)9 Von Neumanns 迹不等式 [wiki链接](https://en.wikipedia.org/wiki/Trace_inequality#Von_Neumann.27s_trace_inequality)10 矩阵相似11 矩阵的特征值与特征向量12 正规矩阵13 正定矩阵、半正定矩阵正定矩阵 参考文献 如果有概念不懂请从目录中查找或者直接检索。 如果想直入主题请从第7小节开始看。 1 谱分解 (spectral decomposition)
矩阵中有一个概念叫做谱分解。
定理2.5.3 所以根据定理2.5.3的(a)(b)可知**正规矩阵(请看第12条都是酉可对角化unitarily diagonalizable)**的形式为存在一个酉矩阵V使得A V Λ V ∗ V \Lambda V^* VΛV∗, 并且 Λ d i a g ( λ 1 , … , λ n ) \Lambda diag (\lambda_1,\dots,\lambda_n) Λdiag(λ1,…,λn).
定理2.2.2 酉相似的两个矩阵的元素平方和相等。 由于酉相似的两个矩阵的元素平方和相等所以自然就可以得到性质c.
根据舒尔三角化定理任何复方阵都酉相似于一个三角阵该三角阵的对角元素为其特征值。则写出它的舒尔分解形式 A U T U ∗ A UTU^* AUTU∗, 其中 U [ u 1 , … , u n ] U [u_1,\dots, u_n] U[u1,…,un]是一个酉矩阵 T [ t i j ] ∈ M n T [t_{ij}]\in M_n T[tij]∈Mn是一个上三角矩阵。这样一个分解可以写成AU UT即A [ u 1 , … , u n ] [u_1,\dots,u_n] [u1,…,un] [ u 1 , … , u n ] [u_1,\dots,u_n] [u1,…,un]T, 而T是对角阵所以$Au_i t_{ii}u_i $ for each i 1 , … , n i 1,\dots,n i1,…,n, 因此 U U U的n个列是A的标准正交的特征向量。
根据矩阵分析第134页首次出现谱分解给出的定义来看谱分解的定义可以这么写 其中酉矩阵的n个列向量就是A的特征向量。
一个正规矩阵可以表示成一个酉矩阵、一个对角矩阵、以及该酉矩阵的共轭转置的乘积。这样一个分解称作该正规矩阵的谱分解。
谱分解中对角矩阵的对角元便是其特征值酉矩阵的列向量便是其对应的特征向量。
2 奇异矩阵(singular matrix)
一个线性变换或者矩阵被称之为nonsingular(非奇异)不奇怪如果这个变换仅对0这个输入产生0的输出否则它就是被称作singular(奇异)
对于这个概念我觉得很有意思。singular这个英文单词百度百科上的英文意思是奇怪的独特的独一无二的。根据上面的定义如果某个变换将一个非零的东西映射成了0则这个变换是很奇怪的是异常的。
我觉得称之为非比寻常也是可以的说明这样的变换具有一种超能力能将非零的东西变成零以至于独孤求败无人可比如果它是方阵则没有与之对应的逆矩阵。
方阵中哪些矩阵不平常呢
如果A是一个方阵则下列条件是等价的。
A是非奇异矩阵, 等价于该矩阵存在逆矩阵
等价于 Ax 0的有唯一解零向量
等价于 0肯定不是A的特征值因为矩阵的特征值的定义中需要从非零向量映射而非奇异矩阵无法将非零向量映射到零向量故0断然不是A的一个特征值
3 酉相似(unitary similarity)
定义对于酉矩阵来说酉矩阵的共轭转置即为其逆矩阵。所以存在一个相似变换其对应的矩阵为酉矩阵则称变换前后的两个矩阵是酉相似的。
性质 如果两个矩阵酉相似则两个矩阵的元素平方和相等即二者的共轭转置与原矩阵的乘积的迹相等。 tr B ∗ B tr A ∗ A \operatorname{tr} B^* B\operatorname{tr} A^* A trB∗BtrA∗A 如果某个矩阵酉相似于一个对角矩阵则称该矩阵是酉可对角化的。
舒尔定理
可能基本矩阵理论中最有用的一个事实要归于舒尔的一个定理任何复方阵都酉相似于一个三角阵该三角阵的对角元素是矩阵的特征值可以以任意特定的顺序排列。这就是大名鼎鼎的舒尔形式、舒尔三角化任何一个方阵都酉相似于一个对角线元素为该方阵的特征值的上三角矩阵。
4 酉矩阵
定义酉矩阵的逆矩阵是其共轭转置。
说明酉矩阵这一类矩阵的逆矩阵的形式简单就是其共轭转置。求共轭转置比求逆更加简单。
性质
酉矩阵是非奇异矩阵其逆矩阵就是其共轭转置。酉矩阵的行向量组和列向量组均是标准正交的。酉矩阵这个线性变换对向量是保持距离的即向量 x x x和向量 U x Ux Ux有相同的欧式范数。两个酉矩阵的乘积如果可以相乘仍为酉矩阵。
5 共轭变换
通过一个非奇异矩阵以及它的共轭转置来对一个矩阵进行映射这样的变换称作共轭变换形如 A → S ∗ A S A \rightarrow S^* A S A→S∗AS
6 酉等价
定义将一个矩阵通过两个酉矩阵变换到一个新的矩阵这样一个变换称作酉等价。
性质
每一个矩阵均酉等价于一个非负的对角阵该对角阵的元素为矩阵的奇异值。这些奇异值很重要。
7 矩阵的迹的计算以及PCA算法推导
在矩阵理论推导过程中经常会使用到矩阵的迹的计算方法所以掌握该类计算方法对于理论推导是大有裨益的。
设 B ∈ R d , n B \in \mathbb{R}^{d, n} B∈Rd,n , D ∈ R d , d D\in \mathbb{R}^{d,d} D∈Rd,d, 求 B T D B B^T D B BTDB的迹。
用到的一个技术叫做 分块矩阵中的列分块。
将矩阵进行分块可以简化计算。当然在分块计算时要先检查矩阵的行数与列数判断是否可以进行相乘
这里需要补充分块矩阵的相关知识。
https://baike.baidu.com/item/%E5%88%86%E5%9D%97%E7%9F%A9%E9%98%B5/10234479 分块矩阵百度百科链接
首先将B进行列分块 B [ b 1 , … , b n ] , b i ∈ R d B [b_1,\dots, b_n], b_i\in \mathbb{R}^d B[b1,…,bn],bi∈Rd
然后 看到这里就可以来进行PCA算法的证明了。
PCA算法是一个降维算法方法是使用一个线性变换将原来的高维空间的向量映射到一个低维空间。目标是找到这样一个线性变换即一个矩阵。要求是不仅能够将原始向量从高维空间映射到低维空间还要能够从低维空间映射回来所以这就又需要一个变换即又一个矩阵并且要求映射回来的向量与原始向量尽可能的逼近。
设 x 1 , … , x m x_1,\dots, x_m x1,…,xm为 R d \mathbb{R}^d Rd中的 m m m个向量, 我们要将其映射到 R n \mathbb{R}^n Rn中nd). 我们需要一个矩阵 W ∈ R n , d W \in \mathbb{R}^{n, d} W∈Rn,d将其映射过去 x ↦ W x \mathbf{x} \mapsto W \mathbf{x} x↦Wx 然后还需要一个矩阵 U ∈ R d , n U \in \mathbb{R}^{d, n} U∈Rd,n可以用来恢复每一个向量的压缩版本即对于一个压缩后的向量 y W x \mathbf{y}W \mathbf{x} yWx 我们可以构造 x ~ U y \tilde{\mathbf{x}}U \mathbf{y} x~Uy使得 x ~ U y \tilde{\mathbf{x}}U \mathbf{y} x~Uy位于原始高维空间 R d \mathbb{R}^d Rd, 且尽可能与原始向量之间的平方距离尽可能小就是下面这样一个优化问题 argmin W ∈ R n , d , U ∈ R d , n ∑ i 1 m ∥ x i − U W x i ∥ 2 2 \underset{W \in \mathbb{R}^{n, d}, U \in \mathbb{R}^{d, n}}{\operatorname{argmin}} \sum_{i1}^m\left\|\mathbf{x}_i-U W \mathbf{x}_i\right\|_2^2 W∈Rn,d,U∈Rd,nargmini1∑m∥xi−UWxi∥22 首先我们证明解集一定满足下面这种形式 U U U的列向量组是标准正交的且 W W W是 U U U的转置矩阵。 证明可参见矩阵分析引理23.1由于时间关系先放一放。
上述结论说明解集是引理23.1中满足条件的U,W组成的集合的子集。
于是上述优化问题可以将搜索范围进一步缩小 argmin U ∈ R d , n : U ⊤ U I ∑ i 1 ∥ x i − U U ⊤ x i ∥ 2 2 . \underset{U \in \mathbb{R}^{d, n}: U^{\top} UI}{\operatorname{argmin}} \sum_{i1}\left\|\mathbf{x}_i-U U^{\top} \mathbf{x}_i\right\|_2^2 . U∈Rd,n:U⊤UIargmini1∑ xi−UU⊤xi 22. 上述目标函数可以化为
由于矩阵的迹是一个线性算子所以累加符号可以与迹运算进行交换进一步将上述问题转化为 argmax U ∈ R d , n : U ⊤ U I trace ( U ⊤ ∑ i 1 m x i x i ⊤ U ) \underset{U \in \mathbb{R}^{d, n}: U^{\top} UI}{\operatorname{argmax}} \operatorname{trace}\left(U^{\top} \sum_{i1}^m \mathbf{x}_i \mathbf{x}_i^{\top} U\right) U∈Rd,n:U⊤UIargmaxtrace(U⊤i1∑mxixi⊤U) 令 A ∑ i 1 m x i x i ⊤ A\sum_{i1}^m \mathbf{x}_i \mathbf{x}_i^{\top} A∑i1mxixi⊤ 那么问题则转化为 argmax U ∈ R d , n : U ⊤ U I trace ( U ⊤ A U ) \underset{U \in \mathbb{R}^{d, n}: U^{\top} UI}{\operatorname{argmax}} \operatorname{trace}\left(U^{\top} A U\right) U∈Rd,n:U⊤UIargmaxtrace(U⊤AU) 如何求解该优化问题首先要能够对目标函数进行计算
可以验证矩阵A是对称矩阵而对称矩阵是正规矩阵正规矩阵又可以进行谱分解写出其谱分解形式 A V D V T A VDV^T AVDVT 其中 D D D为对角阵对角元素为 A A A的特征值 V V V为酉矩阵即 V V T V T V I VV^T V^TV I VVTVTVI, 且 V V V的列向量组为 A A A的特征向量。
则 trace ( U ⊤ A U ) trace ( U ⊤ V D V T U ) \operatorname{trace}\left(U^{\top} A U\right) \operatorname{trace}\left(U^{\top}VDV^T U\right) trace(U⊤AU)trace(U⊤VDVTU)
进行一个变量代换令 B V T U ∈ R d , n B V^T U \in \mathbb{R}^{d,n} BVTU∈Rd,n
于是便有了下面的推导
注经过一下演算通过半正定二次型的定义可知 A A A是半正定矩阵所以矩阵D的对角元素均非负。
主要思路是通过Von Neumann提出的埃尔米特半正定复方阵乘积的迹不等式。 8 幂等矩阵(idempotent matrix)
若一个矩阵是方阵且矩阵的平方仍为自己则称该方阵为幂等矩阵。顾名思义取幂仍为自己的矩阵称为幂等矩阵
性质
幂等矩阵的迹等于幂等矩阵的秩。幂等矩阵要么相似于对角元全为1或者0的对角阵。即对角阵的对角元的元素只能是0,1不会出现其他值。
9 Von Neumann’s 迹不等式 wiki链接
对于两个埃尔米特的n阶半正定复方阵A, 和B, 它们的特针织现在按照递减的顺序进行排列分别为 a 1 ≥ a 2 ≥ ⋯ ≥ a n a_1\ge a_2\ge\dots\ge a_n a1≥a2≥⋯≥an何 b 1 ≥ ⋯ ≥ b n b_1\ge\dots\ge b_n b1≥⋯≥bn,
则有 Tr ( A B ) ≤ ∑ i 1 n a i b i \operatorname{Tr}(A B) \leq \sum_{i1}^n a_i b_i Tr(AB)≤∑i1naibi
10 矩阵相似
如果两个矩阵相似则这两个矩阵有相同的特征值。
11 矩阵的特征值与特征向量
对于一个n阶矩阵A来说如果一个标量 λ \lambda λ和一个非零向量 x x x满足 A x λ x , x ∈ C n , x ≠ 0 , λ ∈ C Ax \lambda x, x\in C^n, x\ne 0, \lambda \in C Axλx,x∈Cn,x0,λ∈C 则 λ \lambda λ称为A的一个特征值 x x x称为A属于 λ \lambda λ的特征向量。 ( λ , x ) (\lambda, x) (λ,x)是矩阵 A A A的一个特征对。
特征值和特征向量从来都是成对出现的。
12 正规矩阵
正规矩阵是非常重要的一类矩阵它包括
酉矩阵、埃尔米特矩阵、斜埃尔米特矩阵(skew Hermitian)、实正交矩阵、实对称矩阵、实斜对称矩阵。
正规矩阵的定义 如果一个n维矩阵A满足它和它的共轭转置矩阵是可交换的则称该矩阵是正规矩阵。
正规矩阵的性质
13 正定矩阵、半正定矩阵
有一类埃尔米特矩阵它们有一个特殊的正的性质它们自然地出现在很多应用中。带有这种正性的埃尔米特矩阵也将正数推广到了矩阵上。这个观察经常为正定矩阵的应用和性质提供了新的视角。下面一些例子也展现了这种特殊的埃尔米特矩阵的出现的方式。
例如 Hessian矩阵、协方差矩阵等。
正定矩阵
定义:称一个埃尔米特矩阵是正定的如果对于任意的复数域上的非零向量其二次型均为正数则称该矩阵是正定矩阵。
同理如果二次型为非负数则称该矩阵为半正定矩阵。
参考文献
[1] https://math.stackexchange.com/questions/1902421/prove-that-the-trace-of-the-matrix-product-uau-is-maximized-by-setting-us
