线性非移变系统理论

线性非移变系统理论建立在图讯号处理中对线性非移变系统的定义上，致力于承袭线性非时变系统理论在操作上的便利性。

图位移（Graph Shift）

对于一个N点的图$G$（可为有向，但通常有限、不重边），可定义图位移$S$，为一线性映射从图讯号时域映射到图讯号时域，可表为一N阶方阵 。

图位移是一个抽象定义，并没有特别指对$G$使用哪种特定方法构造出来的为图位移。

比较被使用的图位移有：连接矩阵A、拉普拉斯矩阵L、正规化拉普拉斯矩阵L_N。

线性非移变系统

线性非移变系统是图讯号处理中，有最简单结构的系统。其性质可最大限度地和数字信号处理中的线性非时变系统对照，并发展出与之类似的运算，达到想要的讯号处理效果。

定义

在一$N$点的图上，给定已定义的图位移$S$，若线性映射$H:\mathbb {C} ^{N}\rightarrow \mathbb {C} ^{N}$满足$HS=SH$，则称其为线性非移变系统（LSI）。

基本性质

1. 不受图位移$S$的作用前后顺序影响。
2. 可表示为图图位移$S$的多项式，也就是说存在$h$多项式，使得$H=h(S)$。更严谨地，若考虑的是N-1阶以下的多项式，则$h$唯一存在。

传递函数

根据性质2.，再以给定好图位移的情况下，对所有线性非移变系统$H$，可唯一定义其传递函数$h$，$h$为最高次项小于N-1阶的多项式，且$H=h(S)$。

基本运算的推广形式

图论傅立叶转换

详见图论傅立叶转换。

折积

折积在图讯号时域中因为没有显著的前后关系，无法定义一个良好的计算式。但因同一张图上的图讯号在频域中之频率值相同，折积的推广定义可使用折积原本的性质：频域中的峰值相乘，也就是

${\hat {s}}_{out}(\lambda _{k})={\hat {s}}_{1}(\lambda _{k}){\hat {s}}_{2}(\lambda _{k})$

其中$s_{1}$、$s_{2}$为输入讯号，$s_{out}$为输出讯号，$\{\lambda _{k}\}_{k=0...N-1}$为频域之特征频率。对上式作逆图论傅立业转换，得

$s_{out}(i)=(s_{1}*s_{2})(i)=\sum _{k=0}^{N-1}{\hat {s}}_{1}(\lambda _{k}){\hat {s}}_{2}(\lambda _{k})u_{k}(i)$

其中$\{u_{k}\}_{k=0...N-1}$为图论傅立叶基底。将此式作为折积之推广定义。

上式有另一个使用矩阵的表示法

$s_{out}=VD_{{\hat {s}}_{2}}V^{-1}s_{1}$

其中$V^{-1}$为图论傅立叶转换矩阵，$V$即为逆傅立叶转换矩阵，$D_{{\hat {s}}_{2}}$表示一对角矩阵，其主对角线的元素为${\hat {s}}_{2}$

平移

平移在图讯号时域中亦因为没有好的顺序关系，无法被良好的直接定义。

但因一般数字信号处理的平移运算等价于将讯号与一个单位脉冲讯号折积，其推广定义可以利用此性质

$s_{out}=s_{in}*\delta _{n}=VD_{{\hat {s}}_{in}}V^{-1}\delta _{n}=VD_{{\hat {s}}_{in}}u_{n}$，其中$\delta _{n}(k)={\begin{cases}1,&{\text{if }}n=k\\0,&{\text{if }}n\neq k\end{cases}}$

滤波

滤波是让输入讯号经过一系统，产生输出讯号的过程。在时域中的表现形式为

$s_{out}=Hs_{in}$

若$H$是线性非移变系统，存在多项式传递函数$h$使得$h=h(S)$，故

$Hs_{in}=h(S)s_{in}=h(V\Lambda V^{-1})s_{in}=Vh(\Lambda )V^{-1}s_{in}=VD_{{\hat {s}}_{H}}V^{-1}s_{in}$

与折积的定义比较，可知其实可将“对$s_{in}$使用$H$滤波”看作“将$s_{in}$与另一个信号$s_{H}$作折积”，其中$s_{H}$符合${\hat {s}}_{H}=(h(\lambda _{1}),h(\lambda _{2}),...h(\lambda _{N-1}))^{T}$，

此时称$s_{H}$为$H$的脉冲响应，${\hat {s}}_{H}$为$H$的频率响应。

参考

• A. Sandryhaila and Jose M. F. Moura, Discrete Signal Processing on Graphs, [[arxiv:1210.4752|http://arxiv.org/abs/1210.4752 （页面存档备份，存于互联网档案馆）]]
• David I Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, Pierre Vandergheynst, The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains, [[arxiv:1211.0053|http://arxiv.org/abs/1211.0053 （页面存档备份，存于互联网档案馆）]]