正规矩阵的谱分解
, .
?
,  ,
.  ,   A                                                   ,
A   ()  . Gauss
.                    m  × n   A   B             P                       Q
Ir 0
B  = P AQ.   r (A) = r , A                       .  Ax = b
0  0
P Ax = P b, x = Qy,
Ir 0
y = P b.                        (4.0.1)
0  0
(4.0.1)  .                            ,  A   A  =
1  Ir  0   1
P          Q   .
0  0
,  ,
.                                ,
Schur , Cholesky LU  ,  (QR )
.    , ,
.
Schur , ,
.    () ,
,  .
,
4.1.1     A  ⇐⇒                   AA  = A  A.
Schur ,  U   U AU  = T                           .             AA      =
A  A ⇐⇒  T T = T  T .  A .
, A , U   U AU  = D
,
AA   = (UDU  )(UD  U ) = UDD  U = (UD  U )(UDU  ) = A  A.
.   A = (aij ), aij       = 0, i > j.  AA   = A  A,
,
a11a11 + a12a12 + · · · + a1n a1n  = a11a11 ,
A  0.  A .
, :
104
n n
4.1.1     A ∈ C      , AA    = A  A,  A .
, , , Hermite , Hermite ,
.  , A , A .
1 1  0
4.1.1    0       1  1  .
1 0  1
4.1.1
4.1.1     A , A , A .
4.1.2    1       1  , 4.1.1,  .                                 ,

文章目录
先修知识: 幂等矩阵
谱分解定理
谱分解的流程
谱分解的推论
谱分解的应用

先修知识: 幂等矩阵

谱分解定理






谱分解的流程

谱分解的推论





谱分解的应用

syms p real;  %定义实数p

A = [ ]; %输入一个矩阵A

[V,D] = eig(A)  %A的特征值为D的对角线元素，V的列向量为其对应的特征向量

simplify(VDinv(V));  %通过特征值和特征向量求出矩阵

O = orth(V);  %将特征向量正交规范化

[la,lb,lc,ld] = deal(D(1,1),D(2,2),D(3,3),D(4,4));  %将特征值赋值给la，lab，lc，ld

[a,b,c,d] = deal(O(:,1),O(:,2),O(:,3),O(:,4));  %将正交规范化后的特征向量赋值给a，b，c，d

simplify(laaa’ + lbbb’ + lccc’ + lddd’)  %a’为a的共轭转置，|a>’=<a|

文章目录
拉普拉斯矩阵的谱分解
谱图卷积
线性模型
参考


图卷积的核心思想是消息传递，怎么传递，主要依赖与其他节点的关系，具体来说：图中的每个节点通过卷积的形式将消息传递给邻居并接收邻居传来的消息，它们无时无刻不因为邻居和更远的点的影响而改变着自己的状态直到最终的平衡，关系越近的邻居影响越大。怎么定义与邻居的关系，以及怎么传播这是两个关键的问题。直接一点，根据后续的研究可以发现解决这两个问题的关键是：拉普拉斯矩阵；谱图卷积

为了获得与邻居的关系，我们从连接矩阵，度矩阵入手。下图1，定义了图上的一些基本概念：节点，边，权重，拉普拉斯矩阵等

$图1$
详细的图资料，请看：  图01—图的基本概念与模型
图02—存储结构，邻接矩阵，关联矩阵，权矩阵，邻接表，十字链表
为什么要用到拉普拉斯矩阵？下面简单概括了拉普拉斯矩阵的基本性质：

拉普拉斯矩阵是对称矩阵，可以进行特征分解（谱分解），这就和GCN的spectral domain对应上了
拉普拉斯矩阵只在中心顶点和一阶相连的顶点上（1-hop neighbor）有非0元素，其余之处均为0
通过拉普拉斯算子与拉普拉斯矩阵进行类比

图1中拉普拉斯算子与拉普拉斯矩阵具体的可以看：
5.8 拉普拉斯算子和拉普拉斯矩阵，图拉普拉斯算子推导
补充一下：

矩阵的谱分解，特征分解，对角化都是同一个概念（特征分解_百度百科）
不是所有的矩阵都可以特征分解，其充要条件为n阶方阵存在n个线性无关的特征向量。
拉普拉斯矩阵是半正定对称矩阵（半正定矩阵本身就是对称矩阵，半正定矩阵_百度百科），线代里关于矩阵有三个相关的性质，来，我们复习一下：


对称矩阵一定n个线性无关的特征向量
半正定矩阵的特征值一定非负
对阵矩阵的特征向量相互正交，即所有特征向量构成的矩阵为正交矩阵。

拉普拉斯矩阵的谱分解
由上可以知道拉普拉斯矩阵一定可以谱分解，且分解后有特殊的形式

$图2$

根据5.10 图上的傅里叶变换和逆变换可以得到：
图傅里叶变换：    $F(\lambda_l)=\widehat f(\lambda_l)=\sum_{i=1}^N f(i)*u_l^*(i)  =U^Tf$
图傅里叶变换的逆变换： $f=\mathbf{U} \mathbf{U}^{-1} f=\mathbf{U} \mathbf{U}^{T} f=\mathbf{U} \hat{f}$
带入$x$：  图信号（也是特征$\lambda_l$  ），就可以得到图2公式2（ $x$  的图傅里叶变换）和3 （$x$  的图傅里叶变换的逆变换）
拉普拉斯矩阵是实对称矩阵，实对称矩阵一定可以用正交矩阵进行正交相似对角化，进而得出拉普拉斯矩阵的谱分解：

$L=U\left(\begin{array}{ccc}  \lambda_{1} & & \\  & \ddots & \\  & & \lambda_{N}  \end{array}\right) U^{-1}  =U\left(\begin{array}{ccc}  \lambda_{1} & & \\  & \ddots & \\  & & \lambda_{N}  \end{array}\right) U^{T}$

$U$ 为特征向量构成的正交矩阵，也就是标椎正交基向量(想象成二维坐标$x_i$的x,y)，而正交矩阵的逆等于正交矩阵的转置：   $U^T=U^{-1}$
假定 $\lambda_{1},\cdots,\lambda_{n}$   从小到大排序，其对应的特征向量为 $u_1,\cdots, u_n$    ，特征值越小，对应的特征向量越平稳，这和傅立叶变换中频率的定义是类似的。下图是对 random sensor network 做特征值分解后的特征向量分布展示，可以看到特征值越小，对应的特征向量越平滑。

n阶对称矩阵一定有n个线性无关的特征向量。n维线性空间中的n个线性无关的向量都可以构成它的一组基。i.e. 下图中，当我们在这个空间中再画一个向量，这个向量都可以用下图中$u1$和$u2$来线性表示。


根据矩阵论的知识，对称矩阵的不同特征值对应的特征向量相互正交，这些正交的特征向量构成的矩阵为正交矩阵。
➢ 拉普拉斯矩阵的n个特征向量是n维空间中的一组标准正交基。

$UU^\top = I \\ L = U\Lambda U^{-1} =  U\Lambda U^\top$
谱图卷积
首先来看图上的谱卷积。图上的谱卷积可以定义为信号 $x \in \mathbb{R}^{N}$ 与卷积核$g_{\theta}=\operatorname{diag}(\theta)$ ( $\left.\theta \in \mathbb{R}^{N}\right)$ 在图上x和g卷积 $\left({ }^{*} \mathrm{~g}\right.$ 看做一个符号也就是图上的卷积),
卷积是怎么操作的，请观看 5.5 卷积、卷积定理和傅里叶变换的关系及其性质
图上的卷积怎么做的，请观看7.2 图卷积算子，图卷积的演变过程，下面直接给出结论：
怎么办？首先分别左乘一个 $U^T$   ，然后左乘$U$逆变换回来，具体过程就是下面的形式：

我们把 $U^{T} g$ 用对角矩阵的形式写开就是上面第二个公式所表示的内容（他们所表示的含义都 是g进行傅里叶变换），在这里，可以将 $g_{\theta}$ 看作是 $L$ 特征向量的函数，也就是 $g_{\theta}(\Lambda)$ 。进一 步，我们可以推出下面的公式:

其中的函数 $g_{\theta}(\Lambda)$ 为卷积核的频率响应函数, $\theta$ 为待学习参数。以上就是频谱图卷积的一般 形式, 有许多频谱图卷积的工作以此式为核心展开。
直觉上来说，图卷积操作可以看成将原始的处于空域的图信号变换到频域上之后,对频域属性进行滤波，然后再恢复到原来的图信号所在的空域中，从而完成了对图信号的降噪与特征提取的功能，但以上不是该论文的要讨论的。
对于图谱卷积来说, 其计算代价无疑是很大的:
(1) 使用 $U$ 进行矩阵乘法运算的计算复杂 度为 $\mathcal{O}\left(N^{2}\right) ;$ (2) 计算大图的拉普拉斯矩阵 $L$ 的特征分解需要很大的计算量。
该论文的贡献是进行方法的改进和加速，这个非常的关键，论文写到：

(i) they are not localized in space
(ii) their learning complexity is in O(n)

因此提出采用一个多项式的滤波器来解决（也就是只考虑最近的邻居，远的邻居置为零）

进一步，作者提出了用切比雪夫多项式，因为切比雪夫多项式可以写成递归的形式，也就是之前计算过的中间结果后面就可以直接用，不必再进行计算。
该方法使用切比雪夫多项式 (Chebyshev polynomial) $T_{k}(x)$ 的 $K$ 阶截断来获得对 $g_{\theta}(\Lambda)$ 的近似:

$g_{\theta^{\prime}}(\Lambda) \approx \sum_{k=0}^{K} \theta_{k}^{\prime} T_{k}(\tilde{\Lambda})$

其中, $\tilde{\Lambda}=\frac{2}{\lambda_{\max }} \Lambda-I_{N}$ 为经 $L$ 的最大特征值 (即谱半径) 缩放后的特征向量矩阵。
$\theta^{\prime} \in \mathbb{R}^{K}$ 表示一个切比雪夫向量。切比雪夫多项式使用递归的方式进行定义:
$T_{k}(x)=2 x T_{k-1}(x)-T_{k-2}(x)$, 其中, $T_{0}(x)=1$ 且 $T_{1}(x)=x_{\text {。 }}$
此时，可以使用近似的 $g_{\theta^{\prime}}$  替代原来的$g_{\theta}$,此时, 可以得到:
$g_{\theta^{\prime}} * x \approx U \sum_{k=0}^{K} \theta^{\prime} T_{k}(\tilde{\Lambda}) U^{T} x=\sum_{k=0}^{K} \theta_{k}^{\prime} U T_{k}(\tilde{\Lambda}) U^{T} x$

而 $T_{k}(\tilde{\Lambda})$ 是 $\Lambda$ 的 $k$ 阶多项式, 且有 $U \tilde{\Lambda}^{k} U^{T}=\left(U \tilde{\Lambda} U^{T}\right)^{k}=\tilde{L}^{k}$, 其中,

$\tilde{L}=\frac{2}{\lambda_{\max }} L-I_{N}$ 这样, 我们就得到了文中的公式:

$g_{\theta^{\prime}} \star x \approx \sum_{k=0}^{K} \theta_{k}^{\prime} T_{k}(\tilde{L}) x$

通过这一近似, 可以发现，谱图卷积不再依赖于整个图, 而只是依赖于距离中心节点 $K$ 步之内 的节点 (即 $K$ 阶邻居) 。在[3]中, Defferrard et al. 使用了这一概念定义了图上的卷积神经网 络

如果K=1，并进行进一步的参数简化，就是后面Thomas Kipf的GCN了~图卷积网络的半监督分类(GCN)
线性模型
近似的谱图卷积虽然可以建立起 $K$ 阶邻居的依赖，然而，却仍然需要在 $\tilde{L}$ 上进行 $K$ 阶运 算。在实际过程中，这一运算的代价也是非常大的。为了降低运算代价, 本文进一步简化了该 运算, 即限定 $K=1$ 。此时，谱图卷积可以近似为 $\tilde{L} \quad($ 或 $L)$ 的线性函数。
当然, 这样做的代价是，只能建立起一阶邻居的依赖。对于这一问题, 可以通过堆积多层图卷积网络建立 $K$ 阶邻居的依赖，而且，这样做的另一个优势是，在建立 $K>1$ 阶邻居的依赖 时, 不需要受到切比雪夫多项式的限制。
为了进一步简化运算，在GCN的线性模型中，本文定义 $\lambda_{\max } \approx 2$ 。此时，我们可以得到图 谱卷积的一阶线性近似：

$g_{\theta^{\prime}} \star x \approx \theta_{0}^{\prime} x+\theta_{1}^{\prime}\left(L-I_{N}\right) x=\theta_{0}^{\prime} x-\theta_{1}^{\prime} D^{-\frac{1}{2}} A D^{-\frac{1}{2}} x$

可以看到，该式中仅有两个参数 $\theta_{0}^{\prime}$ 与 $\theta_{1}^{\prime}$ 。若需建立 $k$ 阶邻居上的依赖，可以通过设置 $k$ 层这样 的滤波器来实现。
在实际的过程中，可以通过对参数进行约束来避免过拟合，并进一步简化运算复杂度。例如, 可以令 $\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime}$, 从而得到

$g_{\theta} \star x \approx \theta\left(I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\right) x$

需要注意的是, $I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$ 的特征值范围为[0,2], 这意味着, 当不停地重复该操 作时 (网络非常深时)， 可能会引起梯度爆炸或梯度消失。为了减弱这一问题, 本文提出了一 种 renormalization trick:

$I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \rightarrow \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$
其中, $\tilde{A}=A+I_{N}, \quad \tilde{D}_{i i}=\Sigma_{j} \tilde{A}_{i j}$ 。
当图中每个节点的表示不是单独的标量而是一个大小为 $C$ 的向量时，可以使用其变体进行处 理：

$Z=\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} X \Theta$

其中, $\Theta \in \mathbb{R}^{C \times F}$ 表示参数矩阵, $Z \in \mathbb{R}^{N \times F}$ 为相应的卷积结果。此时, 每个节点的节 点表示被更新成了一个新的 $F$ 维向量，该 $F$ 维向量包含了相应的一阶邻居上的信息。
参考
[1] arXiv: https://arxiv.org/abs/1606.09375
[2] tensorflow_code: https://github.com/mdeff/cnn_graph
[3] pytorch_code: https://github.com/xbresson/graph_convnets_pytorch
[4] nips: https://papers.nips.cc/paper/6081-convolutional-neural-networks-on-graphs-with-fast-localized-spectral-filtering
[5] reviews: http://media.nips.cc/nipsbooks/nipspapers/paper_files/nips29/reviews/1911.html
[6] spotlight: https://www.youtube.com/watch?v=cIA_m7vwOVQ
[7] slides: https://ndownloader.figshare.com/files/7253636
[8]：https://zhuanlan.zhihu.com/p/272767872