2.3.2 TRPDA求解算法

本节使用分块坐标下降法（Block Coordinate Descent，BCD）求解TRPDA模型。另外，从黎曼优化的角度，本节是将问题化为广义Rayleigh商（generalized Rayleigh-quotient）问题，并可采用黎曼共轭梯度法（Riemannian conjugated gradient method）或者黎曼牛顿法求解（Riemannian Newton method）。

BCD 算法是一种迭代算法，它在每次迭代时交替固定U_j， j≠i来求解U_i。问题式（2.44）中U_j， j≠i已知，只需求解U_i，即只需求解子问题

问题式（2.45）中目标函数可进一步写为

式中， p=q=[1，…，i-1，i+1，…，M]，为以下定义的缩并。

定义：设A=（）∈，C=（）∈，p=[2···m]，q=[2···m]，则张量A和C 的模（p，q）缩并D=（d_ij）= A×∈，定义d_ij=。

命题2.1

令， i∈[M-1]，则A_i∈为对称矩阵。

证明 对任意i∈[M-1]，令B=X×_ML∏_j≠i×_j（U（j））T， C= X∏_j≠i×_j（U（ j） ）T。则B、C∈且

此时，对任意p、q∈[D_i]，有

故A_i为对称矩阵。

此时，目标函数式（2.46）可写为

从而，问题式（2.45）可重写为

对问题式（2.49）用拉格朗日乘子法，它可通过特征值分解求解，即U（i）为A_i的前d _i小的特征值应的d _i个特征向量所组成的矩阵。根据以上讨论，可得求解问题式（2.44）的以下算法。

输入：X∈，L∈RM×M，d=[d₁…d_M-1]，最大迭代次数maxIter。

输出：Y∈和U（i）∈， i∈[M-1]。

（1）随机初始化U（i）∈， i∈[M-1]

（2）对于i=1，2，…，M-1，令p=q=[1，…，i-1，i+1，…，M]。

（3）计算。

（4）计算A_i的奇异值分解，取U（i）为A_i最小的d_i个特征值对应的d_i个特征向量。

（5）收敛或达到最大迭代次数结束。

（6）计算Y=

BCD 算法的优点是设计简单，易于求解，但一般不能保证全局收敛性。TRPDA模型式（2.44）的目标函数可进一步化为

命题2.2

设B=， A=，则A为部分对称张量， B为对称矩阵，rank（B）≤N，且

A_＜M-1＞ =B

式中， A_＜M-1＞为A的（ M-1）模标准化矩阵展开。

性质2.2 设U₁∈，U₂∈，V₁∈，V₂∈，则（U₁⊗U₂ ）（V₁⊗V₂ ）=U₁V₁⊗U₂V₂

设A=（ X×_ML）×，由命题2.2和性质2.2，式（2.50）可写成

结合式（2.28）、式（2.50）和式（2.51），TRPDA问题式（2.44）可重写为

令P（i）=，i∈[M-1]，结合式（2.27），即U（i）∈为列正交矩阵，可得出P（i）为正交投影矩阵且rank（P（i））=d_i。

命题2.3[47]

若P（i）∈为正交投影矩阵且rank（P（i））=d_i，i∈[M-1]。令P=P（1）⊗…⊗P（M-1），则P 也为正交投影矩阵且rank（P）=d₁…d_M-1。

命题2.4[47]

若P∈为正交投影矩阵且rank（P）=d₁…d_M-1。则存在唯一的（ M-1）个正交投影矩阵P（i）∈，且rank（P（i））=d_i，i∈[M-1]，使得P=P（1）⊗…⊗P（ M-1）。

令（D，d）=（（D₁，d₁），…，（D_M-1，d_M-1）），定义集Gr（D，d）={（P（1），…，P（M-1））：rank（P（j））=d_j为正交投影矩阵 j∈[M-1]}

问题式（2.52）最终转化为

或者

文献[47]将问题式（2.54）称为广义 Rayleigh 商问题，并利用黎曼优化（Riemannian optimization）[48-49]技术提出了两种数值算法，即黎曼牛顿法和黎曼共轭梯度法。根据以上讨论，可得以下 TRPDA 求解算法，在不引起歧义情况下，我们简称TRPDA求解算法为TRPDA算法。

输入：训练样本集；类标注：C_i∈Z；子空间的维数：[d₁，…，d_M-1]。

输出：子空间S的基U（i）=[，…，]∈， i∈[M-1]；在子空间S上的表达。

（1）对每个样本X_i，构造对应局部块式（2.30）和式（2.31），利用式（2.37）计算对应矩阵L_i，利用式（2.39）计算样本选择矩阵S_i。

（2）对所有样本X，利用式（2.42）计算对齐矩阵L。

（3）利用前面的计算U（i）=[，…，]∈，i∈[M-1]；。

（4）利用式（2.29）计算样本X的表达Y。

（5）返回子空间S的基U（i），i∈[M-1]；在子空间S上的表达。