线性非移变系统理论

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

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

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

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

定义

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

基本性质

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

传递函数

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

图论傅立叶转换

详见图论傅立叶转换。

折积

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

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

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

${\displaystyle 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)}$ 

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

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

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

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

平移

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

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

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

滤波

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

${\displaystyle s_{out}=Hs_{in}}$ 

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

${\displaystyle 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}}$ 

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

此时称${\displaystyle s_{H}}$ 为${\displaystyle H}$ 的脉冲响应，${\displaystyle {\hat {s}}_{H}}$ 为${\displaystyle 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 （页面存档备份，存于互联网档案馆）]]

1. ^ Sandryhaila, Aliaksei; Moura, Jose M. F. Discrete Signal Processing on Graphs. IEEE Transactions on Signal Processing: 1644–1656. [2016-06-30]. ISSN 1053-587X. doi:10.1109/TSP.2013.2238935. （原始内容存档于2018-12-12）. 
2. ^ Shuman, David I.; Narang, Sunil K.; Frossard, Pascal; Ortega, Antonio; Vandergheynst, Pierre. The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains. IEEE Signal Processing Magazine: 83–98. [2016-06-30]. ISSN 1053-5888. doi:10.1109/MSP.2012.2235192. （原始内容存档于2020-01-11）.