A note on “On-line parameter identification algorithms basedon Householder transformation”

A detailed comparison of two on-line recursive least squares algorithms is presented. Liu's (see IEEE Trans. Signal Processing, vol.41, p.2863-71, Sept. 1993) fast on-line least squares algorithm based on Householder transformation and a stabilized version of a least squares algorithm based on the matrix pseudoinverse are considered     

Systolic implementations of up/down-dating cholesky factorization using vectorized Gram-Schmidt pseudo orthoganalization

We propose a new class ofhyperbolic Gram-Schmidt methods to simultaneously update and downdate the Cholesky factor of a sample covariance matrix efficiently with applications to sliding window recursive least squares (RLS) filtering problems. Several vectorized versions of this Gram-Schmidt approach are introduced, which include conventional column-updating, modified row/column-updating, and square-root-free methods. Comparisons to the existing known methods, such as Householder transformation and Givens rotation, are also given. Upon further reformulating these algorithms, a systolic triarray structure is proposed to facilitate VLSI implementations.This work is partially supported by a UC MICRO grant and the NSF grant NCR-8814407. It is also partially supported by NSF grant ECD-8803012-06.     

Image restoration using a conjugate gradient-based adaptive filtering algorithm

A new two-dimensional (2D) sample-based conjugate gradient (SCG) algorithm is developed for adaptive filtering. This algorithm is based on the conjugate gradient method of optimization and therefore has a fast convergence characteristic. The SCG is computationally simpler than the recursive least squares (RLS) algorithm. The SCG algorithm with the equation-error and output-error methods is investigated for application in image restoration. Simulation results show that the new algorithm significantly outperforms existing algorithms in the restoration of noisy images.This work was supported in part by a grant from the Colorado Advanced Software Institute.     

Systolic block Householder transformation for RLS algorithm withtwo-level pipelined implementation

The authors propose a systolic block Householder transformation (SBHT) approach to implement the HT on a systolic array and also propose its application to the RLS (recursive least squares) algorithm. Since the data are fetched in a block manner, vector operations are in general required for the vectorized array. However, a modified HT algorithm permits a two-level pipelined implementation of the SBHT systolic array at both the vector and word levels. The throughput rate can be as fast as that of the Givens rotation method. The present approach makes the HT amenable for VLSI implementation as well as applicable to real-time high-throughput applications of modern signal processing. The constrained RLS problem using the SBHT RLS systolic array is also considered     

Set-membership identification and filtering for signal processing applications

Optimal bounding ellipsoid (OBE) algorithms comprise a class of novel recursive identification methods for affine-in-parameters system and signal models. OBE algorithms exploit a priori knowledge of bounds on model disturbances to derive a monotonically nonincreasing set of solutions that are feasible in light of the observations and the model structure. In turn, these sets admit criteria for ascertaining the information content of incoming observations, obviating the expense of updating when data are redundant. Relative to classical recursive methods for this task, OBE algorithms are efficient, robust, and exhibit remarkable tracking ability, rendering them particularly attractive for realtime signal processing and control applications. After placing the OBE algorithms in the hierarchy of the broader set-membership identification methods, this article introduces the underlying set-theoretic concepts, compares and contrasts the various published OBE algorithms including the motivation for each development, then concludes with some illustrations of OBE algorithm performance. More recent work on the use of OBE processing infiltering tasks is also included in the discussion. The paper is a survey of a broad and evolving topic, and extensive references to further information are included.J.R.D. was supported in part by the National Science Foundation under Cooperative Agreement no. IBIS-9817485 and under grant no. MIP-9016734. Y.F.H. was supported in part by the NSF under grant no. 97-05173. Opinions, findings, or recommendations expressed are those of the authors and do not necessarily reflect the views of the NSF.     

Numerical stability properties of a QR-based fast leastsquares algorithm

The numerical stability of a recent QR-based fast least-squares algorithm is established from a backward stability perspective. A stability domain approach applicable to any least-squares algorithm, constructed from the set of reachable states in exact arithmetic, is presented. The error propagation question is shown to be subordinate to a backward consistency constraint, which requires that the set of numerically reachable variables be contained within the stability domain associated to the algorithm. This leads to a conceptually lucid approach to the numerical stability question which frees the analysis of stationary assumptions on the filtered sequences and obviates the tedious linearization methods of previous approaches. Moreover, initialization phenomena and considerations related to poorly exciting inputs admit clear interpretations from this perspective. The algorithm under study is proved, in contrast to many fast algorithms, to be minimal     

AR谱估计的一种自适应算法

本文给出Householder变换的一种实时递推算法及其收敛性证明,并用此算法进行AR自适应谱估计。仿真计算表明,此算法具有计算结果准确、可以实时判阶和快速跟踪性好等特点。     

空间相关环境下一种稳健的V-BLAST迭代检测算法

利用Householder变换,并结合WY表示形式,该文首先提出一种修正的Householder QR分解(M-H-QRD)算法,与排序QRD(S-QRD)检测算法相比:M-H-QRD检测算法在空间相关信道环境下具有稳健的数值特性;然后以此为基础,提出了一种基于M-H-QRD的V-BLAST迭代检测算法。仿真结果表明:在空间相关信道环境下,该算法比S-QRD检测算法、M-H-QRD检测算法在性能上具有明显的改善;与标准的V-BLAST算法相比,在高信噪比范围,迭代检测算法取得了与标准的V-BLAST算法几乎同等的性能,在中低信噪比范围,迭代检测算法优于标准的V-BLAST检测算法,同时数值特性比标准的V-BLAST检测算法更为稳健。     

基于ADSP-TS201的复数QR分解算法的递归实现

复矩阵的QR分解在很多领域都有重要的应用,但是现有算法没有给出Householder变换矩阵的递归表达式,从而限制了它的使用,对此进行了修正,并在此基础上介绍了该算法在ADSP-TS201上的具体实现。     

空时自适应处理的滑窗递推QR算法

在局部平稳的杂波环境下,滑窗样本选取方法可以比较准确地估计检测单元的杂波统计特性。该文提出基于滑窗选取样本的递推QR算法,它采用双曲Householder变换实现QR分解的递推,能有效地抑制局部平稳杂波,且具有数值稳定性好,计算量小的优点。仿真数据处理和实测数据处理验证了该方法的有效性。     

Finding all the DC solutions of a certain class of piecewise-linear circuits

The problem of finding all the DC solutions of a certain class of piecewise-linear electronic circuits containing locally passive and locally active one-ports is considered in this paper. An effective method enabling us to locate the solutions is developed. The method constitutes the crucial point of an algorithm based on the idea of successive contraction, division, and elimination that is capable of determining all the solutions. Several numerical examples are given, and some comparison analyses are performed confirming the usefulness of the proposed approach.This work was supported by the State Committee for Scientific Research (KBN) under grant 8T11B0911.     

Parallel implementation of synthetic aperture radar algorithms

Two sequences of operations necessary for implementation of high resolution image formation in strip and spotlight modes of the synthetic aperture radar (SAR) are presented. The sequences are mapped onto a mesh-connected SIMD architecture. The mapping includes not only parallel implementation of all the basic computation steps, but also all the necessary data transformation and communication operations. Detailed estimates of the processing times are provided for Hughes Research Laboratories Systolic/Cellular architecture.This work was partially supported by NSF grant No MIP-8714689     

A new system identification method for fast echo cancelerinitialization

Proposes a new recursive version of an earlier technique for fast initialization of data-driven echo cancelers (DDECs). The speed of convergence and the covariance of the estimate of the proposed technique are comparable to the recursive least squares (RLS) algorithm, however, the computational complexity is no greater than the least mean square (LMS) algorithm. Analysis of computational complexity and the estimation error is also provided. Simulation results based on both floating-point and fixed-point arithmetic illustrate a remarkable improvement in terms of speed of convergence and steady-state error over the computationally comparable LMS algorithm     

二维滑动矩形窗傅氏变换的快速递推算法

该文利用相邻滑动窗数据之间的关系以及傅氏变换的平移性质,提出一种二维滑动矩形窗傅氏变换的快速递推算法。文中分析了该快速递推算法的复杂度和传统直接计算法的复杂度,证明了新的快速递推法可以大大降低计算复杂性,尤其是在图像尺寸和窗口尺寸较大的场合中。该算法可以改善滑窗傅氏变换或Gabor变换的计算效率。     

Finite word-length effects in recursive least squares algorithms with application to adaptive equalization

In this paper we provide a summary of recent and new results on finite word length effects in recursive least squares adaptive algorithms. We define the numerical accuracy and numerical stability of adaptive recursive least squares algorithms and show that these two properties are related to each other, but are not equivalent. The numerical stability of adaptive recursive least squares algorithms is analyzed theoretically and the numerical accuracy with finite word length is investigated by computer simulation. It is shown that the conventional recursive least squares algorithm gives poor numerical accuracy when a short word length is used. A new form of a recursive least squares lattice algorithm is presented which is more robust to round-off errors compared to the conventional form. Optimum scaling of recursive least squares algorithms for fixedpoint implementation is also considered.     

一种基于Householder变换的递归 QRD-LS算法

本文提出了一种采用Householder变换实现的递归QRD-LS算法,该算法通过采用Householder变换取代Giv- ens旋转递归实现复矩阵的QR分解来求解LS问题,可以获得比基于Givens旋转的QRD—LS算法更快的处理速度。此外, 算法引入了复数QR分解,解决了算法只能处理实数信号的问题。通过定义新的数据矩阵,算法还可以合并求解数据域正规方程中的系数矩阵和右侧向量,从而提高了计算效率。通过对其在智能天线中的应用进行仿真,验证了算法的性能。     

Decentralized array processing using the MODE algorithm

Centralized methods for source location using sensor arrays have computational and communication burdens that increase significantly with the number of sensors in the array. Therefore, these methods may not be usable in the applications involving very large arrays. In such applications, the data processing may need to be decentralized. This paper introduces two methods for decentralized array processing, based on the recently proposed MODE algorithm. For prescribed nonoverlapping subarrays, both methods are shown to be statistically optimal in the sense that asymptotically they provide the most accurate decentralized estimates of source location parameters. The problem of subarray selection to further optimize the estimation accuracy is only briefly addressed. The two methods are intended for different types of applications: the first should be preferred when there exist significant possibilities for local processing or for parallel computation in the central processor; otherwise the second method should be preferred. The accuracy of the two decentralized methods is compared to the centralized Cramér-Rao bound, both analytically and numerically, in order to provide indications about the loss of accuracy associated with decentralized processing.The work of P. Stoica was supported by a grant from the Royal Swedish Academy of Engineering Sciences and by the Swedish Research Council for Engineering Sciences under contract 91-676. The work of A. Nehorai was supported by the Air Force Office of Scientific Research under grant no. AFOSR-90-0164, and by the Office of Naval Research under grant no. N00014-91-J-1298.on leave at the Department of Applied Electronics, Chalmens University of Technology, 2-41296 Göthensberg, Sweeden.     

Complex scaled tangent rotations (CSTAR) for fast space-timeadaptive equalization of wireless TDMA

A new update algorithm for space-time equalization of wireless time-division multiple access signals is presented. The method is based on a modified QR factorization that reduces the computational complexity of the traditional QR-decomposition based recursive least squares method and maintains numerical stability. Square roots operations are avoided due to the use of an approximately orthogonal transformation, defined complex scaled tangent rotation     

用Householder变换的递推AR模型化与谱估计算法

Housecholder变换用于上三角化是基于线性预测误差方程的数据阵。可以证明,由上三角阵的主对角元素便可得到各阶AR模型的残差平方和。因此用逐列处理的方法可以构成 AR 模型化与谱估计的递推算法。在大多数情况下,本文的算法不仅给出与协方差算法或修正协方差算法相同的计算结果;而且当计算中存在严重的数值病态问题时,协方差法和修正协方差法无法获得好的AR谱估计,而本文的算法则仍然可以获得好的估计。文中给出了典型的计算例子。     

一种快速递归全局最小二乘算法

针对FIR系统输入和输出信号均被噪声干扰的情况,提出一种快速递归全局最小二乘(XS-RTLS)算法用于迭代计算全局最小二乘解,算法沿着输入数据的符号方向并采用著名的快速增益矢量,搜索约束瑞利商(c-RQ)的最小值得到系统参数估计。算法关于方向更新矢量的内积运算可通过加减运算实现,有效降低了计算复杂度;另外XS-RTLS算法没有进行相关矩阵求逆递归运算,因而具有长期稳定性,算法的全局收敛性通过Laslle不变性原理得到证明。最后通过仿真比较了XS-RTLS算法和递归最小二乘(RLS)算法在非时变系统和时变系统中的性能,验证了XS-RTLS算法的长期稳定性。