CS205A Lecture 6 Eigenproblems, How they arise, properties

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第六讲，这一讲主要介绍了特征向量的应用及其性质。

Chapter 5 特征向量

定义以及性质

首先给出如下定义：

定义5.1(特征值和特征向量)

$\vec x \neq \vec 0$是矩阵$A \in \mathbb C^{n\times n}$的特征向量，如果存在某个复数$\lambda$，使得$A\vec x = \lambda \vec x $，$\lambda $被称为特征值。

定义5.2(谱和谱半径)

矩阵$A$的谱是指$A$的特征值，谱半径$\rho(A)$是使得最大化$|\lambda |$的特征值$\lambda $。

如果$\vec x$是特征向量，其特征值为$\lambda $，那么显然有

$$A(c\vec x) = cA\vec x =c\lambda \vec x =\lambda(c\vec x)$$

所以不失一般性，我们可以假设特征向量都满足

$$||\vec x || =1$$

我们之前都默认特征向量存在，但是这个事实不是那么显然，需要简单说明：

引理5.1

$$每个矩阵A\in \mathbb R^{n\times n}都至少存在一个特征向量$$

课本上有一个证明，这里我给出自己的证明。

证明：首先对之前的等式移项：

$$(A-\lambda I) \vec x = 0$$

如果存在非零向量$\vec x$使得上述方程成立，那么显然有

$$|A-\lambda I|=0$$

所以我们先求解上述方程，由代数基本定理，至少存在一个复根$\lambda _1 $，那么我们求解方程

$$(A-\lambda_1 I)\vec x =0$$

注意由定义$|A-\lambda_1 I|=0$，所以上述方程必然有非零解，即存在特征向量。

引理5.2

$$属于不同特征值的特征向量必然线性无关$$

证明：设特征向量为$\vec x_1 ,…,\vec x_k$，对应的特征值为$\lambda_1,…,\lambda_k$，并且$\lambda_i \neq \lambda_j ,i\neq j​$。

然后使用反证法，如果上述结论不成立，那么上述特征向量线性相关，所以存在不全为$0$的$c_1,…,c_k​$，使得

$$\vec 0 =c_1\vec x_1 +...+c_k \vec x_k$$

不妨设$c_1\neq 0$，然后我们左乘矩阵

$$\prod_{i=2}^k(A-\lambda_i I)$$

可得

$$\begin{aligned} \vec 0 &= \Big(\prod_{i=2}^k(A-\lambda_i I)\Big)(c_1\vec x_1 +...+c_k \vec x_k)\\ &=\sum_{j=1}^k \Big(\prod_{i=2}^k(A-\lambda_i I)\Big) c_j \vec x_j \\ &=c_1 \Big(\prod_{i=2}^k(A-\lambda_i I)\Big) \vec x_1\\ &=c_1 \prod_{i=2}^k(\lambda_1 -\lambda_k) \vec x_1\\ &\neq \vec 0 \end{aligned}$$

这就产生了矛盾。

备注：第二个等号是由定义，第三个等号是由如下事实，

$$(A-\lambda_i I)\vec x_i =\vec 0$$

以及

$$(A-\lambda_i I)(A-\lambda_j I)= (A-\lambda_j I)(A-\lambda_i I)$$

最后一个等号利用到了

$$(A-\lambda_i I)\vec x_1 =(\lambda_1-\lambda_i)\vec x_1$$

定义5.3 (非退化)

$$如果矩阵A\in \mathbb R^{n\times n}的特征向量可以张成整个\mathbb R^n，那么该矩阵被称为非退化或可对角化$$

定义5.4 (相似矩阵)

$$矩阵A,B相似当且仅当存在可逆矩阵T使得B= TAT^{-1}$$

定义5.5 (共轭转置)

$$矩阵A\in \mathbb C^{m\times n}的共轭转置定义 A^H \triangleq \bar A^T$$

定义5.6 (厄米特矩阵)

$$如果A=A^H，那么称矩阵A\in \mathbb C^{n\times n}是厄米特矩阵$$

关于厄米特矩阵有如下重要性质：

引理5.3

$$厄米特矩阵的特征值都是实数$$

为了方便证明，这里定义一些记号：对于向量$\vec x ,\vec y \in \mathbb C^n$，定义内积

$$\langle \vec x, \vec y \rangle =\sum_{i=1}^n x_i \bar y_i$$

由定义，不难得到

$$\begin{aligned} \langle \vec x, \vec y \rangle &= \overline {\langle \vec y, \vec x \rangle } \\ \langle \lambda \vec x, \vec y \rangle &=\lambda\langle \vec x, \vec y \rangle \end{aligned}$$

证明：假设$A\in \mathbb C^{n\times n}$是厄米特矩阵，并且有

$$A\vec x =\lambda \vec x$$

不失一般性，这里假设

$$||\vec x || ^2=\langle \vec x ,\vec x \rangle =1$$

那么

$$\begin{aligned} \lambda & =\lambda \langle \vec x ,\vec x \rangle \\ &=\langle \lambda\vec x, \vec x \rangle\\ &=\langle A\vec x, \vec x \rangle\\ &=(A\vec x )^T {\vec{\bar x}} \\ &=\vec x ^T A^T {\vec{\bar x}} \\ &= \vec x ^T \overline {\bar A^T {\vec{x}}} \\ &=\vec x ^T \overline { A^H {\vec{ x}}} \\ &=\langle \vec x,A^H {\vec{ x}} \rangle \\ &=\langle \vec x,A {\vec{ x}} \rangle \\ &=\langle \vec x,\lambda {\vec{ x}} \rangle \\ &=\bar \lambda \langle \vec x,{\vec{ x}} \rangle \\ &=\bar \lambda \end{aligned}$$

引理5.4

$$厄米特矩阵不同特征值对应的特征向量正交$$

证明：设$A\in \mathbb C^{n\times n}​$是厄米特矩阵，并且对$\lambda \neq \mu​$，我们有

$$\begin{aligned} A\vec x &=\lambda \vec x \\ A\vec y &=\mu\vec y \end{aligned}$$

首先我们显然有

$$\langle A\vec x , \vec y \rangle =\lambda \langle \vec x , \vec y \rangle$$

此外，同之前的讨论，我们还有

$$\begin{aligned} \langle A\vec x,\vec y \rangle &=(A\vec x)^T\vec {\bar y}\\ &=\vec x^T A^T \vec {\bar y}\\ &=\vec x^T \overline { A^H {\vec{ y}}}\\ &=\langle \vec x,A\vec y \rangle \\ &=\mu \langle \vec x , \vec y \rangle \end{aligned}$$

所以

$$\lambda \langle \vec x , \vec y \rangle = \mu \langle \vec x , \vec y \rangle$$

因为

$$\lambda \neq \mu$$

所以

$$\langle \vec x , \vec y \rangle = 0$$

定理5.1 (谱定理)

$$任意厄米特矩阵A正交相似于对角阵，\\ 即存在对角阵D和正交矩阵X，使得\\ D=X^T AX$$

这个定理的证明省略。

引理5.5

$$半正定矩阵的特征值非负$$

证明：设$A\in \mathbb R^{n\times n}$是半正定矩阵，假设

$$A\vec x =\lambda \vec x$$

那么

$$\vec x^T A\vec x = \lambda \vec x ^T\vec x =\lambda ||\vec x ||^2 \ge 0 \\ \lambda \ge 0$$

应用

统计学

假设我们对$100$个病人收集了年龄，体重，血压和心率的数据，第$i$个病人的数据用$\vec x_i \in \mathbb R^4$表示。由医学知识可知，血压高的病人很可能有较大的体重，因此我们希望用低维的数据表示之前的信息，这里假设用一维数据表示。所以，我们希望数据平行于某个向量$\vec v $，从而$\vec x_i \approx c_i \vec v$，由上一讲的内容可得平行于$\vec v $方向关于$\vec x_i$的最佳近似为投影

$$\begin{aligned} \text{proj}_{\vec v} \vec x_i &=\frac{\vec x_i .\vec v}{\vec v.\vec v} \vec v \\ &= (\vec x_i . {\hat v}){\hat v} & 其中{\hat v}=\frac { \vec v }{||\vec v||} \end{aligned}$$

类似最小二乘法，我们有如下最小化问题：

$$\begin{aligned} \min &\ \sum_{i}||\vec x_i -\text{proj}_{\vec v} \vec x_i ||^2 \\ \text{s.t}& \ ||\hat v || =1 \end{aligned}$$

简化上式得到

$$\begin{aligned} \sum_{i}||\vec x_i -\text{proj}_{\vec v} \vec x_i ||^2 &=\sum_{i}||\vec x_i -(\vec x_i . {\hat v}){\hat v}||^2 \\ &=\sum_{i} (||\vec x_i||^2 -(\vec x_i . {\hat v})^2)\\ &=\text{const} - \sum_i (\vec x_i . {\hat v})^2\\ &=\text{const} - ||X^T \hat v ||^2\\ &=\text{const} - \hat v^T XX^T\hat v \end{aligned}$$

所以上述问题等价于如下问题

$$\begin{aligned} \max &\ \hat v^T XX^T \hat v \\ \text{s.t}& \ ||\hat v || =1 \end{aligned}$$

利用拉格朗日乘子法，可以将上述问题化为

$$XX^T \hat v =\lambda \hat v$$

这里就利用到了特征向量。

谱嵌入

考虑相似性度量问题，模型如下

$$E(\vec x ) =\sum_{i,j}w_{ij}(x_i -x_j)^2 \\ w_{ij}=w_{ji}$$

我们的目标是最小化上述式子，注意如果对$x$不加限制，那么最小值显然为$0$，所以增加限制：

$$||\vec x || ^2=1$$

但是只有一个限制依然不够，考虑

$$\vec x =(\frac 1 {\sqrt n},...,\frac 1 {\sqrt n})$$

最小值依然为$0$，所以这里再添加一个限制：

$$\vec 1^T \vec x = 0$$

所以最终的问题如下：

$$\begin{aligned} \min &\ E(\vec x ) \\ \text{s.t}& \ ||\vec x ||^2=\vec x^T \vec x =1 \\ & \ \vec 1^T \vec x=0 \end{aligned}$$

对$E(\vec x)$进行化简：

$$\begin{aligned} E(\vec x) &=\sum_{ij}w_{ij}(x_i-x_j)^2 \\ &=\sum_{ij}w_{ij}(x_i^2-2x_ix_j+x_j^2) \\ &=\sum_{ij}w_{ij}x_i^2-2\sum_{ij}w_{ij}x_ix_j +\sum_{ij}w_{ij}x_j^2 \\ &=\sum_{i}a_ix_i^2-2\sum_{ij}w_{ij}x_ix_j +\sum_{j}b_j x_j^2 \\ &a_i \triangleq \sum_{j}w_{ij},b_j \triangleq \sum_{i}w_{ij}， \text{diag}(A)= \vec a , \text{diag}(B)= \vec b,由对称性可得A=B\\ &=\vec x^T(A-2W+B)\vec x & \\ &=\vec x^T (2A-2W)\vec x\\ &\triangleq x^T M\vec x \end{aligned}$$

注意我们有

$$M\vec 1 = (2A-2W) \vec 1 =2(\vec a -\vec a )=\vec 0$$

所以$0$是$M$的特征值，且对应的特征向量为$\vec 1 $。

对之前的问题可以构造拉格朗日乘子：

$$L = \vec x^T M\vec x -\lambda (\vec x^T \vec x-1)-\mu \vec 1^T \vec x$$

关于$\vec x$求梯度，令其为$\vec 0$

$$\nabla_{\vec x} L =2M\vec x -2\lambda \vec x -\mu \vec 1 =\vec 0 \tag 1$$

关于$\vec 1$做内积可得

$$2M\vec 1^T\vec x -2\lambda\vec 1^T \vec x -\mu\vec 1^T \vec 1 = 0$$

由条件，我们有

$$\vec 1^T \vec x = 0$$

所以

$$\begin{aligned} -n\mu &= 0 \\ \mu &= 0 \end{aligned}$$

那么(1)变成

$$M\vec x =\lambda \vec x \tag 2$$

并且

$$\begin{aligned} E(\vec x )&=\vec x^T M\vec x \\ &=\lambda \vec x^T\vec x \\ &=\lambda \end{aligned}$$

所以原问题等价于求解(2)，即求解$M$对应的特征值。