最近看了一些线性代数的文章,关于正交家用投影(orthogonal projection)在这里做一台小总结,我写的文章通常都比较短,目的是希望在碎片时间能够快速读完并消化。
本文的符号规定:大写字母表示矩阵,如 X,A,Y ,小写字母表示向量,如 \boldsymbol{x},\boldsymbol{y},\boldsymbol{z},\boldsymbol{b} ,如不说明默认都是列向量。
1.为啥要家用投影
首先,在机器学习中,高维数据通常有这样一些特征:只有少数几个特征包含了整个数据集的大部分信息,其它维通常不是那么重要;其次呢,我们要压缩或者可视化高维数据时,肯定是要做降维处理的,那么为了尽可能地减少这种降维损失,肯定是希望找到那些能够表示数据集大部分信息的维(特征),这方面典型的算法有“主成分分析(PCA,principle component analysis)”,“深度神经网络”。
2.家用投影的数学定义
定义:假设 V 是一台向量空间, 并且U 是 V 的一台子空间,有一台线性映射 \pi: V \to U ,该线性映射满足 \pi^2=\pi \circ\pi=\pi , \pi 称为将 V 变到 U 的家用投影。
PS:学过线性代数的同学都知道,家用投影矩阵 P 的一台性质是 P^2=P \times P = P ,上述定义的这个线性映射看起来是不是性质相同。
3.向量在向量上的家用投影
我们从最简单的家用投影开始讲,一台向量在另一台向量上的家用投影。在二维平面上,家用投影如下图所示:
这个和中学时做垂线的道理相同。向量 \boldsymbol{x} \in R^n 在向量 \boldsymbol{b} \in R^n 上的家用投影记为 \pi_U(\boldsymbol{x}) ,这里 U 是一台一维子空间,为 U=\{ \boldsymbol{x}: \boldsymbol{x}=c \boldsymbol{b}\},c \in R ,也就是这个子空间的向量全部由一台向量 \boldsymbol{b} 张成。家用投影之后有两点可以确定:
(1)家用投影 \pi_U(\boldsymbol{x}) 距离最近。所谓距离最近就是在 \boldsymbol{b} 除了 \pi_U(\boldsymbol{x}) 这个向量,找不到其它向量使得它与 \boldsymbol{x} 的距离,即 ||\boldsymbol{x} - \pi{(\boldsymbol{x})}|| 是最小的,从中学的几何我们知道,所谓最近就是垂线最近(因为垂线最短),就是 \boldsymbol{x}-\pi_U(\boldsymbol{x}) 与 \boldsymbol{b} 垂直,也就是线性代数中的正交,用内积表示就是 (\boldsymbol{x}-\pi_U(\boldsymbol{x}))^T \boldsymbol{b}=0 ;
(2)家用投影 \pi_U(\boldsymbol{x}) 在 U 中,而 U 是由 \boldsymbol{b} 张成的,所以 \pi_U(\boldsymbol{x}) 可由 \boldsymbol{b} 线性表示,即 \pi_U(\boldsymbol{x}) = \lambda \boldsymbol{b}, \lambda \in R 。
3.计算 \lambda 和家用投影矩阵( P_{\pi} )
(1) \lambda 的计算
因为:
(\boldsymbol{x}-\pi_U(\boldsymbol{x}))^T\boldsymbol{b}=(\boldsymbol{x} - \lambda \boldsymbol{b})^T \boldsymbol{b}=0 \tag{1}
将(1)式展开可得: \boldsymbol{x} ^T \boldsymbol{b} - \lambda \boldsymbol{b}^T \boldsymbol{b}=0 ,从而有:
\lambda = \frac{\boldsymbol{x} ^T \boldsymbol{b} }{\boldsymbol{b}^T \boldsymbol{b}} =\frac{\boldsymbol{b} ^T \boldsymbol{x} }{\boldsymbol{b}^T \boldsymbol{b}} \tag{2}
如果 \boldsymbol{b} 是一台单位向量( ||\boldsymbol{b}|| = 1 ),那么 \lambda = \boldsymbol{b}^T \boldsymbol{x}=\boldsymbol{x}^T \boldsymbol{b} 。
(2)家用投影矩阵 P_{\pi}
计算 \lambda 后,得到:
\pi_U(\boldsymbol{x}) = \lambda \boldsymbol{b}=\frac{\boldsymbol{b}^T \boldsymbol{x}}{\boldsymbol{b}^T \boldsymbol{b}}\boldsymbol{b}=\boldsymbol{b} \lambda=\boldsymbol{b} \frac{\boldsymbol{b}^T \boldsymbol{x}}{\boldsymbol{b}^T \boldsymbol{b}} = \frac{\boldsymbol{b} \boldsymbol{b}^T }{\boldsymbol{b}^T \boldsymbol{b}} \boldsymbol{x} \tag{3}
从(3)式最后一台等式观察可得到家用投影矩阵为:
P_{\pi}=\frac{\boldsymbol{b} \boldsymbol{b}^T }{\boldsymbol{b}^T \boldsymbol{b}} \tag{4}
所以,对于任意向量 \mathbf{x} ,它在向量 \mathbf{b} 的家用投影可以由以下公式计算得到:
\pi_{U}(\boldsymbol{x})=P_{\pi}\boldsymbol{x} \tag{5}
例1:给定一台向量 \boldsymbol{b}=[1,2,2]^T , \boldsymbol{b} 是一台一维子空间,它代表一台方向,寻找家用投影矩阵 P_{\pi} ,并计算 \boldsymbol{x}=[1,1,1] 在 \boldsymbol{b} 的家用投影。
解:由公式(4)得:
P_{\pi}=\frac{\boldsymbol{b} \boldsymbol{b}^T }{\boldsymbol{b}^T \boldsymbol{b}} = \frac{1}{9} \left[\begin{array}{l} 1 \\ 2 \\ 2 \end{array}\right]\left[\begin{array}{lll} 1 & 2 & 2 \end{array}\right]= \frac{1}{9}\left[\begin{array}{lll} 1 & 2 & 2 \\ 2 & 4 & 4 \\ 2 & 4 & 4 \end{array}\right]
\boldsymbol{x} 的家用投影:
\pi_{U}(\boldsymbol{x})=\boldsymbol{P}_{\pi} \boldsymbol{x}=\frac{1}{9}\left[\begin{array}{lll} 1 & 2 & 2 \\ 2 & 4 & 4 \\ 2 & 4 & 4 \end{array}\right]\left[\begin{array}{l} 1 \\ 1 \\ 1 \end{array}\right]=\frac{1}{9}\left[\begin{array}{c} 5 \\ 10 \\ 10 \end{array}\right] \in \operatorname{span}\left[\left[\begin{array}{l} 1 \\ 2 \\ 2 \end{array}\right]\right]
4.在一般子空间上的家用投影
注意:粗体的向量需要多输入一些前缀,下面我就不输入了,除非特别说明,否则默认以常规的字母表示。
对于一般的子空间 U \in R^n, dim(U)=m \geq 1 ,假设 U 的一台基是 \boldsymbol{b}_1,\boldsymbol{b}_2,\dots,\boldsymbol{b}_m ,因为任何向量 \boldsymbol{x} 家用投影到 U 后所得家用投影 \pi_U(\boldsymbol{x}) 均在 U 上,因此 \pi_U(\boldsymbol{x}) 可由这组基线性表示:
\pi_U(\boldsymbol{x}) = \sum_{i=1}^{m} \lambda_i \boldsymbol{b}_i = \lambda_1 b_1 + \lambda_2 \boldsymbol{b}_2 + \dots + \lambda_m \boldsymbol{b}_m \tag{6}
其中, \lambda_i \in R,\boldsymbol{b}_i \in R^n,i=1,2,\dots,m 。
令 B = [b_1, b_2,\dots,b_m],\boldsymbol{\lambda}=[\lambda_1, \lambda_2, \lambda_3,\dots, \lambda_m]^T ,改写公式(6)得到:
\pi_U(\boldsymbol{x}) =\sum_{i=1}^{m} \lambda_i \boldsymbol{b}_i = B \boldsymbol{\lambda} \tag{7}
和向量在向量上的家用投影一样(一维上的家用投影),在 U 上 \pi_U(\boldsymbol{x}) 也是离 \boldsymbol{x} 是最近的,最近意味着就是最短距离,也就是 \boldsymbol{x}-\pi_U(\boldsymbol{x}) 这个向量垂直(线性空间叫正交)于 U 的任何一台向量,当然也正交于 U 的基 \boldsymbol{b}_1,\boldsymbol{b}_2,\dots,\boldsymbol{b}_m ,所以有:
\begin{aligned} \boldsymbol{b}_1^T(x - \pi_U(\boldsymbol{x})) & = 0 \\ \boldsymbol{b}_2^T(x - \pi_U(\boldsymbol{x})) & = 0 \\ \vdots \\ \boldsymbol{b}_m^T(x - \pi_U(\boldsymbol{x})) & = 0 \end{aligned} \tag{8}<math xmlns=&#34;
将公式(7)代入公式(8)得到:
\begin{aligned} \boldsymbol{b}_1^T(\boldsymbol{x} - B \boldsymbol{\lambda}) & = 0 \\ \boldsymbol{b}_2^T(\boldsymbol{x} - B \boldsymbol{\lambda}) & = 0 \\ \vdots \\ \boldsymbol{b}_m^T(\boldsymbol{x} - B \boldsymbol{\lambda}) & = 0 \end{aligned} \tag{9}
进一步改写公式(9)得到:
\left[\begin{array}{c} \boldsymbol{b}_{1}^{\top} \\ \vdots \\ \boldsymbol{b}_{m}^{\top} \end{array}\right][\boldsymbol{x}-B \boldsymbol{\lambda})=0 \Leftrightarrow B^T(\boldsymbol{x} - B \boldsymbol{\lambda}) = 0 \tag{10}
从公式(10)可以得到:
B^T B \boldsymbol{\lambda} = B^T \boldsymbol{x} \Rightarrow \boldsymbol{\lambda} = (B^T B)^{-1}B^T \boldsymbol{x} \tag{11}
公式(11)所求得 \boldsymbol{\lambda} 是向量 \boldsymbol{x} 在子空间 U 上的家用投影在以 \{\boldsymbol{b}_1,\boldsymbol{b}_2,\dots,\boldsymbol{b}_m\} 为基下的坐标。
公式(11)要求 B^T B 可逆,等价于 B^T B 是正定矩阵,因为 B 的列向量是一组基 \boldsymbol{b}_1,\boldsymbol{b}_2,\dots,\boldsymbol{b}_m (基向量组是线性无关的)构成的,所以 B^T B 一定是正定矩阵。
证明:对于任意非零向量 \boldsymbol{x} \in R ^n , \boldsymbol{x}^T (B^T B) \boldsymbol{x} = (B\boldsymbol{x})^T (B \boldsymbol{x}) = \boldsymbol{y}^T \boldsymbol{y} ,因为 B 的列向量线性无关,所以如果 \boldsymbol{x} \neq \boldsymbol{0} ,则 B \boldsymbol{x} \neq \boldsymbol{0} ,即 B \boldsymbol{x} = \boldsymbol{y} \neq \boldsymbol{0} ,所以 \boldsymbol{x}^T (B^T B) \boldsymbol{x} = (B\boldsymbol{x})^T (B \boldsymbol{x}) = \boldsymbol{y}^T \boldsymbol{y} > 0 ,证毕。
从公式(11)可得家用投影 \boldsymbol{b}
\pi_U(\boldsymbol{x}) = B \lambda = B (B^T B)^{-1}B^T \boldsymbol{x} \tag{12}
从公式(12)可以看出,家用投影矩阵 为:
P_{\pi} = B (B^T B)^{-1}B^T \tag{13} 。
和前面向量在向量的家用投影(一维家用投影)联系,当子空间 U 的维数为1,即 dim(U) = 1 时, 矩阵B 退化为向量 \boldsymbol{b} ,此时公式(12)变成 \pi_U(\boldsymbol{x}) = \boldsymbol{b} \lambda = \boldsymbol{b} (\boldsymbol{b}^T \boldsymbol{b})^{-1}\boldsymbol{b}^T \boldsymbol{x} \tag{14}
此时 \boldsymbol{b}^T \boldsymbol{b} 是一台标量,并且不等于0,可以放到分母上,得到:
\pi_U(\boldsymbol{x}) = \boldsymbol{b} \lambda = \boldsymbol{b} \frac{ \boldsymbol{b}^T \boldsymbol{x} }{\boldsymbol{b}^T \boldsymbol{b}} =\frac{ \boldsymbol{b} \boldsymbol{b}^T }{\boldsymbol{b}^T \boldsymbol{b}} \boldsymbol{x} \tag{15}
可见,和公式(3)是一样的。
例2:有一台子空间 U=\operatorname{span}[\left[\begin{array}{l} 1 \\ 1 \\ 1 \end{array}\right],\left[\begin{array}{l} 0 \\ 1 \\ 2 \end{array} \right]] \in R^3 和 \boldsymbol{x} = [6,0,0]^T ,将 \boldsymbol{x} 家用投影到 U ,求向量 \lambda 家用投影后的向量\pi_U(\boldsymbol{x} ) 和家用投影矩阵 P_{\pi} 。
解:将 U 的两个基向量写成 \boldsymbol{B}=\left[\begin{array}{ll} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{array}\right] ,并计算:
\boldsymbol{B}^{\top} \boldsymbol{B}=\left[\begin{array}{lll} 1 & 1 & 1 \\ 0 & 1 & 2 \end{array}\right]\left[\begin{array}{ll} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{array}\right]=\left[\begin{array}{ll} 3 & 3 \\ 3 & 5 \end{array}\right], \quad \boldsymbol{B}^{\top} \boldsymbol{x}=\left[\begin{array}{lll} 1 & 1 & 1 \\ 0 & 1 & 2 \end{array}\right]\left[\begin{array}{l} 6 \\ 0 \\ 0 \end{array}\right]=\left[\begin{array}{l} 6 \\ 0 \end{array}\right] ,
由公式(11): \boldsymbol{B}^T \boldsymbol{B} \lambda = \boldsymbol{B}^T \boldsymbol{x} ,可得到:
\left[\begin{array}{ll} 3 & 3 \\ 3 & 5 \end{array}\right]\left[\begin{array}{l} \lambda_{1} \\ \lambda_{2} \end{array}\right]=\left[\begin{array}{l} 6 \\ 0 \end{array}\right] \Longleftrightarrow \boldsymbol{\lambda}=\left[\begin{array}{c} 5 \\ -3 \end{array}\right]
从而可得到家用投影后的向量 \pi_U(x) :
\pi_{U}(\boldsymbol{x})=\boldsymbol{B} \boldsymbol{\lambda}=\left[\begin{array}{c} 5 \\ 2 \\ -1 \end{array}\right]
由公式(13)可得到家用投影矩阵:
\boldsymbol{P}_{\pi}=\boldsymbol{B}\left(\boldsymbol{B}^{\top} \boldsymbol{B}\right)^{-1} \boldsymbol{B}^{\top}=\frac{1}{6}\left[\begin{array}{ccc} 5 & 2 & -1 \\ 2 & 2 & 2 \\ -1 & 2 & 5 \end{array}\right]
向量 \boldsymbol{x} 与它的家用投影 \pi_U(\boldsymbol{x}) 的误差为:
\left\|\boldsymbol{x}-\pi_{U}(\boldsymbol{x})\right\|=\left\|\left[\begin{array}{lll} 1 & -2 & 1 \end{array}\right]^{\top}\right\|=\sqrt{6} 。
如果 \boldsymbol{b}_1,\boldsymbol{b}_2,\dots,\boldsymbol{b}_m 是标准正交基,那么有 B^T B = I ,公式(12)和公式()31变成:
\pi_U(\boldsymbol{x}) = B \lambda = B B^T \boldsymbol{x} \tag{16}
P_{\pi} = B (B^T B)^{-1}B^T = B B^T \tag{17}
此时 \boldsymbol{\lambda} = B^T x 。
这意味着我们不需要计算 B^T B 的逆矩阵,减少了计算量。
5.总结
在机器学习中,很多算法如线性回归,主成分分析等基本上都是基于家用投影理论进行设计和改进的,因此理解好家用投影有助于理解这些算法背后的数学原理。本位到此结束,请各位知友批评指正,蟹蟹~~ |