2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于CGLS和LSQR的联合优化的匹配追踪算法

陈善雄 熊海灵 廖剑伟 周骏 左俊森

孔令智, 高迎彬, 李红增, 张华鹏. 一种快速的多个主成分并行提取算法. 自动化学报, 2017, 43(5): 835-842. doi: 10.16383/j.aas.2017.c160299
引用本文: 陈善雄, 熊海灵, 廖剑伟, 周骏, 左俊森. 一种基于CGLS和LSQR的联合优化的匹配追踪算法. 自动化学报, 2018, 44(7): 1293-1303. doi: 10.16383/j.aas.2018.c160569
KONG Ling-Zhi, GAO Ying-Bin, LI Hong-Zeng, ZHANG Hua-Peng. A Fast Algorithm That Extracts Multiple Principle Components in Parallel. ACTA AUTOMATICA SINICA, 2017, 43(5): 835-842. doi: 10.16383/j.aas.2017.c160299
Citation: CHEN Shan-Xiong, XIONG Hai-Ling, LIAO Jian-Wei, ZHOU Jun, ZUO Jun-Sen. A Matching Pursuit Algorithm of Jointing Optimization Based on CGLS and LSQR. ACTA AUTOMATICA SINICA, 2018, 44(7): 1293-1303. doi: 10.16383/j.aas.2018.c160569

一种基于CGLS和LSQR的联合优化的匹配追踪算法

doi: 10.16383/j.aas.2018.c160569
基金项目: 

重庆市博士后科研项目 Xm2016041

国家自然科学基金 61303227

中国博士后基金 2015M580765

详细信息
    作者简介:

    熊海灵  西南大学计算机与信息科学学院教授.2007年获得西南大学数字农业方向农学博士学位.主要研究方向为数据库与智能信息处理, 计算机模拟及其应用.E-mail:xionghl@swu.edu.cn

    廖剑伟  西南大学计算机与信息科学学院副教授.2012年获日本东京大学计算机科学博士学位.主要研究方向为系统软件和高性能分布式存储.E-mail:liaotoad@gmail.com

    周骏  西南大学计算机与信息科学学院副教授.2013年获得电子科技大学计算机应用技术博士学位, 2014~2015年在罗切斯特大学(University ofRochester)做博士后研究.主要研究方向为图像处理, 计算机视觉, 分子影像.E-mail:zhouj@swu.edu.cn

    左俊森  西南大学计算机与信息科学学院硕士研究生.主要研究方向为数据库与智能检索技术, 计算机模拟及其应用.E-mail:zuojunsen@email.swu.edu.cn

    通讯作者:

    陈善雄  西南大学计算机与信息科学学院副教授.2013年获得重庆大学计算机科学与技术博士学位.主要研究方向为数据挖掘, 模式识别, 压缩感知.本文通信作者.E-mail:csxpml@163.com

A Matching Pursuit Algorithm of Jointing Optimization Based on CGLS and LSQR

Funds: 

Chongqing Postdoctoral Science Foundation Xm2016041

National Natural Science Foundation of China 61303227

China Postdoctoral Science Foundation 2015M580765

More Information
    Author Bio:

     Professor at the College of Computer and Information Science, Southwest University. He received his Ph. D. degree in agronomy from Southwest University in 2007. His research interest covers database and intelligent information processing, computer simulation and application

     Associate professor at the College of Computer and Information Science. He received his Ph. D. degree in computer science from Tokyo University in 2012. His research interest covers system software and high performance storage system

     Associate professor at the College of Computer & Information Science, Southwest University. He received Ph.D. degree in computer science from the Electronic Science and Technology of China in 2013. He did one year postdoctor at University of Rochester, USA in August, from 2014 to 2015. His research interest covers image processing, computer vision, and molecular imaging

     Master student at the College of Computer and Information Science, Southwest University. His research interest covers database and intelligent retrieval techniques, computer simulation and application

    Corresponding author: CHEN Shan-Xiong  Associate professor at the College of Computer and Information Science, Southwest University. He received his Ph. D. degree in computer science from Chongqing University in 2013. His research interest covers data mining, pattern recognition, compressed sensing. Corresponding author of this paper
  • 摘要: 在压缩感知理论中,设计好的稀疏重构算法是一个比较重要,同时也是一个具有挑战性的问题.稀疏重构的基本目标是用较少的数据样本,通过解一个优化问题完成信号或者图像重构.关于稀疏重构过程,一个重要的研究方向是在数据受噪声干扰的情况下,如何高效快速地重建原信号.本文提出了基于共轭梯度最小二乘法(Conjugate gradient least squares,CGLS)和最小二乘QR分解(Least squares QR,LSQR)的联合优化的匹配追踪算法.该算法采用Alpha散度来测量CGLS和LSQR之间的离散度(差异度),并通过离散度来选择最优的解序列.实验分析表明基于CGLS和LSQR的联合优化的匹配追踪算法在压缩采样的信号受噪声干扰情况下具有较好的恢复能力.
  • 在现代信号处理和数据分析领域, 从高维输入信号中提取能够反映系统本质属性的信息是一件非常有意义的工作, 通常将能够完成此类工作的方法称为系统特征提取方法, 而主成分分析方法是应用比较广泛的一种系统特征提取方法.主成分分析主要是通过正交变换将高维的数据映射到低维空间, 从而达到数据压缩和系统特征提取的目的[1].在信号处理领域, 通常又将输入信号自相关矩阵最大特征值对应的特征向量称之为信号的主成分, 将由信号的多个主成分张成的子空间称为信号的主子空间, 而将能够实现对输入信号的主成分或主子空间进行提取的方法称为主成分分析方法[2].目前, 主成分分析方法已经广泛应用于图像处理[3]、故障诊断[4]、模式识别[5]等领域.

    采用神经网络方法来提取输入信号中的主成分是目前国内外的一个研究热点.因为相比传统的数值算法, 如EVD (Eigenvalue decomposition)和SVD (Singular value decomposition), 神经网络算法可以避免对输入信号自相关矩阵的计算, 而且能够处理非平稳的随机输入信号.自从Oja提出的第一个主成分分析神经网络算法以来[6], 学者们相继提出了很多主成分分析算法, 如NIC (Novel information criterion)算法[7]、ULA (Unified learning algorithm)算法[8]、UIC (Unified information criterion)算法[9]等.虽然这些算法已经在各个领域得到了广泛的应用.但是这些算法在应用范围上仍然存在一定的限制, 如Oja算法和ULA算法只能提取一个主成分; NIC算法和UIC算法只能进行主子空间跟踪, 不能提取多个主成分.而在某些信号处理领域需要对信号的多个主成分进行提取, 因此研究如何提取多个主成分就成为一件非常有意义的工作.

    目前为止, 学者们已经提出了一些多个主成分提取算法.根据主成分的获取方式不同, Ouyang等将现行算法分为串行算法和并行算法两类[10].串行算法首先采用单个主成分提取算法提取信号的第一个主成分, 然后采用压缩技术对采样信号进行处理, 消除信号中第一个主成分的影响, 而后依旧采用单个主成分提取算法来提取信号的第二个主成分; 重复上述步骤, 就可以实现多个主成分的提取.串行算法的缺点主要有以下4个方面: 1) 由于串行算法在每次提取过程中都需要用到全部的采样数据, 因此需要大量的存储器件; 2) 由于主成分的提取过程是顺序进行的, 因此会造成很大的提取时延; 3) 由于下一个主成分的提取依赖于当前主成分的提取结果, 因此当前主成分的提取误差会传播到下一次提取过程中, 当提取主成分的维数很大时, 串行算法会造成很大的误差累积; 4) 串行算法必须是信号全部采集完成后才能使用, 因此难以满足实时信号处理的要求.相比串行算法, 并行算法可以在一个算法迭代过程中实现多个主成分的同时提取, 因此可以避免串行算法的上述缺点.此外由于并行算法还具有很好的实时性, 因此引发了大量学者的研究.

    在文献[11]中, Oja等采用对神经网络输出进行加权的方式, 提出了第一个多个主成分并行提取算法; Ouyang等则是对NIC算法进行了加权改进, 提出了一种非对称结构的算法---WNIC (Weighted NIC)算法[10]; Tanaka等[12]对加权的Oja算法进行改进, 提出了一类更为一般化的多个主成分提取算法; 通过对正交投影子空间跟踪算法(Orthogonal projection approximation and subspace tracking, OPAST)进行适当改进, Bartelmaos等提出了一种可以并行提取多个主成分的PC-OPAST (Principal component-OPAST)算法[13], 仿真实验表明PC-OPAST算法的估计精度要高于WNIC算法; Li等通过对NIC算法进行了改进, 提出了一种具有对称结构的算法---MNIC (Modified NIC)算法[14];此后基于Givens空间旋转变换法, Thameri等[15-16]采用提出了4种不同类型的多个主成分并行提取算法(MED-GOPAST (Maximum error deviation-generalized OPAST)、IMED-GOPAST (Improved MED-generalized OPAST)、AS-GOPAST (Automatic selection-generalized OPAST)、H-GOPAST (Hybrid-generalized OPAST)).相比上述其他算法, Thameri等所提算法具有较低的计算复杂度.然而, 上述大多数并行提取算法都属于二阶算法, 算法的收敛速度较慢.为了进一步提升算法的收敛速度, 本文提出了一种新型的算法.

    本文的章节安排如下:第1节主要介绍本文中符号的命名规则和重要符号说明; 第2节根据现有的算法提出了一种新型的多个主成分提取算法; 第3节主要是对算法进行收敛性分析; 算法的自稳定性证明安排在第4节; 第5节是算法的数值仿真和实际应用; 第6节是本文的结论.

    为了规范符号使用, 这里对本文中符号的使用规则进行确定.在本文中, 矩阵用斜体大写字母表示(如 ${{R}}$ ); 而加粗的斜体小写字母则代表向量(如 ${{\pmb y}}$ ); 标量一般用不加粗的斜体小写字母表示(如 $\eta $ ).此外, 这里还给出了一些常用符号的含义:

    ${{R}}$ 向量的自相关矩阵

    ${{W}}$ 神经网络的权矩阵

    ${{A}}$ 加权矩阵

    $\eta $ 神经网络的学习因子

    $\alpha$ 遗忘因子

    $n$ 提取主成分的维数

    考虑满足如下多输入多输出关系的线性神经网络模型:

    $ \begin{equation} {{\pmb y}}(k)= {{{W}}^{\rm T}}(k){{\pmb x}}(k) \end{equation} $

    (1)

    其中, ${{\pmb y}}(k)\in\textbf{R}{^{r \times 1}}$ 是神经网络的输出, ${{W}}(k)\in \textbf{R} {^{n \times r}}$ 是神经网络的权矩阵, 输入信号 ${{\pmb x}}(k)\in {\textbf{R}^{n \times 1}}$ 是一个零均值的随机过程, 这里作为神经网络的输入, $n$ 代表输入向量的维数, $r$ 代表所需提取主成分的维数.

    令为输入信号的自相关矩阵, ${\lambda _i}$ 和分别为自相关矩阵 ${{R}}$ 的特征值和对应的特征向量.则根据矩阵理论的知识可得:矩阵 ${{R}}$ 是一个对称正定矩阵, 且其特征值均是非负的.对矩阵 ${{R}}$ 进行特征值分解得:

    $ \begin{equation} {{R}} = {{U\Lambda }}{{{U}}^{\rm T}} \end{equation} $

    (2)

    其中, 是由矩阵 ${{R}}$ 的特征向量构成的矩阵, 是由矩阵 ${{R}}$ 的特征值组成的对角矩阵.为了后续使用方便, 这里将特征值按照降序的方式进行排列, 即特征值满足如下方程:

    $ \begin{equation} {\lambda _1} > {\lambda _2} > \cdots > {\lambda _r} > \cdots > {\lambda _n} > 0 \end{equation} $

    (3)

    根据主成分的定义可知, 特征值所对应的特征向量称为矩阵 ${{R}}$ 的前 $r$ 主成分, 而通常将由这些主成分张成的空间称为信号的主子空间.而多个主成分提取算法的任务就是构造合适的神经网络权矩阵迭代更新方程, 使神经网络的权矩阵能够收敛到矩阵 ${{R}}$ 的前 $r$ 主成分.

    在文献[11]中, Oja等利用加权子空间法提出了多个主成分并行提取算法, 其算法形式为:

    $ \begin{align} {{W}}(k + 1)=& {{W}}(k)+ \eta [{{RW}}(k)- \nonumber\\ &{{W}}(k){{{W}}^{\rm T}}(k){{RW}}(k){{A}}] \end{align} $

    (4)

    其中, $\eta$ 是神经网络的学习因子且满足关系 $0< \eta <1$ , $A$ 是一个 $r \times r$ 维对角矩阵且其对角线元素为: .在式(4) 所描述的学习算法的约束下, 神经网络算法的权矩阵将收敛到信号自相关矩阵 ${{R}}$ 的前 $r$ 个主成分.然而算法(4) 存在收敛速度慢的问题, 为此本文提出了如下算法, 其算法形式为:

    $ \begin{align} {{W}}(k &+ 1) =\nonumber\\ &{{W}}(k)+ \eta {{W}}(k)[{({{{W}}^{\rm T}}(k){{W}}(k))^{-1}}- \nonumber\\ &{{I}}]+\eta ({{RW}}(k){{{W}}^{\rm T}}(k){{W}}(k){{{A}}^2} -\nonumber\\ &{{W}}(k){{A}}{{{W}}^{\rm T}}(k){{RW}}(k){{A}}) \end{align} $

    (5)

    其中矩阵 ${{A}}$ 同样为一个 $r \times r$ 维对角矩阵且其对角线元素为: ${a_1} > {a_2} > \cdots > {a_r} > 0$ , 这点是与算法(4) 一致的.式(5) 是一种全新的多个主成分提取算法.对比式(4) 和式(5) 可以发现, 式(5) 是一个非二阶的算法.根据文献[9]的结论, 非二阶算法可以在算法迭代过程中引入一个自适应的学习因子, 进而加速算法的收敛速度.因此式(5) 所描述的算法应具有较快的收敛速度, 这点将在稍后的仿真实验部分予以验证.

    在主成分分析神经网络算法领域, 通常将与学习因子相乘的项称为算法的学习步长[9].显然, 式(5) 中算法的学习步长由两部分构成.为了简便起见, 这里令矩阵和矩阵.如果令式(5) 中的加权矩阵 ${{A}} = {{I}}$ , 且省去算法的矩阵 $C$ , 则算法退化成为另外一种主成分分析算法---Chen算法[17].然而仅仅由矩阵 ${{B}}$ 构成学习步长时, 算法很容易发生边界不稳定现象.为此, 需要对神经网络的加权矩阵加以限制, 最常用的方法就是增加正交约束[9].这里采用了一个非二阶的权矩阵约束措施(即添加矩阵 $C$ ), 这一操作不仅可以解决算法的不稳定问题, 还可以提升算法的收敛速度.

    式(5) 所描述的算法只适用于自相关矩阵已知的情况, 而在实际使用时只能得到信号的观测值, 自相关矩阵通常是未知的且是需要实时估计的.这里给出自相关矩阵的估计公式:

    $ \begin{equation} {{\hat R}}(k)= \frac{{(k - 1)}}{k}\alpha {{\hat R}}(k - 1)+ \frac{{{{{\pmb x}}_k}{{\pmb x}}_k^{\rm T}}}{k} \end{equation} $

    (6)

    其中, $\alpha$ 为遗忘因子, 且满足 $0<\alpha <1$ .显然当时, 矩阵 ${{\hat R}}(k)\to {{R}}$ .因此式(5) 在实际使用时, 应首先使用式(6) 对自相关矩阵进行估计, 然后将估计得到的矩阵代入式(5), 即可以完成对输入信号多个主成分的提取.为方便使用, 这里将式(5) 所描述的算法记为FMPCE (Fast multiple principle components extraction algorithm)算法.

    本节将对所提算法在平稳点处的收敛特性进行分析, 相关结论由定理1给出.

    定理1. 当且仅当权矩阵 ${{W}} = {{P}}$ 时, 式(5) 所描述的FMPCE算法达到稳定状态, 其中 $P$ 是由矩阵 $R$ 的前 $r$ 个特征值对应的特征向量构成的矩阵, 即有.

    证明. 根据文献[18]的描述, 算法的学习步长通常为一个损失函数的梯度.通过对损失函数平稳点的分析就可以完成算法收敛性的分析.这里假设该损失函数为 $JW$ , 则该损失函数对于权矩阵 $W$ 的一阶微分可以表示为:

    $ \begin{align} \nabla J({{W}})&=\nonumber \\ &{{RW}}{{{W}}^{\rm T}}{{W}}{A^2} - {{WA}}{{{W}}^{\rm T}}{{RWA}}+ \nonumber\\ & {{W}}{({{{W}}^{\rm T}}{{W}})^{ - 1}} - {{W}} \end{align} $

    (7)

    如果权矩阵 ${{W}} = {{P}}$ , 则有

    $ \begin{align} \nabla J({{W}})&|_{W= P}=\nonumber\\& {{RP}}{{{P}}^{\rm T}}{{P}}{{{A}}^2} - {{PA}}{{{P}}^{\rm T}}{{RPA}}~+ \nonumber\\&{{P}}{({{{P}}^{\rm T}}{{P}})^{ - 1}} - {{P}}=\nonumber\\& {{P}}{{{\Lambda }}_r}{{{A}}^2} - {{PA}}{{{\Lambda }}_r}{{A}}= {{0}} \end{align} $

    (8)

    其中, 是由矩阵 $R$ 的前 $r$ 个特征值构成的对角矩阵.反之, 根据矩阵分析理论, 在平稳点处有 $\nabla J({{W}})= {{0}}$ , 即

    $ \begin{equation} \begin{split} &{{RW}}{{{W}}^{\rm T}}{{W}}{{{A}}^2} - {{WA}}{{{W}}^{\rm T}}{{RWA}} = \\ &~~~~~~~~~{{W}} - {{W}}{({{{W}}^{\rm T}}{{W}})^{ - 1}} \end{split} \end{equation} $

    (9)

    对上式两边左乘以 ${{{W}}^{\rm T}}$ , 可得

    $ \begin{equation} \begin{split} &{{{W}}^{\rm T}}{{RW}}{{{W}}^{\rm T}}{{W}}{{{A}}^2} - {{{W}}^{\rm T}}{{WA}}{{{W}}^{\rm T}}{{RWA}}=\\ & \quad\quad\quad\quad {{{W}}^{\rm T}}{{W}} - {{I}} \end{split} \end{equation} $

    (10)

    定义矩阵 ${{Q}} = {{{W}}^{\rm T}}{{W}} - {{I}}$ , 则矩阵 $Q$ 是一个对称矩阵, 由于权矩阵 $W$ 的任意性, 则有矩阵和分别是两个对称矩阵, 即有

    $ \begin{equation} {{{W}}^{\rm T}}{{RW}}{{{W}}^{\rm T}}{{W}}{{{A}}^2} = {{{A}}^2}{{{W}}^{\rm T}}{{W}}{{{W}}^{\rm T}}{{RW}} \end{equation} $

    (11)

    $ \begin{equation} {{{W}}^{\rm T}}{{WA}}{{{W}}^{\rm T}}{{RWA}} = {{A}}{{{W}}^{\rm T}}{{RWA}}{{{W}}^{\rm T}}{{W}} \end{equation} $

    (12)

    由于矩阵 ${{{W}}^{\rm T}}{{RW}}$ 和矩阵 $A$ 均是对称矩阵, 则根据上面两式可得 ${{{W}}^{\rm T}}{{W}} = {{I}}$ .也就是说, 在 $J({{W}})$ 的平稳点处权矩阵 $W$ 的各列向量之间是相互正交的.将其代入式(9) 可得, $J({{W}})$ 平稳点有:

    $ \begin{equation} {{RW}}{{{A}}^2} = {{WA}}{{{W}}^{\rm T}}{{RWA}} \end{equation} $

    (13)

    令是矩阵的特征值分解, 其中 $Q$ 是一个正交矩阵.将其代入式(13) 可得: ${{RP'}} = {{P'}}{{{\Lambda '}}_r}$ , 其中, .由于矩阵 ${{{\Lambda '}}_r}$ 是一个对角矩阵且 ${{P'}}$ 是一个列满秩矩阵, 则矩阵 ${{{\Lambda'}}_r}$ 和 ${{P'}}$ 必定等于矩阵 ${{{\Lambda }}_r}$ 和 ${{P}}$ .

    下面对加权矩阵 ${{A}}$ 的作用做进一步讨论.令和 ${{{R}}_y} = {{{W}}^{\rm T}}{{RW}}$ , 将其代入式(13) 并进行适当化简可得:

    $ \begin{equation} {{W}} = {{{R}}_{xy}}{({{A}}{{{R}}_y}{{{A}}^{ - 1}})^{ - 1}} \end{equation} $

    (14)

    矩阵的作用就是对矩阵 ${{{R}}_{xy}}$ 的各列向量施加Gram-Schmidt正交化操作[19].由于矩阵是一个非对称矩阵且矩阵的各元素可以写为:

    $ \begin{align} \begin{array}{l} {{A}}{{{R}}_y}{{{A}}^{ - 1}}=~~~~~\\ ~~~ \left[{\begin{array}{*{10}{c}} {{\rm E}\{ z_1^2\} }&{\dfrac{{{a_1}}}{{{a_2}}}z}&{\dfrac{{{a_1}}}{{{a_3}}}z}& \cdots &{\dfrac{{{a_1}}}{{{a_r}}}z}\\ {\dfrac{{{a_2}}}{{{a_1}}}z}&{{\rm E}\{ z_2^2\} }&{\dfrac{{{a_2}}}{{{a_3}}}z}& \cdots &{\dfrac{{{a_2}}}{{{a_r}}}z}\\ \vdots&\vdots&\vdots &\ddots&\vdots \\ {\dfrac{{{a_r}}}{{{a_1}}}z}&{\dfrac{{{a_2}}}{{{a_r}}}z}&{\dfrac{{{a_3}}}{{{a_r}}}z}& \cdots &{{\rm E}\{ z_r^2\} } \end{array}} \right] \end{array} \end{align} $

    (14)

    其中用 $z$ 来代表矩阵 ${{{R}}_y}$ 的元素.根据式(15) 可得矩阵 ${{{R}}_y}$ 的上三角部分的元素均是乘以一个大于1的数, 而下三角部分则是乘以一个小于1的数.通过使用第一列正交化 ${{R}}_{xy}$ 可以获得矩阵 ${{{R}}}$ 的第一个主成分, 通过第二列正交化 ${{R}}_{xy}$ 可以获得矩阵 ${{{R}}}$ 的第二个主成分, 依次类推.值得注意的是第二列中只有一个大于1的系数 ${{a}_{1}}/{{a}_{2}}$ , 而其他所有系数均是小于1.根据文献[20]可得, 系数 ${{a}_{1}}/{{a}_{2}}$ 可以避免后续操作对已经提取的主成分造成影响.上述分析表明, 可以通过合理的选择加权矩阵 ${{A}}$ , 使得算法最终将能够实现对矩阵 $R$ 的多个主成分的提取.

    自稳定性是指不论神经网络初始权矩阵如何选择, 神经网络权矩阵的模值均能收敛到一个常值, 而与初始权矩阵无关.在文献[21]中Möller指出:所有不具备自稳定性的神经网络算法都具有发散的可能性, 因此自稳定性已经成为了神经网络算法的一个必备特性.本节将对FMPCE算法的自稳定性进行分析证明.

    定理2. 如果输入信号是有界的且学习因子 $\eta$ 足够小, 则FMPCE算法的权矩阵模值将收敛到一个常值(该值等于提取主成分维数的均方根, 即 $\sqrt{r}$ ), 而与初始权矩阵的选择无关.

    证明. 根据式(5) 可得, 在 $k+1$ 时刻权矩阵的模值为:

    $ \begin{align*} \begin{array}{l} \left\| {{{W}}(k + 1)} \right\|_F^2=~~~~\\ ~~~~~~~~ {\rm tr}\left[{{{{W}}^{\rm T}}(k + 1){{W}}(k + 1)} \right]=\\~~~~~~~~ {\rm tr}\left\{ {\left[{{{W}} + \eta {{RW}}{{{W}}^{\rm T}}{{W}}{{{A}}^2}- \eta {{W}}-} \right.} \right.\\~~~~~~~~ {\left. {\eta {{WA}}{{{W}}^{\rm T}}{{RWA}} + \eta {{W}}{{({{{W}}^{\rm T}}{{W}})}^{-1}}} \right]^{\rm T}}\times\\~~~~~~~~ \left[{{{W}} + \eta {{W}}{{({{{W}}^{\rm T}}{{W}})}^{-1}}-\eta {{W}}} \right. + \\~~~~~~~~ \left. {\left. { \eta {{RW}}{{{W}}^{\rm T}}{{W}}{{{A}}^2}-\eta {{WA}}{{{W}}^{\rm T}}{{RWA}}} \right]} \right\}=\\~~~~~~~~ {\rm tr}\left\{ {{{{W}}^{\rm T}}{{W}} + 2\eta {{{W}}^{\rm T}}{{RW}}{{{W}}^{\rm T}}{{W}}{{{A}}^2}}- \right.\\~~~~~~~~ 2\eta {{{W}}^{\rm T}}{{WA}}{{{W}}^{\rm T}}{{RWA}} - 2\eta {{{W}}^{\rm T}}{{W}}+ \\~~~~~~~~ 2\eta {{{W}}^{\rm T}}{{W}}{({{{W}}^{\rm T}}{{W}})^{ - 1}} + o(\eta ) \approx\\~~~~~~~~ {\rm tr}\left\{ {{{{W}}^{\rm T}}{{W}}} \right\} + 2\eta {\rm tr}\left\{ {{{I}} - {{{W}}^{\rm T}}{{W}}} \right\} \end{array}\\[-6mm] \end{align*} $

    (16)

    在上式中为了书写方便, 而省略了第二个等号以后的迭代时刻符号 $k$ .由于学习因子足够小, 因此可以忽略有关学习因子的二阶项.对比前后两个时刻权矩阵模值的大小可得:

    $ \begin{equation} \begin{split} &\frac{{\left\| W(k + 1) \right\|_F^2}}{{\left\| {{{W}}(k)} \right\|_F^2}}=~~~~~~~~~~~~\\ &~~~~~~~~~~~~1+\frac{{ 2\eta {\rm tr}\left\{ {{{I}} - {{{W}}^{\rm T}}(k){{W}}(k)} \right\}}}{{{\rm tr}\left\{ {{{{W}}^{\rm T}}(k){{W}}(k)} \right\}}}=\\ &~~~~~~~~~~~~ 1 + 2\eta \frac{{r - \left\| {{{W}}(k)} \right\|_F^2}}{{\left\| {{{W}}(k)} \right\|_F^2}}~~~~~~\\ &~~~~~~~~~~~~ \left\{ {\begin{array}{*{20}{c}} { > 1}, &\mbox{若}&{\left\| {{{W}}(k)} \right\|_F^{} < \sqrt r }\\ { = 1}, &\mbox{若}&{\left\| {{{W}}(k)} \right\|_F^{} = \sqrt r }\\ { < 1}, &\mbox{若}&{\left\| {{{W}}(k)} \right\|_F^{} > \sqrt r } \end{array}} \right. \end{split} \end{equation} $

    (17)

    通过式(17) 可以发现, 无论 $k$ 时刻的权矩阵模值是否等于 $\sqrt r $ , 下一时刻 $k+1$ 的权矩阵模值都将趋于 $\sqrt r $ , 即在收敛时权矩阵模值将趋于一个常数.这一特性表明, 无论初始时刻的权矩阵模值如何选择, 将不会对算法的收敛结果造成任何影响, 即FMPCE算法具有自稳定性.

    本节将提供4个仿真实验来对所提算法的性能进行验证.第一个实验主要验证FMPCE算法提取信号中多个主成分的能力; 第二实验主要考察FMPCE算法的自稳定性; 第三个实验则是将FMPCE算法与一些现存的多个主成分提取算法进行比较; 第四个实验则是应用FMPCE算法进行图像压缩和重建并与一些现有算法进行比较.在整个实验过程中, 为了定量地对算法性能进行评价, 这里引入如下两个评价函数, 第一个是方向余弦(Direction cosine, DC):

    $ \begin{equation} {\rm DC}_i(k)= \frac{{\left| {{{\pmb w}}_i^{\rm T}(k){{{\pmb u}}_i}} \right|}}{{\left\| {{{\pmb w}_i}(k)} \right\| \cdot \left\| {{{{\pmb u}}_i}} \right\|}} \end{equation} $

    (18)

    其中, $i = 1, 2, \cdots, r$ 且 ${{{\pmb w}}_i}$ 代表权矩阵 $W$ 的第 $i$ 列, ${{{\pmb u}}_i}$ 则代表信号的第 $i$ 个主成分.从式(18) 可以得出:如果方向余弦曲线能够收敛到1, 神经网络算法的权矩阵必定已经收敛到信号主成分的方向.方向余弦衡量的是算法的估计精度, 而权向量模值则能够评价算法的收敛性.

    $ \begin{equation} {\rm{Nor}}{{\rm{m}}_i}{\rm{(}}k{\rm{)= }}\left\| {{{{\pmb w}}_i}(k)} \right\|, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} i = 1, 2, \cdots, r \end{equation} $

    (19)

    本实验采用文献[10]中所使用的信号产生方法, 输入信号采用如下一阶滑动回归模型来产生:

    $ \begin{equation} x(k)= 0.75x(k - 1)+ e(k) \end{equation} $

    (20)

    该模型由一个均值为0方差为1的高斯白噪声 $e(k)$ 作为模型驱动输入.取该模型的10个不连续的输出构成神经网络的输入向量, 即 $n=10$ .接下来采用本文所提出的FMPCE算法对该输入信号的前3个主成分进行提取, 即 $r=3$ . FMPCE算法的初始化参数设置为:初始权矩阵为随机的, 学习因子 $\eta=0.1$ , 加权矩阵 ${{A}} ={\rm diag}\{3, 2, 1\}$ .图 1图 2分别给出了FMPCE算法的仿真结果, 在该图中, 所有学习曲线均是为100次独立实验的平均结果.

    图 1  FMPCE算法的方向余弦曲线
    Fig. 1  DC curves of FMPCE
    图 2  FMPCE算法的权向量模值曲线
    Fig. 2  Norm curves of FMPCE

    图 1中可以看出:大约经过1500次左右的迭代后, FMPCE算法的3条方向余弦曲线就都收敛到了1, 这就说明FMPCE算法的权矩阵已经收敛到了信号主成分的方向; 对照图 2可以看出, 经过30次迭代运算后, 权矩阵模值均已经收敛到1, 也就是说此时的FMPCE算法已经收敛.该仿真实验表明: FMPCE算法具备提取信号多个主成分的能力.

    本实验主要对FMPCE算法的自稳定性进行仿真验证.本实验同样采取式(20) 产生的输入信号. FMPCE算法的初始化参数设置为:学习因子 $\eta = 0.01$ , 加权矩阵, 初始化权矩阵为随机产生的且其模值被标准化为模值大于3, 等于3和小于3等情况.然后分别考察在这种不同初始权矩阵情况下, FMPCE算法的权矩阵模值收敛情况.

    图 3是经过100次独立仿真获得的FMPCE算法权矩阵模值曲线, 从图 3中可以看出:不论初始权矩阵如何选择, FMPCE算法收敛时权矩阵模值均等于 $\sqrt{3}$ , 这点是与定理2中的分析一致的.通过该实验可得: FMPCE算法具有自稳定性.

    图 3  不同初始条件下FMPCE算法的权矩阵模值曲线
    Fig. 3  Norm curves of FMPCE under different conditions

    本节将所提出的FMPCE算法与文献[14]中的MNIC算法和文献[15]中的MED-GOPAST算法进行对比.本实验中的输入信号同样由式(20) 产生, 这里分别采用这三种算法对该输入信号的前2个主成分进行提取, 即 $r=2$ .三种算法的初始化参数设置为:对MNIC算法和FMPCE算法而言, 加权矩阵 ${{A}} ={\rm diag}\{2, 1\}$ , 学习因子 $\eta = 0.15$ ; 对MED-GOPAST算法而言, 遗忘因子 $\alpha = 0.998$ .为了公平比较, 三种算法的初始化权矩阵均是随机产生的.三种算法对于该信号的提取结果如图 4图 5所示, 该结果是100次独立实验结果的平均值.

    图 4  三种算法提取第一个主成分的方向余弦曲线
    Fig. 4  DC curves of three algorithms for the 1st PC
    图 5  三种算法提取第二个主成分的方向余弦曲线
    Fig. 5  DC curves of three algorithms for the 2nd PC

    图 4图 5中可以看出:大约经历了200次左右的迭代运算后, FMPCE算法的方向余弦曲线就已经收敛到了1, 这一收敛速度要优于MED-GOPAST算法和MNIC算法.从上面两图的最后放大结果中还可以看出, 虽然三种算法均收敛到了单位1, 但是三种算法的最终收敛值并不相同:其中MNIC算法与单位1偏差最大, MED-GOPAST算法次之, 三种算法中FMPCE算法偏差最小.由于方向余弦可以表征算法的估计精度, 所以可以说在这三种算法中, FMPCE算法具有最好的估计精度.通过此实验可以得出结论: FMPCE算法不仅具有较快的收敛速度, 而且具有很高的估计精度.

    图像压缩一直是计算机图形图像学领域内的热点问题, 通过图像压缩技术可以减小图像数据中的冗余信息从而实现更加高效的格式存储和数据传输, 而基于主成分分析的压缩方法又是图像压缩领域内的一种常用方法[22].本小节将采用主成分分析方法对著名的Lena图像进行压缩和重构. Lena原始图像如图 6(a)所示, 该图像的分辨率512像素 $\times$ 512像素.这里将Lena图像分解为若干个8像素 $\times$ 8像素的不重叠小块并将这些小块按照从左到右从上到下的顺序排列, 就构成了一个64维的数据向量.将这些数据进行中心化处理后作为主成分分析算法的输入序列.然后分别采用FMPCE算法、MED-GOPAST算法和MNIC算法对Lena图像进行压缩后重建.

    图 6  原始的与重构后的Lena图像
    Fig. 6  Original and reconstituted Lena images

    三种算法的初始化参数设置方法与第5.3节相同, 这里不再重复.图 6(b) $\sim$ (d)分别给出了在重构维数为1, 4, 7三种不同情况下采用FMPCE算法对于Lena图像的重构结果, 表 1给出了在不同的重构维数下, 三种算法的重构误差.从图 6表 1中可以得出:利用FMPCE算法对Lena图像进行压缩重构可以获得较清晰的重构图像和较低的重构误差, 即可以利用FMPCE算法解决图像重构问题.对比三种不同算法的重构误差还可以发现, 在相同的重构维数下FMPCE算法具有最小的重构误差, 即FMPCE算法对提取的主成分具有最高的估计精度, 这点是与第5.3节中的结论一致的.

    表 1  不同重构维数下三种算法的重构误差
    Table 1  Reconstitution errors of the three algorithms with different reconstitution dimensions
    重构维数 1 4 7
    FMPCE 0.094 0.0837 0.0813
    MED-GOPAST 0.0959 0.0852 0.0846
    MNIC 0.1283 0.1015 0.0933
    下载: 导出CSV 
    | 显示表格

    本文首先对一些多个主成分提取并行算法进行了研究, 针对现有算法收敛速度慢的问题, 提出了一种新的具有较快收敛速度的非二阶算法, 该算法可以从输入信号中并行提取多个主成分; 然后采用平稳点分析法对所提算法的收敛性和自稳定性进行了证明; 最后通过仿真实验对所提算法的性能进行了验证.仿真结果表明:相比一些现有算法, 所提算法不仅收敛速度快而且估计精度较高.


  • 本文责任编委 孙富春
  • 图  1  OMP、StOMP、CoSaOMP、ROMP和COCLMP在噪声干扰下对稀疏信号的重构效果

    Fig.  1  Reconstruction effect of sparse signals include noise for OMP, StOMP, CoSaOMP, ROMP, COCLMP

    图  2  噪声干扰的不同采样次数下OMP、StOMP、CoSaOMP、ROMP、COCLMP算法重构结果

    Fig.  2  Reconstruction result include noise under different sampling number for OMP, StOMP, CoSaOMP, ROMP, COCLMP

    图  3  噪声干扰下OMP、StOMP、CoSaOMP、ROMP、COCLMP算法对图像的重构效果

    Fig.  3  Image reconstruction effect include noise for OMP, StOMP, CoSaOMP, ROMP, COCLMP

    图  4  噪声下重构Lena、aerial、man、boat图的PSNR

    Fig.  4  The PSNR of reconstructing Lena, aerial, man, boat include noise

  • [1] Moshtaghpour A, Jacques L, Cambareri V, Degraux K, De Vleeschouwer C. Consistent basis pursuit for signal and matrix estimates in quantized compressed sensing. IEEE Signal Processing Letters, 2016, 23(1):25-29 doi: 10.1109/LSP.2015.2497543
    [2] Zhao W Q, Beach T H, Rezgui Y. Efficient least angle regression for identification of linear-in-the-parameters models. Proceedings of the Royal Society A:Mathematical, Physical and Engineering Sciences, 2017, 473(2198):Article No.20160775 doi: 10.1098/rspa.2016.0775
    [3] Lee H C, Song B, Kim J S, Jung J J, Li H H, Mutic S, et al. An efficient iterative CBCT reconstruction approach using gradient projection sparse reconstruction algorithm. Oncotarget, 2016, 7(52):87342-87350 http://europepmc.org/abstract/MED/27894103
    [4] 许志强.压缩感知.中国科学:数学, 2012, 42(9):865-877 https://www.wenkuxiazai.com/doc/3851fb1eff00bed5b9f31d8b.html

    Xu Zhi-Qiang. Compressed sensing:a survey. Science China:Mathematics, 2012, 42(9):865-877 https://www.wenkuxiazai.com/doc/3851fb1eff00bed5b9f31d8b.html
    [5] 方红, 杨海蓉.贪婪算法与压缩感知理论.自动化学报, 2011, 37(12):1413-1421 http://www.aas.net.cn/CN/abstract/abstract17639.shtml

    Fang Hong, Yang Hai-Rong. Greedy algorithms and compressed sensing. Acta Automatica Sinica, 2011, 37(12):1413-1421 http://www.aas.net.cn/CN/abstract/abstract17639.shtml
    [6] Cohen A, Dahmen W, DeVore R. Orthogonal matching pursuit under the restricted isometry property. Constructive Approximation, 2017, 45(1):113-127 doi: 10.1007/s00365-016-9338-2
    [7] Do T T, Gan L, Nguyen N, Tran T D. Sparsity adaptive matching pursuit algorithm for practical compressed sensing. In: Proceedings of the 42th Asilomar Conference on Signals, Systems and Computers. Pacific Grove, CA, USA: IEEE, 2008. 581-587
    [8] Needell D, Vershynin R. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2):310-316 doi: 10.1109/JSTSP.2010.2042412
    [9] Lee D. MIMO OFDM channel estimation via block stagewise orthogonal matching pursuit. IEEE Communications Letters, 2016, 20(10):2115-2118 doi: 10.1109/LCOMM.2016.2594059
    [10] Davenport M A, Needell D, Wakin M B. Signal space CoSaMP for sparse recovery with redundant dictionaries. IEEE Transactions on Information Theory, 2013, 59(10):6820-6829 doi: 10.1109/TIT.2013.2273491
    [11] Giryes R, Elad M. RIP-based near-oracle performance guarantees for SP, CoSaMP, and IHT. IEEE Transactions on Signal Processing, 2012, 60(3):1465-1468 doi: 10.1109/TSP.2011.2174985
    [12] Ramirez-Giraldo J C, Trzasko J, Leng S, Yu L, Manduca A, McCollough C H. Nonconvex prior image constrained compressed sensing (NCPICCS):theory and simulations on perfusion CT. Medical Physics, 2011, 38(4):2157-2167 doi: 10.1118/1.3560878
    [13] Babaie-Kafaki S, Ghanbari R. A hybridization of the Hestenes-Stiefel and Dai-Yuan conjugate gradient methods based on a least-squares approach. Optimization Methods and Software, 2015, 30(4):673-681 doi: 10.1080/10556788.2014.966825
    [14] Shaw C B, Prakash J, Pramanik M, Yalavarthy P K. Least squares QR-based decomposition provides an efficient way of computing optimal regularization parameter in photoacoustic tomography. Journal of Biomedical Optics, 2013, 18(8):Article No.80501 doi: 10.1117/1.JBO.18.8.080501
    [15] Paige C C, S M A. LSQR:an algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software, 1982, 8(1):43-71 doi: 10.1145/355984.355989
    [16] Cichocki A, Zdunek R, Amari S I. Csiszár's divergences for non-negative matrix factorization: family of new algorithms. In: Proceedings of the 2006 International Conference on Independent Component Analysis and Blind Signal Separation. Charleston, SC, USA: Springer, 2006. 32-39
    [17] Cichocki A, Amari S I. Families of Alpha-Beta-and Gamma-divergences:flexible and robust measures of similarities. Entropy, 2010, 12(6):1532-1568 doi: 10.3390/e12061532
    [18] 余南南, 邱天爽.压缩传感条件下红外和可见光图像融合技术的研究.信号处理, 2012, 28(5):692-698 http://cdmd.cnki.com.cn/Article/CDMD-10183-2008126444.htm

    Yu Nan-Nan, Qiu Tian-Shuang. Fusion technology of infrared and visible images in compressive sensing. Signal Processing, 2012, 28(5):692-698 http://cdmd.cnki.com.cn/Article/CDMD-10183-2008126444.htm
    [19] 王琴, 沈远彤.基于压缩感知的多尺度最小二乘支持向量机.自动化学报, 2016, 42(4):631-640 http://www.aas.net.cn/CN/abstract/abstract18849.shtml

    Wang Qin, Shen Yuan-Tong. Multi-scale least squares support vector machine using compressive sensing. Acta Automatica Sinica, 2016, 42(4):631-640 http://www.aas.net.cn/CN/abstract/abstract18849.shtml
  • 期刊类型引用(21)

    1. 李伟,邓志翔. 列车运行控制系统运营中的安全分析方法. 武汉冶金管理干部学院学报. 2023(02): 17-20 . 百度学术
    2. 张友鹏,魏智健,杨妮,张迪. 基于KPCA-SVM的S700K转辙机故障诊断方法. 安全与环境学报. 2023(09): 3089-3097 . 百度学术
    3. 欧阳鑫锋,孔令刚. 基于改进动态时间规整的道岔故障诊断方法. 现代信息科技. 2023(20): 136-139+143 . 百度学术
    4. Yong Chen,Christian Buerger,Miao Lin,Xudong Li,Volker Labenski,Haixia Jin,Hai Wang,Yang Liu,Tsuyoshi Ino,Harald Feifel,Tian Tan,Fangrong Chang. Left-turn-across-path-from-opposite-direction accidents in China:CIDAS accident study. Transportation Safety and Environment. 2023(04): 358-370 . 必应学术
    5. Yunting Zheng,Shaohua Chen,Zhiyong Tan,Yongkui Sun. Research on fault diagnosis of a railway point machine based on a multi-entropy feature extraction method and support vector machine. Transportation Safety and Environment. 2023(04): 338-346 . 必应学术
    6. 陈蕊. 基于电流曲线的道岔卡阻识别算法及实现. 自动化与仪表. 2022(04): 21-27 . 百度学术
    7. 池毅,陈光武. 基于一维卷积神经网络的实时道岔故障诊断. 计算机工程与应用. 2022(20): 293-299 . 百度学术
    8. 吴小雪,丁大伟,任莹莹,刘贺平. 二维FM系统的同时故障检测与控制. 自动化学报. 2021(01): 224-234 . 本站查看
    9. 李婉婉,李国宁. 基于GMM聚类和PNN的道岔故障诊断研究. 控制工程. 2021(03): 429-434 . 百度学术
    10. 郑云水,白邓宇,王妍. 基于相似度的道岔健康状态评估及故障检测方法研究. 铁道科学与工程学报. 2021(04): 877-884 . 百度学术
    11. 刘美容,刘津涛,何怡刚. 基于EMD复合多尺度熵的模拟电路故障诊断方法. 电子测量技术. 2021(04): 51-56 . 百度学术
    12. 李林,于颖. 智能继电保护回路故障监测全数字仿真研究. 计算机仿真. 2021(12): 460-464 . 百度学术
    13. 阮莹,梁利娟. 数字集成电路老化故障高精度预测方法仿真. 计算机仿真. 2020(02): 434-437 . 百度学术
    14. 高亚丽,陈光武. 基于改进FNN的道岔电路故障诊断方法. 科技创新与应用. 2020(15): 125-127 . 百度学术
    15. 孔令刚,焦相萌,陈光武,范多旺. 基于Mallat小波分解与改进GWO-SVM的道岔故障诊断. 铁道科学与工程学报. 2020(05): 1070-1079 . 百度学术
    16. 孔令刚,焦相萌,陈光武,范多旺. 基于多域特征提取与改进PSO-PNN的道岔故障诊断. 铁道科学与工程学报. 2020(06): 1327-1336 . 百度学术
    17. 杨菊花,于苡健,陈光武,司涌波,邢东峰. 基于CNN-GRU模型的道岔故障诊断算法研究. 铁道学报. 2020(07): 102-109 . 百度学术
    18. 姬文江,左元,黑新宏,高橋聖,中村英夫. 基于FastDTW的道岔故障智能诊断方法. 模式识别与人工智能. 2020(11): 1013-1022 . 百度学术
    19. Huidong Wang,Shifan He,Chengdong Li,Xiaohong Pan. Pythagorean Uncertain Linguistic Variable Hamy Mean Operator and Its Application to Multi-attribute Group Decision Making. IEEE/CAA Journal of Automatica Sinica. 2019(02): 527-539 . 必应学术
    20. 张友鹏,江雪莹,赵斌. 融合粗糙集与灰色模型的道岔故障预测. 铁道科学与工程学报. 2019(09): 2331-2338 . 百度学术
    21. 吴永成,阳长琼,何涛. 基于Fretchet距离与TWSVM的多机牵引道岔故障诊断研究. 铁道科学与工程学报. 2019(11): 2866-2872 . 百度学术

    其他类型引用(27)

  • 加载中
  • 图(4)
    计量
    • 文章访问数:  2705
    • HTML全文浏览量:  454
    • PDF下载量:  706
    • 被引次数: 48
    出版历程
    • 收稿日期:  2016-08-16
    • 录用日期:  2017-05-06
    • 刊出日期:  2018-07-20

    目录

    /

    返回文章
    返回