基于树型QR分解的自适应最小二乘滤波新算法

尹纯辉，王　凡，向　华

（1.武汉大学 数学与统计学院，湖北 武汉 430072；2.武汉华为研究所 技术接入部，湖北 武汉 430073）

基于树型QR分解的自适应最小二乘滤波新算法

尹纯辉1，王凡2，向华1

（1.武汉大学 数学与统计学院，湖北 武汉 430072；2.武汉华为研究所 技术接入部，湖北 武汉 430073）

本文以最小二乘滤波算法为基础，基于TSQR（Tall-Skinny QR）算法提出新的方法FtQR-LS（Flat-tree QR least squares）求解自适应滤波系数。在处理过程中，将目标矩阵按行分成多个子信息矩阵，对小规模子矩阵用传统QR分解，再用树型结构归约出目标矩阵QR分解。在处理中充分利用并行性，同时保持了数值稳定性，也有效地降低计算时间的开销。一定程度上，平衡了经典算法求解自适应滤波系数时计算复杂度与稳定性之间的矛盾。

QR分解；最小二乘；Givens旋转；Householder变换；FtQR-LS

最小二乘准则是经典算法求解自适应滤波时主要用到的准则，而在求解最小二乘滤波问题时最常用到的方法便是QR分解［1-2］。实现QR分解的算法有多种，如 Cholesky QR分解［3］，Gram-Schmidt正交化，Givens旋转［4-5］和Householder变换［3］。研究表明，Cholesky QR分解和普通（非修正）Cram-Schmidt正交化数值稳定性较差，Givens旋转和Householder变换因其在处理行列数较小时的目标矩阵高效性及数值稳定性［4］，成为实现QR分解中使用最频繁的两种方法。然而，在实际运用中经常会遇到特殊的大型矩阵，如高瘦矩阵，所谓的高瘦矩阵指的是矩阵的行数远远大于列数，有时行列数之比达100∶1，甚至10000∶1［3，6］。此时，如果仍直接使用Givens旋转和Householder变换，那么不仅要花费大量的时间去处理目标矩阵，最后还有可能会造成数值结果的不稳定。针对这种情形，本文利用了新的算法去实现QR分解，即FtQR-LS算法。这种算法的处理过程不同于Givens旋转和Householder变换，它的思想是将目标矩阵分解成许多个子矩阵，然后对子矩阵用树型结构进行QR分解。此种做法不仅能保证系统本身的鲁棒性，更重要的是利用并行性相当程度上减小了在处理目标矩阵时的时间开销。

1　求解自适应滤波系数的经典方法

1.1LMS算法

最小均方算法是一种搜索算法，LMS算法是自适应滤波理论中应用最广泛的算法，最主要的特点包括计算复杂度低、在平稳环境中易于收敛、利用有限精度实现时算法的稳定性等。

利用梯度算法可以推得LMS算法的递推公式为：

1.2RLS算法

对于RLS算法，即使输入信号相关矩阵的最大特征值与最小特征值相差比较大，也能够快速收敛，而且在时变环境中这类算法具有极好的稳定性。但这些优势均是以增加计算复杂度为代价而实现的。

在最小二乘意义下，可以得到RLS算法的递推公式［7］：

其中，

其中，λ为遗忘因子，且0＜λ＜1。

1.3QR-RLS算法

利用QR分解使输入数据矩阵对角化，可以得到递归最小二乘（RLS）方法的另一种实现方法。基于QR分解的递归最小二乘算法的主要优点是可以采用脉动阵实现，即利用并行性。

定义对角阵Λ（n）=diag（λN-1，λN-2，…，λ，1）和输入信号组成的矩阵X（n）其中Q是使

设上三角化的正交矩阵。则

为了使（5）式中范数最小，只有使

从而可得自适应滤波系数

2　FtQR-LS算法求解滤波系数

下面介绍新的QR分解算法：FtQR（Flat-tree QR），这种新的分解方式是基于TSQR［3，8-10］（Tall Skinny QR），其中需要处理的信息矩阵的行数远远大于其列数。实际计算中需要解决的问题所组成的目标矩阵的行数往往远超过其列数，如果还利用传统的算法去解决此类问题就带来计算时间和计算精度方面的问题。因此，需要提出新的解决方案，TSQR算法便是众多计算此类问题算法中效果十分显著的一类算法。

步骤一：首先对子矩阵A0进行QR分解，得到Q00和R00。其中，Q00是正交矩阵，R00是上三角阵。步骤一结束后，得到下面的分解

步骤三：将步骤二中得到的上三角矩阵R01和子矩阵A2结合，然后对结合后的矩阵进行QR分解，得到Q02和R02。其中，Q02是正交矩阵，R02是上三角矩阵。步骤三结束后，得到下面的分解

步骤四：将步骤三中得到的上三角矩阵R02和子矩阵A3结合并对结合后的矩阵进行QR分解，得到Q03和R03。其中，Q03是正交矩阵，R03是上三角矩阵。事实上，R03就是我们最终想要求解的上三角矩阵R。步骤四结束后，得到下面的分解

除了Givens变换，每个子矩阵的QR分解也可以通过Householder变换实现。

有了上述QR分解之后，类似于前文1.3节的QR-RLS算法，我们通过求解一个最小二乘问题得到自适应滤波系数，从而可得自适应滤波系数

3　FtQR算法的仿真性能及分析

FtQR在系统辨识中的应用。这个例子主要的目的是去估计未知系统的滤波系数，将未知系统的滤波系数记为w0。在实施过程中选择一个阶数（N阶）与未知系统相同的自适应滤波器。具体做法如下：

图1 系统辨识的模型

图2给出了FtQR-LS算法与LMS算法，RLS算法和QR-RLS算法迭代500次后计算自适应滤波系数后得到的均方误差的波动情况。其中，取遗忘因子λ=0.97，LMS算法的迭代步长μ=0.1。

从图2四种算法得到的均方误差曲线波动情况来看，与LMS算法相比QR-RLS算法，RLS算法和FtQR-LS算法得到的自适应滤波系数计算出的输出结果更接近于未知系统的期望。而本文用到的FtQR-LS算法得到的输出结果明显优于LMS算法。在块的QR分解中我们可以利用Householder变换，而不是像经典算法中仅用Givens变换。

图2　LMS，RLS，QR-RLS，FtQR-LS均方误差波动曲线

为了进一步测试本文算法的高效性，在上述实验的基础上，我们将输入信号的个数增加到600，800，1 000，2 000。分别用上述四种算法对其测试。表1列出了这四种算法在求解滤波系数时所需时间以及误差绝对值和的平均两个方面的对比情况。其中，T表示时间（单位：秒），err表示误差绝对值求和后的平均值。

从表1可以看到，当未知系统为3阶时，FtQR-LS算法在求解自适应滤波系数时与经典RLS，QR-RLS相比在时间花费上具有十分明显的优势；相比于LMS算法而言，FtQR-LS算法耗时略长些，但误差均小些，从实际应用综合考虑来说，可以得到FtQR-LS算法更优于LMS算法。

表2是在自适应滤波器阶数固定不变的情形下对四种算法的优劣作比较。下面改变自适应滤波器的阶数，然后比较四种算法在计算滤波系数所耗时长及在此过程中所产生的误差大小情况。其中，T表示时间（单位：秒），err表示误差绝对值求和后的平均值。

表1　FtQR-LS，LMS，RLS，QR-RLS四种算法耗时（T）及误差（err）

表2　FtQR-LS，RLS，QR-RLS，LMS四种算法耗时（T）及误差（err）

比较表2中几组实验得到的数据可以看出，在固定变量迭代次数为2 000次的情形下。当自适应滤波器的阶数从7阶逐渐增加到19阶时，看到在每一种情形下FtQR-LS算法耗时都小于RLS，QR-RLS算法；相比于LMS算法，从输出误差可以看出LMS算法在随着自适应滤波器阶数逐步增大到19阶时得到的输出误差的偏差较大，而FtQR-LS算法的得到的是数值依然是稳定的。综合考虑来看，FtQR-LS算法性能更好，具有实际应用价值。

4　小结

LMS算法虽然计算复杂度低，但随着滤波器阶数逐步增大时这种算法就不能保证每次计算得出的数值是稳定的。RLS算法，QR-RLS算法虽具有良好的数值稳定性，但它的计算复杂度是相当的高。为了平衡计算复杂度与数值稳定性，我们利用FtQR-LS算法求解最优自适应滤波系数，有效地降低了QR-RLS算法在每次迭代时的除法运算。FtQR-LS算法对块进行分解时用Householder变换替换经典算法中的Givens变换有效地降低求解自适应滤波系数的计算复杂度。本文使用FtQR-LS算法求解滤波系数时是基于后验误差，再者是否不需要求解最后一次迭代的滤波系数就能得到最优解值得进一步的探究。

［1］ Maddah-Ali M A，Sadrabadi M A，Khandani A K. Broadcast in MIMO systems based on a generalized QR decomposition：signaling and performance analysis ［J］.IEEE Transactions on Information Theory，2008，54（3）：1124-1138.

［2］ Li H，Wang B L.Method and apparatus for QR-factorizing matrix on a multiprocessor system：US，US 8543626 B2［P］.2013.

［3］ Benson A R，Gleich D F，Demmel J.Direct QR factorizations for tall-and-skinny matrices in MapReduce architectures［C］//2013 IEEE International Conference on Big Data，2013：264-272.

［4］ Leung H，Haykin S.Stability of recursive QRD-LS algorithms using finite-precision systolic array implementation［J］.IEEETransactionsonAcoustics，Speech，and Signal Processing，1989，37（5）：760-763.

［5］ Cioffi J M.The fast adaptive ROTOR's RLS algorithm ［J］.IEEE Transactions on Acoustics Speech and Signal Processing，1990，38（4）：631-653.

［6］ Rafique A，Kapre N，George A，et al.Enhancing performance of Tall-Skinny QR factorization using FPGAs［C］//IEEE International Conference on Field Programmable Logic andApplications，2012：443-450.

［7］ 刘郁林，万群.自适应滤波算法与实现［M］.4版.北京：电子工业出版社，2014：144-146.

［8］ Tayem N，Omer M，Raza S A，et al.Parallel TSQRTLS and QR-TLS factorization for joint time delay and frequency estimation［J］.Asilomar Conference on Signals，2013，118（1）：195-199.

［9］ Chen L，Petiton S A.TSQR based Krylov basis computation method on hybrid GPU cluster［C］//IEEE International Conference on CLUSTER Computing.IEEE，2015：106-109.

［10］Nadra K，Médard J J，Mul J D，et al.TSQR gate，delete function［J］.Molecular and Cellular Biology，2012，32 （23）：4794-4810.

The new algorithm of least squares adaptive filtering based on flat tree QR

YIN Chun-hui1，WANG Fan2，XIANG Hua1

（1.School of Mathematics and Statistics，Wuhan University，Wuhan Hubei 430072，China；2.Technology Access Department，Wuhan Institute of Huawei，Wuhan Hubei 430073，China）

In this paper we investigate the least squares method based on the newly presented TSQR algorithm in adaptive filtering.We introduce a new approach（Flat-tree QR least squares）FtQR-LS to seek the filtering coefficients.In this process，we divide the target matrix into a series of submatrices by row，and apply the traditional QR decomposition on small submatrices，then achieve a complete QR decomposition by a flat tree reduction.In this way we take advantage of parallelism，and meanwhile keep the numerical stability and effectively reduce computational time overhead.Our new algorithm keeps a balance between computational complexity and numerical stability in classical LS adaptive filtering algorithms.

QR decomposition；least square；Givens rotation；Householder transform；FtQR-LS

TN911.72

A

1004-4329（2016）03-012-05

10.14096/j.cnki.cn34-1069/n/1004-4329（2016）03-012-05

2016-04-15

国家自然科学基金项目（11571265，11471253）资助。

尹纯辉（1988-），男，硕士研究生，研究方向：数值代数与并行计算。