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 $,那么显然有

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

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

引理5.1

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

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

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

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

注意由定义$|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​$,使得

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

可得

这就产生了矛盾。

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

以及

最后一个等号利用到了

定义5.3 (非退化)

定义5.4 (相似矩阵)

定义5.5 (共轭转置)

定义5.6 (厄米特矩阵)

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

引理5.3

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

由定义,不难得到

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

不失一般性,这里假设

那么

引理5.4

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

首先我们显然有

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

所以

因为

所以

定理5.1 (谱定理)

这个定理的证明省略。

引理5.5

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

那么

应用

统计学

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

类似最小二乘法,我们有如下最小化问题:

简化上式得到

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

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

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

谱嵌入

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

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

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

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

所以最终的问题如下:

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

注意我们有

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

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

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

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

由条件,我们有

所以

那么(1)变成

并且

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

本文标题:CS205A Lecture 6 Eigenproblems, How they arise, properties

文章作者:Doraemonzzz

发布时间:2019年03月28日 - 01:30:00

最后更新:2019年03月28日 - 02:27:27

原始链接:http://doraemonzzz.com/2019/03/28/CS205A Lecture 6 Eigenproblems; How they arise, properties/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。