-
摘要: 信息准则在发展主子空间跟踪算法中具有十分重要的意义.目前, 主子空间信息准则还不多见, 为此本文提出了一种新型的主子空间跟踪信息准则.当且仅当神经网络权矩阵收敛到信号主子空间的一个正交基时, 该信息准则取得唯一全局极大值.通过梯度上升法对该信息准则求极值导出了一个主子空间跟踪算法.最后通过仿真实验和实际应用证明了所提算法的正确性和实用性.Abstract: It is clear that a properly chosen information criterion is a very important part in developing principal subspace tracking algorithms. Up to now, the numbers of principal subspace tracking information criterion are not rich. Based on this fact, a novel information criterion is proposed in this paper. This information criterion exhibits a single global maximum attained if and only if the weight matrix spans the desired principal subspace. A subspace tracking algorithm is derived by using gradient ascent method to this information criterion. Numerical simulation and real application experiments are carried out to show the correctness and practicality of the proposed algorithm.
-
Key words:
- Principal subspace tracking /
- information criterion /
- gradient ascent method /
- neural networks
-
在信息处理领域, 通常将信号自相关矩阵最大特征值对应的特征向量称之为信号的主成分, 而由信号的多个主成分张成的空间称为信号的主子空间.在很多信号处理问题中, 需要对信号的主子空间进行在线跟踪, 如视觉跟踪[1]、波达方向估计[2]、图像处理[3]、谱分析[4]等领域.因此, 发展主子空间跟踪算法就成为了一件非常有意义的工作.
以往解决主子空间跟踪问题主要依靠矩阵特征值分解(Eigenvalue decomposition, EVD)和奇异值分解(Singular value decomposition, SVD)等, 然而该方法计算复杂度高, 而且难以满足实时信号处理的要求.为了克服这些缺点, 学者们提出了基于Hebbian神经网络的主子空间跟踪方法.相比传统的EVD和SVD方法, 神经网络方法具有以下3个方面的优点: 1)可以对输入信号的自相关矩阵进行在线估计; 2)算法的计算复杂度较低; 3)能够处理非平稳的随机信号[4].基于上述优势, 神经网络方法已经成为近些年来国际上的一个研究热点.
基于单层线性神经网络, Oja提出了著名的Oja算法[5], 然而Oja算法是一个单维主成分提取算法.为了能够实现对信号主子空间的跟踪, 学者们通过对Oja算法进行了改进提出了很多算法, 如FDPM (Fast data projection method)算法[6]、SOOJA (Stable and orthonormal OJA algorithm)算法[7]、SDPM (Stable DPM algorithm)算法[8]等, 然而上述算法大多是基于启发式推理提出来的, 而并没有建立相对应的信息准则.由于信息准则在算法发展中具有很重要的意义[9], 因此研究主子空间准则是一件非常有意义的工作.在文献[10]中, 基于最小均方误差(Least mean squared error, LMSE)准则, Yang提出了投影近似子空间跟踪算法(Projection approximation subspace tracking, PAST); 此后, Miao等提出了NIC (Novel information criterion)准则[11], 并分别导出了梯度和递归型主子空间跟踪算法; 基于Rayleigh商函数, Kong等提出了UIC (Unified information criterion)准则[12], 仿真实验表明基于UIC准则导出的算法具有很快的收敛速度.目前, 发展主子空间跟踪准则仍然具有很强的研究价值.
本文将提出一种新型的主子空间跟踪信息准则, 并通过梯度法导出快速的主子空间跟踪算法.论文的结构安排如下:第1节是提出一种新的主子空间信息准则; 第2节是对所提信息准则进行前景分析; 第3节主要是采用梯度上升法导出主子空间算法; 第4节通过两组仿真实验对所提算法的性能进行验证; 本文的结论在第5节.
1. 新型主子空间跟踪信息准则
考虑一个具有如下形式的多输入多输出线性神经网络模型:
$$ \begin{equation} {\pmb{y}} = {{W}^{\rm T}}{\pmb{x}} \end{equation} $$ (1) 其中, $ {W} = [{\pmb {w}_1}, {\pmb {w}_2}, \cdots , {\pmb {w}_r}] \in {{\bf {R}}^{n \times r}} $是神经网络的权矩阵, $ {\pmb {w}_i} $是权矩阵$ {W} $的第$ i $列; $ {\pmb{x}} \in {{\bf {R}}^{n \times 1}} $是采样信号, 这里作为神经网络的输入; $ {\pmb{y}} \in {{\bf {R}}^{r \times 1}} $为采样信号的低维表示, $ r $是子空间的维数.本文的目的就是构造合适的神经网络权矩阵迭代更新方程, 使神经网络的权矩阵最终能够收敛到采样信号的主子空间.
基于上述神经网络模型, 给定域$ \Omega = \{ {W}|0 < {{W}^{\rm T}}{RW} < \infty , {{W}^{\rm T}}{W} \ne 0\} $, 提出如下信息准则:
$$ \begin{align} {{W}^*} = \, & {\rm{arg}}{\kern 1pt} \mathop {\max }\limits_{{W} \in \Omega } J({W})\\& J({W}) = \frac{1}{2}{\rm tr}\left[ {({{W}^{\rm T}}{RW}){{({{W}^{\rm T}}{W})}^{ - 1}}} \right]+\\& \frac{1}{2}{\rm tr}\left[ {\ln ({{W}^{\rm T}}{W}) - {{W}^{\rm T}}{W}} \right] \end{align} $$ (2) 其中, $ {{R}} = {\rm E}[{{\pmb {xx}}}_{}^{\rm T}] $为采样信号的自相关矩阵.根据矩阵理论可得:矩阵$ {{R}} $是一个对称的正定矩阵, 且特征值均是非负的.对矩阵$ {{R}} $特征值分解得:
$$ \begin{equation} {{R}} = {{U\Lambda }}{{{U}}^{\rm T}} \end{equation} $$ (3) 其中, $ {{U}} = [{{\pmb {u}}_1}, {{\pmb {u}}_2}, \cdots , {{\pmb {u}}_n}] $是由矩阵$ {{R}} $的特征向量构成的矩阵, $ {{\Lambda }} = {\rm {\rm {\rm diag}}}\{{\lambda _1}, {\lambda _2}, \cdots , {\lambda _n}\} $是由矩阵$ {{R}} $的特征值组成.为了后续使用方便, 这里将特征值按降序进行排列, 即特征值满足如下方程:
$$ \begin{equation} {\lambda _1} > {\lambda _2} > \cdots > {\lambda _r} > \cdots > {\lambda _n} > 0 \end{equation} $$ (4) 根据主子空间的定义可知特征值$ {\lambda _1}, {\lambda _2}, \cdots , {\lambda _r} $所对应的特征向量张成的子空间称为输入信号的主子空间.从式(2)可得$ J({W}) $是无下界的, 且当$ {W} $趋于无穷大时, $ J({W}) $将趋于负无穷大, 因此研究$ J({W}) $的极小值是没有任何意义的.实际上, 我们关心的是$ J({W}) $的极大点.具体说来, 我们关心以下几个问题:
1) $ J({W}) $有没有全局极大点？
2) $ J({W}) $的全局极大点与信号的主子空间之间的关系是什么？
3) $ J({W}) $有没有其他局部极值？
上述三个问题的回答将由下在一节中完成.
2. 信息准则的全局最优值分析
信息准则(2)的全局最优值分析通过定理1和定理2来完成.
定理1. 在域$ \Omega = \{ {W}|0 < {{W}^{\rm T}}{RW} < \infty , {{W}^{\rm T}}{W} \ne 0\} $内, 当且仅当$ {W} = {{{U'}}_r}{{Q}} $时, 权矩阵$ {W} $是信息准则$ J({W}) $的一个平稳点, 其中$ {{{U'}}_r} = [{{\pmb {u}}_{j1}}, {{\pmb {u}}_{j2}}, \cdots , {{\pmb {u}}_{jr}}] $是由自相关矩阵$ {{R}} $的任意$ r $个特征向量构成的矩阵, $ {{Q}} $是任意一个$ r \times r $维正交矩阵.
将$ {{R}} $的特征向量作为空间$ {{\bf{R}}^{n \times n}} $的一组正交基, 则权矩阵$ {W} $可以表示为: $ {W} = {{{U}}^{\rm T}}{{\tilde W}} $, 其中$ {{\tilde W}} \in {{\bf {R}}^{n \times r}} $称为系数矩阵.将这一结果代入式(2)可得:
$$ \begin{align} {{{{\tilde W}}}^*} = \, & {\rm{arg}}{\kern 1pt} \mathop {\max }\limits_{{W} \in \Omega } E({{\tilde W}})\\ E({{\tilde W}}) = \, & \frac{1}{2}{\rm tr}[({{{{\tilde W}}}^{\rm T}}{{\Lambda \tilde W}}){({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 1}}]+\\& \frac{1}{2}{\rm tr}[\ln ({{{{\tilde W}}}^{\rm T}}{{\tilde W}}) - {{{{\tilde W}}}^{\rm T}}{{\tilde W}}] \end{align} $$ (5) 显然式(2)和式(5)是等价的, 即定理1的证明是可以通过对下述推论的证明来完成.
推论1. 在域$ \tilde \Omega = \left\{ {{{\tilde W}}|0 < {{{{\tilde W}}}^{\rm T}}{{\Lambda \tilde W}} < \infty} \right. $, $ \left. { {{{{\tilde W}}}^{\rm T}}{{\tilde W}} \ne 0} \right\} $中, 当且仅当$ {{\tilde W}} = {{{P}}_r}{{Q}} $时, $ {{\tilde W}} $是$ E({{\tilde W}}) $的一个平稳点, 其中$ {{{P}}_r} \in {{ {R}}^{n \times r}} $是任意一个$ n \times r $维置换矩阵.
证明参见附录A.
定理2. 在域$ \Omega $内, 当且仅当$ {W} = {{{\tilde U}}_r}{{Q}} $时, 其中$ {{{\tilde U}}_r} = [{{\pmb {u}}_1}, {{\pmb {u}}_2}, \cdots , {{\pmb {u}}_r}] $是由自相关矩阵$ {{R}} $的前$ r $个特征向量构成的矩阵且$ {{Q}} $是任意一个$ r \times r $维正交矩阵, 信息准则$ J({W}) $达到全局极大. $ J({W}) $没有其他局部极值, 在全局最大点处有:
$$ \begin{equation} J({W}) = \frac{1}{2}\sum\limits_{i = 1}^r {{\lambda _i}} - \frac{r}{2} \end{equation} $$ (6) 同定理1的证明过程一样, 这里将通过对推论2的证明来完成定理2的证明.
推论2. 在域$ \tilde \Omega $中, 当且仅当$ {{\tilde W}} = {{\bar PQ}} $, 信息准则$ E({{\tilde W}}) $达到全局最大点, 其中$ {{\bar P}} = {( {{{\tilde P}}}\; \; {{0}})^{\rm T}} \in {{ {\bf R}}^{n \times r}} $一个$ n \times r $维矩阵, $ {{\tilde P}} $是一个置换矩阵, 而$ E({{\tilde W}}) $所有其他的平稳点都是鞍点.
证明参见附录B.
通过定理1和定理2可知, 当神经网络权矩阵$ {W} $刚好收敛到自相关矩阵$ {{R}} $的主子空间的一组正交基时, $ J({W}) $取得全局极大值, 从而建立起神经网络与信号主子空间之间的关系.由于信息准则$ J({W}) $只有一个全局最大点, 而没有局部极值, 因此采用非线性规划算法(如梯度法、共轭梯度法、牛顿法等)来求解该优化问题.梯度算法是采用$ J({W}) $的梯度作为迭代步长; 共轭梯度法需要不断修正算法的共轭方向, 所导出的算法通常具有较高的计算复杂度; 牛顿法则用到的Hessian矩阵, 而当$ {W} $是一个矩阵时该Hessian矩阵是非常难以获得的.相比共轭梯度法和牛顿算法, 梯度法具有算法结构更为简单, 计算复杂度低, 因此下一节将采用梯度算法导出新型的主子空间跟踪算法.
3. 主子空间跟踪算法
假定$ {\pmb{x}}(k), k = 0, 1, 2, \cdots $是一个平稳的随机过程, 这里将其作为神经网络模型的输入.根据随机学习理论, 权矩阵$ {W} $的变化规律与输入向量$ {\pmb{x}}(k) $并不相关.取式(2)作为最优化函数, 则可以得出所提信息准则的梯度流为:
$$ \begin{align} \frac{{{\rm d}{W}(t)}}{{\rm d}{t}} = \, & \left[ {\frac{{{W}(t)}}{{{{W}^{\rm T}}(t){W}(t)}} - {W}(t)} \right]+\\& \left[ {{RW}(t) - \frac{{{W}(t){{W}^{\rm T}}(t){RW}(t)}} {{{{W}^{\rm T}}(t){W}(t)}}} \right]\times\\& {\left\{ {{{W}^{\rm T}}(t){W}(t)} \right\}^{ - 1}} \end{align} $$ (7) 应用随机近似理论可得:
$$ \begin{align} &\frac{{{\rm d}{W}(t)}}{{\rm d}{t}} = \\&\quad \left[ {{W}(t){{\left\{ {{{W}^{\rm T}}(t){W}(t)} \right\}}^{ - 1}} - {W}(t)} \right]- \\&\quad \left[ {{W}(t){{W}^{\rm T}}(t){\pmb{x}}(t){{\pmb{x}}^{\rm T}}(t){W}(t){{\left\{ {{{W}^{\rm T}}(t){W}(t)} \right\}}^{ - 1}}} \right.- \\&\quad \left. {{\pmb{x}}(t){{\pmb{x}}^{\rm T}}(t){W}(t)} \right]{\left\{ {{{W}^{\rm T}}(t){W}(t)} \right\}^{ - 1}} \end{align} $$ (8) 对式(8)进行离散化操作后获得如下方程:
$$ \begin{align} &{W}\left( {k + 1} \right) = \\&\quad {{W}}(k) - \eta \left[ {{{W}}(k){{\left( {{{{W}}^{\rm T}}(k){{W}}(k)} \right)}^{ - 1}}{\pmb{y}}(k){{\pmb{y}}^{\rm T}}(k)} \right.- \\&\quad \left. {{\pmb{x}}(k){{\pmb{y}}^{\rm T}}(k)} \right] {\left( {{{{W}}^{\rm T}}(k){{W}}(k)} \right)^{ - 1}} - \eta {{W}}(k)+ \\&\quad \eta {{W}}(k){\left( {{{{W}}^{\rm T}}(k){{W}}(k)} \right)^{ - 1}} \end{align} $$ (9) 其中, $ \eta $是神经网络的学习因子, 且满足$ 0 < \eta < 1 $.式(9)所描述的算法在每一步迭代过程中计算复杂度为: $ n{{r}^{2}}+4{{r}^{3}}\text{ /}3 $, 这点与UIC算法[12]是相同的, 要少于NIC算法[11]中的$ 2{n^2}r + {\rm O}(n{r^2}) $的计算量和共轭梯度算法[13] $ 12{n^2}r + {\rm O}(n{r^2}) $的计算量.
4. 仿真实验
本节通过两个仿真实例来对所提算法的性能进行验证.第一个实验考察所提算法提取多维主子空间的能力并将仿真结果与其他同类型算法进行对比; 第二个是应用所提算法解决图像重构问题.
4.1 主子空间跟踪实验
在本实验中, 所提算法将与UIC算法和SDPM算法进行对比.为了衡量算法的收敛性能, 这里采用如下两个评价函数, 第一个是第$ k $次迭代时的权矩阵模值
$$ \begin{equation} p({{{W}}_k}) = {\left\| {{{W}}_k^{\rm T}{{{W}}_k}} \right\|_F} \end{equation} $$ (10) 第二个是指标参数
$$ \begin{equation} {\rm{dist}}({{{W}}_k}) = {\left\| {{{W}}_k^{\rm T}{{{W}}_k}{\rm diag}{\left\{{{{W}}_k^{\rm T}{{{W}}_k}} \right\}^{ - 1}} - {{{I}}_r}} \right\|_F} \end{equation} $$ (11) 指标参数代表着权矩阵正交化的偏离程度.显然, 如果$ {\rm{dist}}({{{W}}_k}) $收敛到0, 则意味着权矩阵收敛到了主子空间的一个正交基.
本实验中信号产生方法与文献[12]相同, 即输入信号$ {{{X}}_k} = {{B}}{{\pmb {z}}_k} $, 其中$ B=\text{randn}(31,31)/31$是一个随机产生的矩阵, $ {{\pmb {z}}_k} \in {{ {\bf R}}^{31 \times 1}} $是高斯的、瞬时白的、随机产生的向量.在本实验中, 分别采用UIC算法、SDPM算法和所提算法对信号的12维主子空间进行提取跟踪.三种算法采用相同的学习因子$ \eta = 0.1 $, 初始权矩阵是随机产生的(即矩阵的每一个元素均服从均值为零方差为1的高斯分布).通常情况下, 取不同的初始化权矩阵时, 算法具有不同的收敛速度.为了更全面地衡量算法性能, 通常取多次实验的平均值来描述算法收敛过程.在图 1和图 2分别给出了三种算法在迭代过程中的权矩阵模值曲线和指标参数曲线, 该结果曲线是100次独立实验结果平均得到的.图中实线代表着所提算法, 虚线代表UIC算法, 点划线代表SDPM算法.
图 1和图 2中可以发现, 所提算法的权矩阵模值曲线收敛到了一个常数而且指标参数收敛到了零.这就表明所提算法具备跟踪信号主子空间的能力.从图 1中我们还可以发现, 所提算法的权矩阵模值在200步时就已经收敛, 而UIC算法则需要300步, SDPM算法需要800步, 即所提算法的权矩阵模值曲线具有最快的收敛速度.同理, 从图 2中可以发现所提算法指标参数的收敛速度要优于其他两个算法.综合两图可以得出结论:三种算法中, 所提算法具有最快的收敛速度.
4.2 图像压缩重构离实验
数据压缩是主子空间算法的一个很重要的应用.本实验将利用所提算法对著名的Lena图像进行压缩重构.如图 3所示, 原始Lena图像的像素为$ 512 \times 512 $.在本实验中, 将Lena图像分解成若干个$ 8 \times 8 $不重叠的小块.将每一个小块中的数据按照从左至右从上到下的顺序排列起来, 构成一个64维向量.在去掉均值和标准化后, 将这些图像数据构成一个输入序列.然后采用SDPM算法、UIC算法以及所提算法对该图像进行压缩重构, 这里重构维数为5.与实验1相同, 本实验同样采用权矩阵模值和指标参数两个评价函数.
本实验中三种算法的初始化参数设置方法与实验1相类似, 具体参数如下:学习因子$ \eta = 0.2 $, 初始化权矩阵是随机产生的.图 4是经过所提算法压缩后重构出来的Lena图像, 图 5是三种算法的权矩阵模值曲线, 图 6是三种算法的指标参数曲线, 该结果曲线都是100次独立实验的平均值.对比图 3和图 4可以发现, 重构的Lena图像是很清晰的, 即所提算法能够有效解决图像压缩重构问题.通过图 5和图 6可以发现:不论是权矩阵模值曲线还是指标参数曲线, 所提算法的收敛速度均要快于UIC算法和SDPM算法.这进一步证实了所提算法在收敛速度方面的优势.
5. 结论
主子空间跟踪算法在现代信息科学各个领域均有着很重要的应用.基于Hebbian神经网络的主子空间跟踪是近些年来国际上的一个研究热点.然而目前大多数主子空间跟踪神经网络算法是基于启发式推理而提出来的, 能够提供信息准则的算法并不多见.针对这一问题, 本文提出了一种新型的信息准则, 并对所提信息准则的前景进行了严格的证明.通过梯度上升法导出了一个主子空间跟踪算法.仿真实验表明:相比一些现有主子空间跟踪算法, 所提算法具有更快的收敛速度.
进一步的研究方向是寻找新型的主子空间信息准则, 创新信息准则的平稳点分析方法, 将主子空间算法应用于更广泛的领域.
附录A.推论1证明
证明 在域$ \tilde \Omega $内, $ E({{\tilde W}}) $对于矩阵$ {{\tilde W}} $的一阶微分存在, 且有
$$ \begin{align} \nabla E({{\tilde W}}) = \, & {{\Lambda \tilde W}}{({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 1}} - {{\tilde W}} - \\& {{\tilde W}}{({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 2}}{{{{\tilde W}}}^{\rm T}}{{\Lambda \tilde W}} + {{\tilde W}}{({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 1}} \end{align} $$ (A1) 定义一个矩阵集$ \left\{ {{{\tilde W}}|{{\tilde W}} = {{{P}}_r}{{Q}}} \right\} $, 则在该集合内的任意一点均有:
$$ \begin{align} & \nabla E({{\tilde W}}){|_{{{\tilde W}} = {{{P}}_r}{{Q}}}} = \\&\qquad {{\Lambda }}{{{P}}_r}{{Q}}{({{{Q}}^{\rm T}}{{P}}_r^{\rm T}{{{P}}_r} {{Q}})^{ - 1}} + {{{P}}_r}{{Q}}{({{{Q}}^{\rm T}} {{P}}_r^{\rm T}{{{P}}_r}{{Q}})^{ - 1}}- \\&\qquad {{{P}}_r}{{Q}}{({{{Q}}^{\rm T}}{{P}}_r^{\rm T}{{{P}}_r}{{Q}})^{ - 2}}{{{Q}}^{\rm T}}{{P}}_r^{\rm T}{{\Lambda }}{{{P}}_r}{{Q}} - {{{P}}_r}{{Q}} = \\&\qquad {{\Lambda }}{{{P}}_r}{{Q}} + {{{P}}_r}{{Q}}{{{Q}}^{\rm T}}{{P}}_r^{\rm T}{{\Lambda }}{{{P}}_r}{{Q}} = 0 \end{align} $$ (A2) 反之, 根据定义可得, 在$ E({{\tilde W}}) $平稳点处有$ \nabla E({{\tilde W}}) = {{0}} $成立, 即
$$ \begin{align} &{{\Lambda \tilde W}}{({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 1}} + {{\tilde W}}{({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 1}}- \\&\qquad {{\tilde W}}{({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 2}}{{{{\tilde W}}}^{\rm T}}{{\Lambda \tilde W}} - {{\tilde W}} = {{0}} \end{align} $$ (A3) 将上式左右两边各乘以$ {{{\tilde W}}^{\rm T}} $可得:
$$ \begin{align} & {{{{\tilde W}}}^{\rm T}}{{\Lambda \tilde W}}{({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 1}} + {{{{\tilde W}}}^{\rm T}}{{\tilde W}}{({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 1}}- \\&\qquad {{{{\tilde W}}}^{\rm T}}{{\tilde W}}{({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 2}}{{{{\tilde W}}}^{\rm T}}{{\Lambda \tilde W}} - {{{{\tilde W}}}^{\rm T}}{{\tilde W}} = \\&\qquad {{{{\tilde W}}}^{\rm T}}{{\Lambda \tilde W}} {({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 1}} - {{{{\tilde W}}}^{\rm T}}{{W}}- \\&\qquad {({{{{\tilde W}}}^{\rm T}}{{\tilde W}})^{ - 1}}{{{{\tilde W}}}^{\rm T}}{{\Lambda \tilde W}} + {{I}} = \\&\qquad {{I}} - {{{{\tilde W}}}^{\rm T}}{{W}} = {{0}} \end{align} $$ (A4) 根据上式可得, 在$ E({{\tilde W}}) $平稳点处有
$$ \begin{equation} {{{\tilde W}}^{\rm T}}{{W}} = {{I}} \end{equation} $$ (A5) 上式表明在$ E({{\tilde W}}) $平稳点处矩阵$ {{\tilde W}} $的各个列向量之间是相互正交的.将式(A5)代入式(A3)可得:
$$ \begin{equation} {{\Lambda \tilde W}} = {{\tilde W}}{{{\tilde W}}^{\rm T}}{{\Lambda \tilde W}} \end{equation} $$ (A6) 令矩阵$ {\tilde W}$的行向量为${{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{u}}}_{i}}\ (i=1,2,\cdots ,n) $, 即有$ \tilde W{\rm{ = }}{\left[ {\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\smile$}} \over u} _1^{\rm{T}},\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\smile$}} \over u} _2^{\rm{T}}, \cdots ,\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\smile$}} \over u} _n^{\rm{T}}} \right]^{\rm{T}}} $, 同时定义矩阵$ {{B}} = {{{\tilde W}}^{\rm T}}{{\Lambda \tilde W}} $, 则根据式(11)可得:
$$ \begin{equation} {\sigma _i}{\mathord{\buildrel{\lower3pt\hbox{$ \smile$}} \over u} _i} = {\mathord{\buildrel{\lower3pt\hbox{$ \smile$}} \over u} _i}{{B}}, \quad i = 1, 2, \cdots , n \end{equation} $$ (A7) 显然, 上式可以看作是矩阵$ {{B}} $的特征值分解.由于$ {{B}} $是一个$ r \times r $维对称正定矩阵, 只有$ r $个相互正交的左行特征向量, 即矩阵$ {{\tilde W}} $只有$ r $个相互正交的行向量.更进一步, 矩阵$ {{\tilde W}} $的这$ r $个非零行向量正好构成了一个正交矩阵, 也就是说此时矩阵$ {{\tilde W}} $可以通过$ {{\tilde W}} = {{{P}}_r}{{Q}} $来表示.
附录B.推论2证明
证明 定义一个置换矩阵$ {{{P}}_r} \ne {{\bar P}} $, 则矩阵$ {{{P}}_r} $中的第$ r + 1 $到$ n $个行向量之中必有一个非零的行向量.由于$ {{{P}}_r} $和$ {{\bar P}} $同为两个置换矩阵, 则必定存在两个对角矩阵$ {{\bar \Lambda }} $和$ {{\hat \Lambda }} $使得下式成立:
$$ \begin{equation} {{{\bar P}}^{\rm T}}{{\Lambda \bar P}} = {{\bar \Lambda }}, {{P}}_r^{\rm T}{{\Lambda }}{{{P}}_r} = {{\hat \Lambda }} \end{equation} $$ (B1) 根据上式可得:
$$ \begin{equation} \begin{cases} {\rm tr}\left( {{{{{\bar P}}}^{\rm T}}{{\Lambda \bar P}}} \right) = \sum\limits_{i = 1}^r {{\lambda _i}} \\ {\rm tr}\left( {{{P}}_r^{\rm T}{{\Lambda }}{{{P}}_r}} \right) = \sum\limits_{i = 1}^r {{\lambda _{{{\hat j}_i}}}} \end{cases} \end{equation} $$ (B2) 将特征值$ {\lambda _{\hat ji}} $ $ (i = 1, 2, \cdots , r) $按照降序顺序排列, 即有$ {\hat \lambda _{\hat j1}} > {\hat \lambda _{\hat j2}} > \cdots > {\hat \lambda _{\hat jr}} $, 则对于$ {{{P}}_r} \ne {{\bar P}} $, 则必定存在有$ {\lambda _i} > {\hat \lambda _{\hat ji}}\; (i = 1, 2, \cdots , r) $成立, 即有:
$$ \begin{equation} {\rm tr}\left( {{{{{\bar P}}}^{\rm T}}{{\Lambda \bar P}}} \right) > {\rm tr}\left( {{{P}}_r^{\rm T}{{\Lambda }}{{{P}}_r}} \right) \end{equation} $$ (B3) 由于
$$ \begin{align} E({{{P}}_r}{{Q}}) = \, & \frac{1}{2}{\rm tr}[({{{Q}}^{\rm T}}{{P}}_r^{\rm T}{{\Lambda }}{{{P}}_r}{{Q}}){({{{Q}}^{\rm T}}{{P}}_r^{\rm T}{{{P}}_r}{{Q}})^{ - 1}}]+\\& \frac{1}{2}{\rm tr}[\ln ({{{Q}}^{\rm T}}{{P}}_r^{\rm T}{{{P}}_r}{{Q}}) - {{{Q}}^{\rm T}}{{P}}_r^{\rm T}{{{P}}_r}{{Q}}] = \\& \frac{1}{2}{\rm tr}[({{{Q}}^{\rm T}}{{P}}_r^{\rm T}{{\Lambda }}{{{P}}_r}{{Q}})] - \frac{r}{2} = \\& \frac{1}{2}{\rm tr}[({{P}}_r^{\rm T}{{\Lambda }}{{{P}}_r})] - \frac{r}{2} \end{align} $$ (B4) $$ \begin{align} E({{{{\bar P}}}^{\rm T}}{{Q}}) = \, & \frac{1}{2}{\rm tr}[({{{Q}}^{\rm T}}{{{{\bar P}}}^{\rm T}}{{\Lambda \bar PQ}}){({{{Q}}^{\rm T}}{{{{\bar P}}}^{\rm T}}{{\bar PQ}})^{ - 1}}]+ \\& \frac{1}{2}{\rm tr}[\ln ({{{Q}}^{\rm T}}{{{{\bar P}}}^{\rm T}}{{\bar PQ}}) - {{{Q}}^{\rm T}}{{{{\bar P}}}^{\rm T}}{{\bar PQ}}] = \\& \frac{1}{2}{\rm tr}[({{{Q}}^{\rm T}}{{{{\bar P}}}^{\rm T}}{{\Lambda \bar PQ}})] - \frac{r}{2} = \\& \frac{1}{2}{\rm tr}[({{{{\bar P}}}^{\rm T}}{{\Lambda \bar P}})] - \frac{r}{2} \end{align} $$ (B5) 根据式(B3)有:
$$ \begin{equation} E({{{P}}_r}{{Q}}) < E({{{\bar P}}^{\rm T}}{{Q}}) \end{equation} $$ (B6) 即集合$ \left\{ {{P_r}Q|{Q^{\rm{T}}}\Lambda Q > 0\& {{\rm{P}}_{\rm{r}}} \ne {\rm{\bar P}}} \right\} $的点并不是全局极大点.
由于$ {{{P}}_r} \ne {{\bar P}} $, 则矩阵$ {{\bar P}} $中必定存在一列向量$ {{{\bar p}}_i} $ $ (1 \le i \le r) $, 使得:
$$ \begin{equation} {{\bar p}}_i^{\rm T}{{{P}}_r} = {{0}} \end{equation} $$ (B7) 同理, 矩阵$ {{{P}}_r} $中也存在一列向量$ {{{p}}_{r, j}}\; (1 \le j \le r) $使得
$$ \begin{equation} {{{p}}_{r, j}}{{\bar P}} = {{0}} \end{equation} $$ (B8) 令$ {{{\bar p}}_i} $的非零元素为$ {\bar j_i} $行, $ {{{p}}_{r, j}} $的非零元素为$ {\hat j_j} $行, 则有$ {\bar j_i} > {\hat j_j} $和$ {\lambda _{{{\hat j}_j}}} > {\lambda _{{{\bar j}_i}}} $.定义矩阵:
$$ \begin{equation} {{B}} = \left[ {{{{p}}_{r, 1}}, \cdots , \frac{{{{{p}}_{r, i}} + \varepsilon {{{{\bar p}}}_i}}}{{\sqrt {1 + {\varepsilon ^2}} }}, \cdots , {{{p}}_{r, r}}} \right] \end{equation} $$ (B9) 其中, $ \varepsilon $是正任意小数.由$ {{{\bar p}}_i} $和$ {{{p}}_{r, j}} $有且仅有一个非零元素得
$$ \begin{align} {{\Lambda B}} = \, & {\rm diag}\left\{ {{\lambda _{\hat j1}}{{{p}}_{r, 1}}, \cdots , } {\frac{{{\lambda _{\hat jj}}{{{p}}_{r, i}} + \varepsilon {\lambda _{\bar ji}}{{{{\bar p}}}_i}}}{{\sqrt {1 + {\varepsilon ^2}} }}, \cdots , {\lambda _{\hat jr}}{{{p}}_{r, r}}} \right\} \end{align} $$ (B10) 更进一步有:
$$ \begin{equation} {{{B}}^{\rm T}}{{\Lambda B}} = {\rm diag}\left\{ {{\lambda _{\hat j1}}, \cdots , \frac{{{\lambda _{\hat jj}} + \varepsilon {\lambda _{\bar ji}}}}{{1 + {\varepsilon ^2}}}, \cdots , {\lambda _{\hat jr}}} \right\} \end{equation} $$ (B11) 通过式(A8)可得:
$$ \begin{align} & {{{B}}^{\rm T}}{{\Lambda B}} - {{P}}_r^{\rm T}{{\Lambda }}{{{P}}_r} = \\& \qquad {\rm diag}\left\{ {{\lambda _{\hat j1}}, \cdots , \frac{{{\lambda _{\hat jj}} + \varepsilon {\lambda _{\bar ji}}}}{{1 + {\varepsilon ^2}}}, \cdots , {\lambda _{\hat jr}}} \right\}- \\& \qquad {\rm diag}\left\{ {{\lambda _{\hat j1}}, \cdots , {\lambda _{\hat jj}}, \cdots , {\lambda _{\hat jr}}} \right\} = \\& \qquad {\rm diag}\left\{ {0, \cdots , \frac{{\left( { - {\lambda _{\hat jj}} + {\lambda _{\bar ji}}} \right){\varepsilon ^2}}}{{1 + {\varepsilon ^2}}}, \cdots , 0} \right\} \end{align} $$ (B12) 由于$ {\lambda _{\hat jj}} > {\lambda _{\bar ji}} $, 所以$ {{{B}}^{\rm T}}{{\Lambda B}} - {{P}}_r^{\rm T}{{\Lambda }}{{{P}}_r} $是一个负定矩阵, 因此有:
$$ \begin{equation} E({{BQ}}) = \frac{1}{2}{\rm tr}[{{{B}}^{\rm T}}{{\Lambda B}}] - \frac{r}{2} < E({{{P}}_r}{{Q}}) \end{equation} $$ (B13) 即集合$ \left\{ {{P_r}Q|{Q^{\rm{T}}}\hat \Lambda Q > \;0{\rm{\& }}{P_r} \ne \bar P} \right\} $中所有平稳点都是不稳定的鞍点.
接下来将证明: $ J({{W}}) $没有其他局部极值.令$ {{{\dot U}}_r} = {{{\tilde U'}}_r} + \varepsilon {{{M}}_1} $, 其中$ {{{M}}_1} = [{{0}}, \cdots , {{\pmb {u}}_k}, \cdots , {{0}}] $, $ 1 \le k \le r $.即$ {{{\dot U}}_r} $是$ {{{\tilde U'}}_r} $沿$ {{\pmb {u}}_k} $的方向增长而成.由于$ {{{\tilde U'}}_r} \ne {{{\tilde U}}_r} $, 则必定有$ {\lambda _k} > {\lambda _{jk}} $.
当$ {{W}} = {{{\dot U}}_r}{{Q}} $时, 有:
$$ \begin{align} & {\left. {J({{W}})} \right|_{{{W}} = {{{{\dot U}}}_r}{{Q}}}} - {\left. {J({{W}})} \right|_{{{W}} = {{{{\tilde U'}}}_r}{{Q}}}} = \\& \qquad \frac{1}{2}\left( {{\lambda _k} - {\lambda _{jk}}} \right){\varepsilon ^2} + o({\varepsilon ^2}) \end{align} $$ (B14) 令$ {{{\ddot U}}_r} = {{{\tilde U'}}_r} + \varepsilon {{{M}}_2} $, 其中$ {{{M}}_2} = [{{0}}, \cdots , {{\pmb {u}}_{jk}}, \cdots , {{0}}] $, $ 1 \le k \le r $.即$ {{{\dot U}}_r} $是$ {{{\tilde U'}}_r} $沿$ {{\pmb {u}}_{jk}} $的方向增长而成.当$ {{W}} = {{{\dot U}}_r}{{Q}} $时, 有:
$$ \begin{align} & {\left. {J({{W}})} \right|_{{{W}} = {{{{\ddot U}}}_r}{{Q}}}} - {\left. {J({{W}})} \right|_{{{W}} = {{{{\tilde U'}}}_r}{{Q}}}} = - 2{\varepsilon ^2} + o({\varepsilon ^2}) \end{align} $$ (B15) 从式(B14)$ \, \sim\, $(B15)得当$ {{W}} = {{{U'}}_r}{{Q}} $且$ {{W}} \ne {{{\tilde U}}_r}{{Q}} $时, $ J({{W}}) $沿$ {{\pmb {u}}_k} $方向是增的, 而沿$ {{\pmb {u}}_{jk}} $方向是减的, 所以$ J({{W}}) $在该平稳点处不可能取得局部极值.
-
[1] Helwani K. Fundamentals of adaptive filter theory. Adaptive Identification of Acoustic Multichannel Systems Using Sparse Representations. Cham: Springer International Publishing, 2015. [2] Haddadi F. Steady-state statistical performance analysis of subspace tracking methods. IEEE Transactions on Signal Processing, 2016, 64(18): 4781-4791 doi: 10.1109/TSP.2016.2572039 [3] 孔令智, 高迎彬, 李红增, 张华鹏.一种快速的多个主成分并行提取算法.自动化学报, 2017, 43(5): 835-842 doi: 10.16383/j.aas.2017.c160299Kong 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 [4] Nguyen V D, Abed-Meraim K, Linh-Trung N, Weber R. Generalized minimum noise subspace for array processing. IEEE Transactions on Signal Processing, 2017, 65(14): 3789-3802 doi: 10.1109/TSP.2017.2695457 [5] Du K L, Swamy M N S. Principal component analysis. Neural Networks and Statistical Learning. London: Springer, 2014. doi: 10.1007/978-1-4471-5571-3_12 [6] Doukopoulos X G, Moustakides G V. Fast and stable subspace tracking. IEEE Transactions on Signal Processing, 2008, 56(4): 1452-1465 doi: 10.1109/TSP.2007.909335 [7] Golub G H, Van Loan C F. Matrix computations. Mathematical Gazette, 1996, 47(5 Series Ⅱ): 392-396 http://dl.acm.org/citation.cfm?id=248979&dl=ACM&coll=portal&... [8] Wang R, Yao M L, Zhang D M, Zou H X. A novel orthonormalization matrix based fast and stable DPM algorithm for principal and minor subspace tracking. IEEE Transactions on Signal Processing, 2012, 60(1): 466-472 doi: 10.1109/TSP.2011.2169406 [9] Gao Y B, Kong X Y, Zhang H H, Hou L A. A weighted information criterion for multiple minor components and its adaptive extraction algorithms. Neural Networks, 2017, 89: 1-10 doi: 10.1016/j.neunet.2017.02.006 [10] Yang B. Projection approximation subspace tracking. IEEE Transactions on Signal Processing, 1995, 43(1): 95-107 doi: 10.1109/78.365290 [11] 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 [12] Kong X Y, Hu C H, Han C Z. A dual purpose principal and minor subspace gradient flow. IEEE Transactions on Signal Processing, 2012, 60(1): 197-210 doi: 10.1109/TSP.2011.2169060 [13] Kong X Y, Hu C H, Duan Z S. Principal Component Analysis Networks and Algorithms. Singapore: Springer, 2017. -
下载:
下载:
计量
- 文章访问数: 1209
- HTML全文浏览量: 293
- PDF下载量: 130
- 被引次数: 0
