A Parallel Multiple Minor Components Extraction Algorithm and Its Convergence Analysis
-
摘要: 次成分分析是信号处理领域内一项重要的分析工具.目前，多维次成分并行提取算法数量稀少，而且现有的算法在应用时还存在很多限制条件.针对上述问题，在分析研究OJAm次子空间跟踪算法的基础上，采用加权矩阵法提出了一种多维次成分提取算法，并采用递归最小二乘法对所提算法进行了简化，最后采用李雅普诺夫函数法确定了所提算法的全局收敛域.相比现有算法，所提算法对信号的特征值大小没有要求，也不需要在迭代过程中进行模值归一化操作，同时算法具有较低的计算复杂度.仿真实验表明：所提算法能够并行提取多维次成分，而且收敛速度要优于现有同类型算法.Abstract: Minor component analysis is a powerful tool in the field of signal processing. Up to now, there are few algorithms that can extract multiple minor components in parallel. Some existing algorithms have some limitations for real applications. In order to solve these problems, a novel multiple minor components extraction algorithm is proposed by introduing the weighted matrix method into the OJAm minor subspace algorithm. A recursive least square (RLS) algorithm is also derived based on the proposed algorithm. The global convergence region of the proposed algorithm is obtained by using the Lyapunov function method. Compared with some existing algorithms, the proposed algorithm has no restriction on the values of eigenvalue and does not need normalization operation during iterations. Its computation complexity is less than those of some counterparts. Simulation results show that the proposed algorithm can adaptively extract multiple minor components from input signals in parallel and has faster convergence speed than some same-type algorithms.
-
在信号处理领域, 将信号自相关矩阵最小特征值对应的特征向量定义为信号的次成分(Minor component, MC).次成分分析是一种从信号提取次成分的技术.次成分分析已经广泛应用于计算机视觉[1]、波达方向估计[2]、FIR滤波器设计[3]、曲面拟合[4]等领域.目前, 基于神经网络的次成分分析算法是国际上的一个研究热点.相比传统的特征值分解算法, 神经网络算法具有计算复杂度低、能够在线实施和跟踪非平稳信号等优点[5].
根据提取次成分的维数, 次成分分析算法可以分为:单维次成分提取、次子空间跟踪和多维次成分提取等三类[6].目前, 学者们已经提出了大量的单维次成分提取算法和次子空间跟踪算法[2-3, 6], 而多维次成分提取算法还非常稀少.传统的多维次成分提取大多是通过串行提取或空间旋转来实现[6].串行提取法是首先利用单维次成分分析算法提取信号的第一个次成分, 然后利用膨胀技术依次提取下一个次成分.串行算法的缺点在于存储器需求量大、提取时间有延迟、误差累计传播等.空间旋转法是首先利用次子空间跟踪算法提取信号的次子空间, 然后进行空间旋转得到多维次成分.空间旋转法的缺点在于计算复杂度的增加[7].
相比串行提取法和空间旋转法, 并行算法能够直接从信号中提取多维次成分, 且不需要中间转换过程, 因此可以避免两类算法的缺点.最早的并行提取算法是由芬兰学者Oja提出来的[8], 该算法虽然可以并行提取多维次成分, 但是其要求信号的最小特征值必须小于1; Mathew等提出的算法[9]虽然没有特征值大小的限制, 但是该算法只适用于信号具有多个相同的最小特征值; 基于Douglas次子空间跟踪算法, Jankovic等[10]提出了一种新型多维次成分提取算法——MDouglas算法, 虽然该算法对特征值大小没有要求, 但是需要事先选取参数, 而且该参数选取的结果直接影响着算法的收敛性能; 采用主/次成分转换机制, Tan等提出了一种并行提取算法[11], 该算法的缺点在于需要事先对最小特征值进行估计; Bartelmaos等所提出的MCA-OOJAH算法[12]虽然对信号特征值没有要求, 但是需要在每次迭代过程中增加模值归一化措施, 以保证算法的收敛性.频繁的模值归一化操作极大地增加了MCA-OOJAH算法的计算复杂度.综上所述可得, 现有算法存在以下几个方面的问题: 1)对信号的特征值有要求; 2)需要事先选取一些参数; 3)算法计算过程复杂.本文研究目的就是发展能够避免上述缺点的多维次成分并行提取算法.
本文的主要贡献可以归纳为以下三个方面: 1)提出了一种多维次成分并行提取算法, 该算法对信号的特征值没有要求, 而且不需要模值归一化操作; 2)利用递归最小二乘(Recursive least square, RLS)技术对所提算法进行改进, 导出了一种具有低计算复杂度的算法; 3)利用李雅普诺夫函数法完成了对所提算法的全局收敛性分析, 确定了所提算法的全局收敛域.
论文的结构安排如下:第1节是对神经网络模型和次成分进行简介; 第2节是在研究OJAm算法的基础上, 提出两种多维次成分提取算法; 第3节是采用李雅普诺夫函数法对所提算法的全局收敛性进行证明; 第4节是通过仿真实验对所提算法的性能进行验证; 论文的总结安排在第5节.
1. 问题描述
考虑如下一个具有多输入多输出的神经网络模型:
$ {\pmb y}~(k) = {{W}^{\rm T}}{\pmb x}~(k), {\kern 1pt} {\kern 1pt} {\kern 1pt} k = 1, 2, \cdots $
(1) 其中, ${\pmb y}~(k) \in {{\bf R}^{r \times 1}}$是神经网络的输出, 是神经网络的状态矩阵, 输入信号是一个零均值的随机过程, 这里作为神经网络的输入, $n$为输入向量的维数, $r$为所需提取次成分成分的维数.
令为输入信号${\pmb x}~(k)$的自相关矩阵, ${\lambda _i}$和分别为自相关矩阵${{R}}$的特征值和对应的特征向量.根据矩阵理论可得:矩阵${{R}}$是一个对称非负定矩阵, 且其特征值均是非负的.为了后续方便, 这里将其矩阵${{R}}$的特征值按照从大到小方式排列, 即
$ {\lambda _1} \ge {\lambda _2} \ge \cdots {\lambda _{n - r + 1}} \ge \cdots \ge {\lambda _n} \ge 0 $
(2) 则矩阵${{R}}$的特征值分解可以表示为
$ {{R}} = {U\Lambda}{{U}^{\rm T}} = {{U}_1}{{\Lambda}_1}{U}_1^{\rm T} + {{U}_n}{{\Lambda}_n}{U}_n^{\rm T} $
(3) 其中, 是由矩阵${{R}}$的特征向量构成的矩阵, 是由矩阵${{R}}$的特征值构成的对角矩阵, 是由前$n - r$个特征向量构成的矩阵, 是由前$n - r$个特征值构成的对角矩阵, 和分别为后$r$个特征向量和特征值构成的矩阵.
根据定义可知特征值所对应的特征向量称为信号的前$r$个次成分, 而由特征向量张成的子空间称为信号的次子空间.子空间跟踪算法的目的是能够估计出子空间${V_1}$的一组基, 而多维次成分提取算法则是要找到确定的特征向量.
2. 多维次成分并行提取算法
2.1 多维次成分提取算法的提出
在文献[13]中, Feng等提出了OJAm次子空间跟踪算法.当OJAm算法收敛时, 该算法的状态矩阵只能收敛到信号次子空间的一组正交基, 而非多维次成分.通过对OJAm算法进行加权处理, 这里提出如下算法
$ \begin{align} {W}(k) =\,&{W}(k - 1) + \eta \Big[{{W}(k- 1){A}}\times \nonumber\\& {({{W}^{\rm T}}(k - 1){W}(k - 1){A})^{ - 2}} - {{\hat R}}(k) \times \nonumber\\& {{W}(k - 1){{({{W}^{\rm T}}(k - 1){{\hat R}}(k){W}(k - 1))}^{ - 1}}} \Big] \end{align} $
(4) 其中, $\eta $是神经网络的学习因子, 满足关系: $0 < \eta \le 1$; ${A} = {\rm diag}\{{a_1}, {a_2}, \cdots, {a_r}\}$是一个$r \times r$维对角矩阵, 其对角线元素均为正数, 且满足关系: ; ${{\hat R}}~(k)$为$k$时刻对自相关矩阵${{R}}$的估计值, 即
$ \begin{align} {{\hat R}}~(k) =\,&\dfrac{1}{k}\sum\limits_{i = 1}^k {{\alpha ^{k - i}}{\pmb x}~(i){{\pmb x}^{\rm T}}~(i)}= \nonumber\\ & \dfrac{{k - 1}}{k}\alpha {{\hat R}}~(k - 1) + \dfrac{1}{k}{\pmb x}~(k){{\pmb x}^{\rm T}}~(k) \end{align} $
(5) 其中, 被称为遗忘因子.如果样本来自于一个平稳的随机过程, 则可以令$\alpha=1$, 此时式(5)相当于对取瞬时数学期望.显然当训练样本非常大时, 将等价于自相关矩阵${{R}}$.另一方面, 如果取自一个非平稳的随机过程, 则遗忘因子应该在区间$(0, 1)$内取值, 以便对采样样本施加一个宽度为$1/\left( {1 - \alpha } \right)$的遗忘窗.该遗忘窗通过对不同时刻的采样样本赋予不同的权值来降低以往数据对于当前结果的影响.遗忘因子$\alpha $的取值是由采样信号来决定.通常对于变化缓慢的样本, $\alpha $的取值要接近1以产生一个较大的遗忘窗; 而对于变化快速的样本, 遗忘窗口宽度应比较小, 此时$\alpha $则应该在接近0处取值[14].为了方便后续使用, 这里将式(4)所描述的算法记为WOJAm (Weighted OJAm)算法.
从式(4)可得:学习因子控制着算法的学习步长.一般说来, 学习因子越大, 算法的学习步长越大, 算法的收敛速度也越快, 但是学习因子过大有时会引起算法的震荡甚至发散.反之, 学习因子越小, 算法的学习步长越小, 收敛速度也越慢, 因此过小的学习因子会降低算法的性能.目前, 学习因子的选择主要依靠经验知识, 如何选取最优的学习因子仍是一个难以解决的问题.从式(5)可得:遗忘因子主要影响着信号的自相关矩阵.根据文献[15]的研究, 遗忘因子对于算法的收敛速度几乎没有影响.
2.2 基于递归最小二乘的改进型算法
虽然WOJAm算法可以提取信号的多维次成分, 但其计算复杂度为${n^2}r + 5n{r^2} + 11{r^3}/3$, 高于OJAm算法${n^2}r + 2n{r^2} + 10{r^3}/3$的计算算复杂度.通常, 高昂的计算复杂度会在一定程度上限制算法的使用范围.由于RLS技术能够在不改变算法性能的前提下降低算法的计算复杂度[16], 因此本节将研究基于RLS技术的多维次成分提取算法.
假设在第$i~(1 \le i \le k)$次迭代时, 输入数据在神经网络状态矩阵${W}~(k - 1)$上的投影可以通过式来近似(这一近似已经广泛应用于很多算法的推导过程中, 并不会影响算法的最终性能[17]).通过这一近似, 就可以在任意时刻获得神经网络的输出的估计值.将式(5)代入式(4)可得:
$ \begin{align} {W}~(k) =\,&{W}~(k - 1) + \mu \Bigg[{{W}~(k- 1){A} \times }\nonumber\\ & {({{W}^{\rm T}}~(k - 1){W}~(k - 1){A})^{ - 2}} - \nonumber\\ & {\left( {\sum\limits_{i = 1}^k {{\alpha ^{k - i}}{\pmb x}~(i){{\pmb y}^{\rm T}}~(i)} } \right){{\left( {\sum\limits_{i = 1}^k {{\alpha ^{k - i}}{\pmb y}~(i){{\pmb y}^{\rm T}}~(i)} } \right)}^{ - 1}}} \Bigg] \end{align} $
(6) 为了方便计算, 这里做如下简记:
$ {P}~(k) = {\left( {\sum\limits_{i = 1}^k {{\alpha ^{k - i}}{\pmb y}~(i){{\pmb y}^{\rm T}}~(i)} } \right)^{ - 1}} $
(7) $ {\tilde W}~(k) = \left( {\sum\limits_{i = 1}^k {{\alpha ^{k - i}}{\pmb x}~(i){{\pmb y}^{\rm T}}~(i)} } \right){P}~(k) $
(8) 应用矩阵求逆引理[18], 则式(7)可以化简为:
$ 9\begin{align} {P}~(k)=\, & {\left( {\alpha \sum\limits_{i = 1}^{k - 1} {{\alpha ^{k - i - 1}}{\pmb y}~(i){{\pmb y}^{\rm T}}~(i)} + {\pmb y}~(k){{\pmb y}^{\rm T}}~(k)} \right)^{ - 1}} =\nonumber\\ & {\left( {\alpha {P}~(k - 1) + {\pmb y}~(k){{\pmb y}^{\rm T}}~(k)} \right)^{ - 1}}=\nonumber\\ & {\alpha ^{ - 1}}\left( {{P}~(k - 1) - {\pmb g}~(k){{\pmb y}^{\rm T}}~(k){P}~(k - 1)} \right) \end{align} $
(9) 其中, .从式(9)可得: ${\pmb g}~(k) = {P}~(k - 1){\pmb y}~(k)$, 进而有:
$ \begin{align} {\kern 1pt} &{\tilde W}~(k) = \left( {\sum\limits_{i = 1}^k {{\alpha ^{k - i}}{\pmb x}~(i){{\pmb y}^{\rm T}}~(i)} } \right){P}~(k)= \nonumber\\ & \left( {\sum\limits_{i = 1}^{k - 1} {{\alpha ^{k - i{\rm{ - }}1}}{\pmb x}~(i){{\pmb y}^{\rm T}}~(i)} } \right){P}~(k - 1) + {\pmb x}~(k){\pmb y}_k^{\rm T}{P}~(k)-\nonumber\\ & \left( {\sum\limits_{i = 1}^{k - 1} {{\alpha ^{k - i{\rm{ - }}1}}{\pmb x}~(i){{\pmb y}^{\rm T}}~(i)} } \right){P}~(k - 1){\pmb y}~(k){{\pmb g}^{\rm T}}~(k)= \nonumber\\ & {\tilde W}~(k - 1) + \left( {{\pmb x}~(k) - {\tilde W}~(k - 1){\pmb y}~(k)} \right){{\pmb g}^{\rm T}}~(k) \end{align} $
(10) 上式推导过程中用到了如下结论:
$ \begin{align} {\pmb g}~(k)&{{\pmb y}^{\rm T}}~(k - 1){P}~(k - 1)=\nonumber\\ & {\left( {{\pmb g}~(k){{\pmb y}^{\rm T}}~(k - 1){P}~(k - 1)} \right)^{\rm T}}=\nonumber\\ & {P}~(k - 1){\pmb y}~(k - 1){{\pmb g}^{\rm T}}~(k) \end{align} $
(11) 综合式(6)~(10), 就可以利用$k$时刻的输入向量和$k-1$时刻的${\tilde W}~(k - 1)$来估计状态矩阵, 即完成了利用RLS技术对WOJAm算法的改进, 因此将该算法记为RLS-WOJAm算法, 其计算过程如下.
初始化:令$k = 0$, 选择合适的学习因子$\eta $和遗忘因子, 其他初始化参数设置为: ${P}~(0) = \delta {{I}_r}$ (其中是一个非常小的数), ${\tilde W}~(0) = {0}$.
迭代过程:令$k = k + 1$, 根据以下方程对神经网络状态矩阵进行更新迭代,
$ \begin{align} \begin{array}{l} {\pmb y}~(k) = {{W}^{\rm T}}~(k - 1){\pmb x}~(k)\\ {\pmb g}~(k) = \dfrac{{{P}~(k - 1){\pmb y}~(k)}} {\alpha + {{\pmb y}^{\rm T}}~(k){P}~(k - 1){\pmb y}~(k)}\\ {P}~(k) = {\alpha ^{ - 1}}\left( {{P}~(k - 1) - {\pmb g}~(k){{\pmb y}^{\rm T}}~(k){P}~(k - 1)} \right)\\ {\tilde W}~(k) = {\tilde W}~(k - 1) + \left( {{\pmb x}~(k) - {\tilde W}~(k - 1){\pmb y}~(k)} \right){{\pmb g}^{\rm T}}~(k)\\ {W}~(k) = {W}~(k - 1) - \eta {\tilde W}~(k)+\\ \eta {W}~(k - 1){A}{({{W}^{\rm T}}~(k - 1){W}~(k - 1){A})^{ - 2}} \end{array} \end{align} $
(12) 2.3 算法性能评价
本节对所提算法进行分析, 并将所提算法与一些现有算法进行比较:
1) 将WOJAm算法与OJAm算法进行对比可以发现, 两者相差的只是加权矩阵${A}$. OJAm算法只是在对状态矩阵的模值进行了约束, 而WOJAm算法则是通过该加权矩阵对状态矩阵不断地实施Gram-Schmidt正交化操作, 从而使得状态矩阵能够收敛到所需的次成分.显然, 这里加权矩阵的作用是与文献[16]相类似的.
2) 从文献[13]可得, OJAm算法是一个次子空间跟踪算法, 算法只能收敛到信号次子空间的一组基, 不一定是次成分, 而所提算法收敛结果则是确定的次成分.根据矩阵理论[18]可得:子空间${V_1}$有很多种不同的基, 而次成分只是其中一个特殊的基.即所提算法不仅适用于多维次成分提取, 而且还可以用于子空间跟踪.因此相比OJAm算法, 所提算法具有更为广泛的应用范围.
3) 这里将所提算法与近期提出的AMMD算法[11]和MCA-OOJAH算法[12]进行对比.在应用AMMD算法前, 必须要对信号自相关矩阵的最大特征值进行估计, 由于信号是多种多样, 有些情况下是难以估计的, 因此这一约束限制了AMMD算法的实际应用.而所提算法在使用前并没有这一要求, 因此拓宽了使用范围. MCA-OOJAH算法虽然没有限制条件, 但是其需要在每一次迭代过程中增加状态矩阵模值归一化操作, 以确保算法的稳定性, 由于大量的归一化操作, 增加了MCA-OOJAH算法的计算量, 而所提算法则没有这些要求, 降低了算法的硬件开销.
4) 虽然WOJAm算法的计算复杂度为, 但是由其导出的RLS-WOJAm算法的计算复杂度将至.这一计算复杂度不仅要低于原来的OJAm次子空间跟踪算法(), 而且还要比AMMD算法[11] $ {n^3} + 2{n^2}r + {\rm O}(n)$的计算复杂度和MDouglas算法[10] $ {n^2}r + 5n{r^2} + {\rm O}(n)$的计算复杂度要低很多.此外, RLS-WOJAm算法只涉及到矩阵的加、乘和简单求逆操作, 因此实施较为容易.
3. 算法的全局收敛性分析
文献[13]只是对OJAm算法进行了收敛性分析, 并未给出算法的收敛域; 本节将通过李雅普诺夫函数法对所提算法的收敛性进行分析, 确定出算法的收敛域.借鉴现有文献[19]分析结论可得:所提WOJAm算法和RLS-WOJAm在本质上是相同的, 因此两个算法具有相同的全局收敛域.假定输入信号是一个零均值的平稳随机过程, 当学习因子$\eta $非常小时, 根据随机近似理论[20], 则式(4)所描述的离散时间方程可以转化为相对应的一阶常微分方程
$ \begin{align} \frac{{{\rm d}{W}~(t)}}{{{\rm d}t}} =\,&{RW}~(t){({{W}^{\rm T}}~(t){RW}~(t))^{ - 1}}-\nonumber\\& {W}~(t){A}{({{W}^{\rm T}}~(t){W}~(t){A})^{ - 2}} \end{align} $
(13) 其中, .通过对式(13)的收敛性分析就可以间接获得所提算法的全局收敛性.事实上, 算法的全局收敛性主要是回答以下两个问题[21]:
1) 式(13)所描述的动态系统能否全局收敛到自相关矩阵的多维次成分?
2) 算法对于次成分的吸引域是多少?或者说确保算法全局收敛的初始条件是什么?
为了回答上述问题, 这里构造如下函数:
$ L({W}) = - \frac{1}{2}{\rm tr}\left\{ {{\rm ln}\left[{{{W}^{\rm T}}{{{R}}_r}{W}} \right] + {{\left( {{{W}^{\rm T}}{WA}} \right)}^{ - 1}}} \right\} $
(14) 其中, .所提算法的收敛性可以通过定理1来完成.
定理1. $L({W})$是常微分方程(13)所对应的李雅普诺夫函数, 通过该函数可以获得神经网络状态矩阵${W}$在平稳点处的吸引域为
$ \Omega = \left\{ {{W}|0 < {{W}^{\rm T}}{{{R}}_r}{W} < \infty , {{W}^{\rm T}}{WA} \ne {0}} \right\} $
(15) 证明. 由于$L({W})$是一个连续函数, 则其是连续可微的:
$ \nabla L({W}) = - \left[{{{{R}}_r}{W}{{({{W}^{\rm T}}{{{R}}_r}{W})}^{ - 1}} - {WA}{{({{W}^{\rm T}}{WA})}^{ - 2}}} \right] $
(16) 通过链式法则, 可以获得$L({W})$对于时间$t$的导数
$ \begin{align} &\frac{{{\rm d}L({W}~(t))}}{{{\rm d}t}}={\rm tr}\left[{\nabla L({W}) \cdot \frac{{{\rm d}{{W}^{\rm T}}}}{{{\rm d}{\rm{t}}}}} \right]=\nonumber\\&\quad - {\rm tr}\left\{ {{{\left[{{{{R}}_r}{W}{{({{W}^{\rm T}}{{{R}}_r}{W})}^{ - 1}} - {WA}{{({{W}^{\rm T}}{WA})}^{ - 2}}} \right]}^{\rm T}}} \right.\cdot\nonumber\\&\quad \left. { \left[{{RW}{{({{W}^{\rm T}}{RW})}^{ - 1}} - {WA}{{({{W}^{\rm T}}{WA})}^{ - 2}}} \right]} \right\} \end{align} $
(17) 为了方便起见, 上式中省略了时间变量$t$.根据李雅普诺夫第二定律, 需要证明如下结论:在域内, 而在域$\{ {W}|{W} = {{U}_n}{{A}^{ - {\textstyle{1 \over 2}}}}\} $内.为了完成上述证明, 这里将${{R}} = {{U}_1}{{\Lambda}_1}{U}_1^{\rm T} + {{U}_n}{{\Lambda}_n}{U}_n^{\rm T}$代入式(17), 并进行适当化简可得:
$ \begin{align} \begin{array}{l}\small \dfrac{{{\rm d}L({W})}}{{{\rm d}t}} = - {\rm tr}\left\{ {{{\left[ {\begin{array}{*{20}{c}} { - {{Z}_1}{A}{{({Z}_2^{\rm T}{{Z}_2}{A})}^{ - 2}}}\\ {{{\Lambda}_2}{{Z}_2}{{({Z}_2^{\rm T}{{\Lambda}_2}{{Z}_2})}^{ - 1}} - {{Z}_2}{A}{{({Z}_2^{\rm T}{{Z}_2}{A})}^{ - 2}}} \end{array}} \right]}^{\rm T}}} \right.\cdot\\ \quad \left. { \left[{\begin{array}{*{20}{c}} {{{\Lambda}_1}{{Z}_1}{{({Z}_1^{\rm T}{{\Lambda}_1}{{Z}_1} + {Z}_2^{\rm T}{{\Lambda}_2}{{Z}_2})}^{ - 1}} - {{Z}_1}{A}{{({Z}_2^{\rm T}{{Z}_2}{A})}^{ - 2}}}\\ {{{\Lambda}_2}{{Z}_2}{{({Z}_1^{\rm T}{{\Lambda}_1}{{Z}_1} + {Z}_2^{\rm T}{{\Lambda}_2}{{Z}_2})}^{ - 1}} - {{Z}_2}{A}{{({Z}_2^{\rm T}{{Z}_2}{A})}^{ - 2}}} \end{array}} \right]} \right\} \end{array} \end{align} $
(18) 其中, ${{Z}_1} = {U}_1^{\rm T}{W}$和.由于, 则矩阵${{Z}_2}$是可逆的.因此, 必定存在一矩阵使得${{Z}_1} = {B}{{Z}_2}$成立.将式(18)中的${{Z}_1}$用${{Z}_2}$来表示, 则有:
$ \begin{align} \dfrac{{{\rm d}L({W})}}{{{\rm d}t}} =\,&{\rm tr}\left\{ {2{C} + {CZ}_2^{\rm T}~({I} + {{B}^{\rm T}}{B}){{Z}_2}{{C}^{\rm T}}} \right\}-\nonumber\\& {\rm tr}\left\{ {{{Z}_2}^{ - 1}{{({I} + {{B}^{\rm T}}{{\Lambda}_1}{B\Lambda}_2^{ - 1})}^{ - 1}}{{Z}_2}^{ - T}} \right\} \end{align} $
(19) 其中, .当${W}$接近平稳点处时, 矩阵${C}$可以近似为一个对角矩阵, 即.此时, 式(19)就可以化简为:
$ \begin{align} \frac{{{\rm d}L({W})}}{{{\rm d}t}} \approx\,&{\rm tr}\left\{ {2{C'} + {C'Z}_2^{\rm T}~({I} + {{B}^{\rm T}}{B}){{Z}_2}{C'}} \right\}- \nonumber\\& {\rm tr}\left\{ {{{Z}_2}^{ - 1}{{({I} + {{B}^{\rm T}}{{\Lambda}_1}{B\Lambda}_2^{ - 1})}^{ - 1}}{{Z}_2}^{ - T}} \right\} \end{align} $
(20) 接下来, 考虑矩阵${{Z}_1} \ne {0}$的情况.根据矩阵理论有:
$ {\rm tr}\left\{ {{Z}_2^{\rm T}~({I} + {{B}^{\rm T}}{B}){{Z}_2}} \right\} < {\rm tr}\left\{ {{{Z}_2}~({I} + {{B}^{\rm T}}{{\Lambda}_1}{B\Lambda}_2^{ - 1}){{Z}_2}} \right\} $
(21) 令, 则其特征值分解可以表示为:
$ {D} = {\Phi \Psi }{{\Phi }^{\rm T}} $
(22) 其中, 是一对角矩阵, 是矩阵${D}$的特征值, 是由特征向量组成的矩阵.将式(22)代入式(21)可得:
$ \begin{align} \frac{{{\rm d}L({W})}}{{{\rm d}t}}<\, &- {\rm tr}\left\{ { - 2{C'} + {C'DC'} + {{D}^{ - 1}}} \right\}=\nonumber\\& 2{\rm tr}~({C'}) - {\rm tr}~({C'\Psi C'}) - {\rm tr}\left[{{{({\Psi })}^{ - 1}}} \right] =\nonumber\\& \sum\limits_{i = 1}^r {\left( {2{c_i} - c_i^2{\mu _i} - \dfrac{1} {\mu _i}} \right)} \le 0 \end{align} $
(23) 接下来考虑${{Z}_1} = {0}$的情况, 此时式(19)可简化为:
$ \frac{{{\rm d}L({Z})}}{{{\rm d}t}} = - {\rm tr}~({{E}^{\rm T}}{E}) \le 0 $
(24) 其中, .
从式(24)可得:当且仅当${E} = {0}$时, 有成立.此时${{Z}_2} = {{A}^{ - {\textstyle{1 \over 2}}}}$, 即${W} = {{U}_n}{{A}^{ - {\textstyle{1 \over 2}}}}$.从式(23)和式(24)可得:对于任意的${W} \in {\Omega ^*}$均有成立.因此, 在域$\Omega $内平稳点${W} = {{U}_n}{{A}^{ - {\textstyle{1 \over 2}}}}$是渐近稳定的, 即只要初始化状态矩阵${W}$在域$\Omega $以内, 则算法(13)全局渐近收敛到自相关矩阵矩阵${{R}}$的前$r$个次成分.
4. 仿真实验
本节将通过两个数值仿真实验来验证所提算法的性能.第一个实验是考察所提算法提取多维次成分的能力, 第二个实验将所提算法与一些现有算法进行对比.在仿真实验过程中, 为了衡量算法的性能, 这里采取两个评价函数, 第一个是方向余弦(Direction cosine, DC):
$ {\rm{D}}{{\rm{C}}_i}{\rm{(}}k{\rm{) = }}\frac{{\left| {{W}_i^{\rm T}~(k){{\pmb v}_i}} \right|}}{{\left\| {{{W}_i}~(k)} \right\|\left\| {{{\pmb v}_i}} \right\|}} $
(25) 其中, ${{W}_i}~(k)$表示在$k$时刻神经网络状态矩阵的第$i$列, 而${v_i}$则是代表着自相关矩阵${{R}}$的第$i$个次成分.显然, 如果${{W}_i}~(k)$能够收敛到次成分${v_i}$的方向, 则方向余弦的值应该收敛到1.
方向余弦只能评价状态矩阵的收敛方向, 而状态矩阵模值也是一个非常重要的评价函数:
$ {\rm{Nor}}{{\rm{m}}_i}~(k) = \left| {{W}_i^{\rm T}~(k){{W}_i}~(k)} \right|, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} i = 1, 2, \cdots, r $
(26) 当神经网络状态矩阵收敛到次成分的方向(此时方向余弦等于1)时, 如果状态矩阵模值能够收敛到一个常值, 则算法是收敛的.
4.1 多维次成分提取实验
本实验考察所提算法提取多维次成分的能力.实验中, 输入信号由式产生, 其中, 是一个随机产生的$10 \times 10$维矩阵, 而${\pmb z}~(k) \in {{{\bf R}}^{10 \times 1}}$是一个均值为零方差为${\sigma ^2} = 1$的高斯白噪声序列.这里分别采用WOJAm算法和RLS-WOJAm算法对信号的前3个次成分进行提取(即$r = 3$).两种算法的初始化参数设置如下:根据加权矩阵${a_r} > {a_{r - 1}} > \cdots > {a_1} > 0$的要求, 这里取加权矩阵$A = {\rm diag}\{3, 2, 1\}$; 根据$0 < \eta \le 1$要求, 同时也要保证算法的收敛性能, 这里取学习因子$\eta = 0.1$; 由于输入信号是一个近似平稳的随机过程, 所以这里取遗忘因子$\alpha = 0.998$; 此外RLS-WOJAm算法中初始化逆矩阵${P}~(0) = 0.001\times{I}{}_3$, 其中${I}{}_3$是一个$3 \times 3$的单位矩阵.两个算法的采取相同的初始化状态矩阵, 且该矩阵是随机产生的.仿真结果如图 1~图 4所示, 该结果是100次独立实验的平均值.
图 1和图 3分别是两种算法状态矩阵列向量与所求次成分之间的方向余弦曲线; 图 2和图 4分别是状态矩阵各列向量的模值, 黑线则是整个状态矩阵的$F$-范数.从图 1和图 3中可以看出, 经历若干次迭代后, WOJAm算法和RLS-WOJAm算法的方向余弦均收敛到1, 即两种算法均最终收敛到了信号次成分的方向.从图 2和图 3中可得:两种算法在方向余弦收敛到1的同时, 状态矩阵模值也已经收到一个常值.综合两图可以得出结论:本文所提两种算法均能够自适应地提取信号的多维次成分, 而且具有很好的收敛特性.
此外对比上述4图可以得出结论:对于方向余弦曲线和状态矩阵模值曲线, WOJAm算法和RLS-WOJAm算法的收敛情况近似相同, 只是WOJAm算法的收敛速度略快于RLS-WOJAm算法.由于RLS-WOJAm算法是由WOJAm算法推导而来, 两者本质上是相同的, 所以上述现象很容易解释.从第2.3节可得, RLS-WOJAm算法的计算复杂度远小于WOJAm算法, 因此RLS-WOJAm算法更符合实际使用需要.在后续实验中, 将重点对RLS-WOJAm算法的性能进行考核.
4.2 算法性能对比实验
为了突出所提算法的性能, 本实验将所提RLS-WOJAm算法与MCA-OOJAH算法[12]和AMMD算法[11]进行比较.实验中输入信号采用如下一阶滑动回归模型来产生:
$ x(k) = 0.75x(k - 1) + e(k) $
(27) 该模型由一个均值为零方差为1的高斯白噪声$e(k)$作为模型驱动输入.取该模型的10个不连续的输出构成神经网络的输入向量.然后利用上述三种算法对该输入信号的前3个次成分进行提取, 即$r=3$.试验中三个算法采用相同的初始化状态矩阵, 学习因子也都设置为0.1, 仿真结果如图 5~图 8所示.
图 5~图 7分别是所提次成分的方向余弦曲线, 图 8是在迭代过程中三种算法的状态矩阵模值曲线.从图 8中可以看出, 由于MCA-OOJAH算法在迭代过程中存在模值归一化操作, 所以其模值始终为一常值, 而RLS-WOJAm算法和AMMD算法虽然没有归一化操作, 但状态矩阵模值仍能收敛到一个固定值.从图 5~图 7中可以发现:在所有次成分的提取过程中, RLS-WOJAm算法的收敛速度均快于其他两种算法.
5. 结论
本文对多维次成分并行提取算法进行了研究.首先, 通过对OJAm次子空间跟踪算法进行加权改造, 提出了一种多维次成分并行提取算法; 然后, 为了降低该的计算复杂度的, 采用递归最小二乘技术导出了一种新型算法——RLS-WOJAm算法; 相比现有算法, 所提算法对信号自相关矩阵的特征值大小没有要求, 也没有模值归一化措施; 最后, 通过李雅普诺夫函数法确定了所提算法的全局收敛域.仿真实验表明:相比现有一些同类型算法, 所提算法具有较快的收敛速度.
-
[1] Thameri M, Abed-Meraim K, Belouchrani A. Low complexity adaptive algorithms for Principal and Minor Component Analysis. Digital Signal Processing, 2013, 23(1):19-29 doi: 10.1016/j.dsp.2012.09.007 [2] Arjomandi-Lari M, Karimi M. Generalized YAST algorithm for signal subspace tracking. Signal Processing, 2015, 117:82-95 doi: 10.1016/j.sigpro.2015.04.025 [3] Jou Y D, Sun C M, Chen F K. Eigenfilter design of FIR digital filters using minor component analysis. In:9th International Conference on Information, Communications and Signal Processing. Tainan, China:IEEE, 2013. 1-5 [4] Pattanadech N, Yutthagowith P. Fast curve fitting algorithm for parameter evaluation in lightning impulse test technique. IEEE Transactions on Dielectrics and Electrical Insulation, 2015, 22(5):2931-2936 doi: 10.1109/TDEI.2015.005165 [5] Cirrincione G, Cirrincione M. Neural-Based Orthogonal Data Fitting:The EXIN Neural Networks. New York, USA:John Wiley and Sons, 2011 [6] Kong X Y, Hu C H, Duan Z S. Neural networks for principal component analysis. Principal Component Analysis Networks and Algorithms. Singapore:Springer, 2017. 47-73 [7] 高迎彬, 孔祥玉, 胡昌华, 侯立安.并行提取多个次成分的改进型Möller算法.控制与决策, 2017, 32 (3):493-497 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201703015Gao Ying-Bin, Kong Xiang-Yu, Hu Chang-Hua, Hou Li-An. Modified Möller algorithm for multiple minor components extraction. Control and Decision, 2017, 32(3):493-497 http://d.old.wanfangdata.com.cn/Periodical/kzyjc201703015 [8] Oja E. Principal components, minor components, and linear neural networks. Neural Networks, 1992, 5(6):927-935 doi: 10.1016/S0893-6080(05)80089-9 [9] Mathew G, Reddy V U. Orthogonal eigensubspace estimation using neural networks. IEEE Transactions on Signal Processing, 1994, 42(7):1803-1811 doi: 10.1109/78.298287 [10] Jankovic M V, Reljin B. A new minor component analysis method based on Douglas-Kung-Amari minor subspace analysis method. IEEE Signal Processing Letters, 2005, 12(12):859-862 doi: 10.1109/LSP.2005.859497 [11] Tan K K, Lv J C, Zhang Y, Huang S N. Adaptive multiple minor directions extraction in parallel using a PCA neural network. Theoretical Computer Science, 2010, 411 48:4200-4215 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=7df63e683cd19c7aad37b172b356a6e9 [12] Bartelmaos S, Abed-Meraim K. Fast adaptive algorithms for minor component analysis using Householder transformation. Digital Signal Processing, 2011, 21(6):667-678 doi: 10.1016/j.dsp.2011.05.001 [13] Feng D Z, Zheng W X, Jia Y. Neural network learning algorithms for tracking minor subspace in high-dimensional data stream. IEEE Transactions on Neural Networks, 2005, 16(3):513-521 doi: 10.1109/TNN.2005.844854 [14] Nguyen T D, Takahashi N, Yamada I. An adaptive extraction of generalized eigensubspace by using exact nested orthogonal complement structure. Multidimensional Systems and Signal Processing, 2013, 24(3):457-483 doi: 10.1007/s11045-012-0172-9 [15] Yang B. Projection approximation subspace tracking. IEEE Transactions on Signal Processing, 1995, 43(1):95-107 doi: 10.1109/78.365290 [16] Gao Y B, Kong X Y, Hu C H, Li H Z, Hou L A. A generalized information criterion for generalized minor component extraction. IEEE Transactions on Signal Processing, 2017, 65(4):947-959 doi: 10.1109/TSP.2016.2631444 [17] Nguyen T D, Yamada I. Adaptive normalized quasi-newton algorithms for extraction of generalized Eigen-Pairs and their convergence analysis. IEEE Transactions on Signal Processing, 2013, 61(6):1404-1418 doi: 10.1109/TSP.2012.2234744 [18] Lewis D W. Matrix Theory. Singapore:World Scientific, 2012 [19] Miao Y, Hua Y. Fast subspace tracking and neural network learning by a novel information criterion. IEEE Transactions on Signal Processing, 1998, 46(7):1967-1979 doi: 10.1109/78.700968 [20] Gao Y B, Kong X Y, Hu C H, Zhang H H, Hou L A. Convergence analysis of Möller algorithm for estimating minor component. Neural Processing Letters, 2014, 42(2):355-368 doi: 10.1007/s11063-014-9360-y [21] Kong X Y, Hu C H, Ma H G, Han C Z. A unified self-stabilizing neural network algorithm for principal and minor components extraction. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(2):185-198 doi: 10.1109/TNNLS.2011.2178564 -
下载:
下载:
计量
- 文章访问数: 1677
- HTML全文浏览量: 193
- PDF下载量: 445
- 被引次数: 0
