Rotation-based RLS algorithms: unified derivations, numericalproperties, and parallel implementations

This work presents a unified derivation of four rotation-based recursive least squares (RLS) algorithms. They solve the adaptive least squares problems of the linear combiner, the linear combiner without a desired signal, the single channel, and the multichannel linear prediction and transversal filtering. Compared to other approaches, the authors' derivation is simpler and unified, and may be useful to readers for better understanding the algorithms and their relationships. Moreover, it enables improvements of some algorithms in the literature in both the computational and the numerical issues. All algorithms derived in this work are based on Givens rotations. They offer superior numerical properties as shown by computer simulations. They are computationally efficient and highly concurrent. Aspects of parallel implementation and parameter identification are discussed     

适于参数识别的多信道QRD自适应格型算法

本文基于格型滤波器的阶递归特性和Givens旋转算法的优越数值性能,推导了两种多信道递归最小二乘格型算法。第一种算法的推导是直接基于对输入数据矩阵进行正交-三角分解,并利用Givens旋转方法来计算其正交-三角分解。首先对输入数据矩阵进行预旋转,然后重复利用单信道Givens格型算法,便可得到第二种算法。两种算法都具有优越的数值性能,尤其是对有限字长的稳健性。待估计的滤波器参数矢量可根据算法的内部变量直接提取,而无需额外的三角阵进行后向代入求解运算。两信道参数识别的计算机模拟结果验证了本文的推导。     

QRD-BASED MULTICHANNEL ADAPTIVE LATTICEALGORITHMS FOR THE PARAMETERIDENTIFICATION PROBLEM

A pair of multichannel recursive least squares (RLS) adaptive lattice algorithms based on the order recursive of lattice filters and the superior numerical properties of Givens algorithms is derived in this paper. The derivation of the first algorithm is based on QR decomposition of the input data matrix directly, and the Givens rotations approach is used to compute the QR decomposition. Using first a prerotation of the input data matrix and then a repetition of the single channel Givens lattice algorithm, the second algorithm can be obtained. Both algorithms have superior numerical properties, particularly the robustness to wordlength limitations. The parameter vector to be estimated can be extracted directly from internal variables in the present algorithms without a backsolve operation with an extra triangular array. The results of computer simulation of the parameter identification of a two-channel system are presented to confirm efficiently the derivation.     

Multiprocessor Implementation of Adaptive Digital Filters

Adaptive filters, employing the transversal filter structure and the least mean square (LMS) adaptation algorithm, or its variations, have found wide application in data transmission equalization, echo cancellation, prediction, spectral estimation, on-line system identification, and antenna arrays. Recently, in response to requirements of fast start-up, or fast tracking of temporal variations, fast recursive least squares (FRLS) adaptation algorithms for both transversal and lattice filter structures have been proposed. These algorithms offer faster convergence than is possible with the LMS/ transversal adaptive filters, at the price of a five-to-tenfold increase in the number of multiplications, divisions, and additions. Here we discuss architectures and implementations of the LMS/transversal, fast-converging FRLS filter, and lattice filter algorithms which minimize the required hardware speed. We show how each of these algorithms can be partitioned so as to be realizable with an architecture based on multiple parallel processors.     

On the duality between fast QR methods and lattice methods in leastsquares adaptive filtering

The authors show that fast QR methods and lattice methods in least squares adaptive filtering are duals and follow from identical geometric principles. Whereas the lattice methods compute the residuals of a projection operation via the forward and backward prediction errors, the QR methods compute instead the weights used in the projections. Within this framework, the parameter identification problem is solved using fast QR methods by showing that the reflection coefficients and tap parameters of a least squares lattice filter operating in the joint process mode are immediately available as internal variables in the fast QR algorithms. This parameter set can be readily exploited in system identification, signal analysis, and linear predictive coding, for example. The relations derived also lead to a fast least squares algorithm of minimal complexity that is a hybrid between a QR and a lattice algorithm. The algorithm combines the order recursive properties of the lattice approach with the robust numerical behavior of the QR approach     

A state-space approach to adaptive RLS filtering

Adaptive filtering algorithms fall into four main groups: recursive least squares (RLS) algorithms and the corresponding fast versions; QR- and inverse QR-least squares algorithms; least squares lattice (LSL) and QR decomposition-based least squares lattice (QRD-LSL) algorithms; and gradient-based algorithms such as the least-mean square (LMS) algorithm. Our purpose in this article is to present yet another approach, for the sake of achieving two important goals. The first one is to show how several different variants of the recursive least-squares algorithm can be directly related to the widely studied Kalman filtering problem of estimation and control. Our second important goal is to present all the different versions of the RLS algorithm in computationally convenient square-root forms: a prearray of numbers has to be triangularized by a rotation, or a sequence of elementary rotations, in order to yield a postarray of numbers. The quantities needed to form the next prearray can then be read off from the entries of the postarray, and the procedure can be repeated; the explicit forms of the rotation matrices are not needed in most cases     

Modular and numerically stable fast transversal filters formultichannel and multiexperiment RLS

The authors present scalar implementations of multichannel and multiexperiment fast recursive least squares algorithms in transversal filter form, known as fast transversal filter (FTF) algorithms. By processing the different channels and/or experiments one at a time, the multichannel and/or multiexperiment algorithm decomposes into a set of intertwined single-channel single-experiment algorithms. For multichannel algorithms, the general case of possibly different filter orders in different channels is handled. Geometrically, this modular decomposition approach corresponds to a Gram-Schmidt orthogonalization of multiple error vectors. Algebraically, this technique corresponds to matrix triangularization of error covariance matrices and converts matrix operations into a regular set of scalar operations. Modular algorithm structures that are amenable to VLSI implementation on arrays of parallel processors naturally follow from the present approach. Numerically, the resulting algorithm benefits from the advantages of triangularization techniques in block processing     

A recursive least M-estimate algorithm for robust adaptive filtering in impulsive noise: fast algorithm and convergence performance analysis

This paper studies the problem of robust adaptive filtering in impulsive noise environment using a recursive least M-estimate algorithm (RLM). The RLM algorithm minimizes a robust M-estimator-based cost function instead of the conventional mean square error function (MSE). Previous work has showed that the RLM algorithm offers improved robustness to impulses over conventional recursive least squares (RLS) algorithm. In this paper, the mean and mean square convergence behaviors of the RLM algorithm under the contaminated Gaussian impulsive noise model is analyzed. A lattice structure-based fast RLM algorithm, called the Huber Prior Error Feedback-Least Squares Lattice (H-PEF-LSL) algorithm is derived. Part of the H-PEF-LSL algorithm was presented in ICASSP 2001. It has an order O(N) arithmetic complexity, where N is the length of the adaptive filter, and can be viewed as a fast implementation of the RLM algorithm based on the modified Huber M-estimate function and the conventional PEF-LSL adaptive filtering algorithm. Simulation results show that the transversal RLM and the H-PEF-LSL algorithms have better performance than the conventional RLS and other RLS-like robust adaptive algorithms tested when the desired and input signals are corrupted by impulsive noise. Furthermore, the theoretical and simulation results on the convergence behaviors agree very well with each other.     

Adaptive Volterra filtering with complete lattice orthogonalization

The article presents a new recursive least squares (RLS) adaptive nonlinear filter, based on the Volterra series expansion. The main approach is to transform the nonlinear filtering problem into an equivalent multichannel, but linear, filtering problem. Then, the multichannel input signal is completely orthogonalized using sequential processing multichannel lattice stages. With the complete orthogonalization of the input signal, only scalar operations are required, instability problems due to matrix inversion are avoided and good numerical properties are achieved. The avoidance of matrix inversion and vector operations reduce the complexity considerably, making the filter simple, highly modular and suitable for VLSI implementations. Several experiments demonstrating the fast convergence properties of the filter are also included     

Adaptive blind equalization using second- and higher orderstatistics

This paper presents two classes of adaptive blind algorithms based on second- and higher order statistics. The first class contains fast recursive algorithms whose cost functions involve second and third- or fourth-order cumulants. These algorithms are stochastic gradient-based but have structures similar to the fast transversal filters (FTF) algorithms. The second class is composed of two stages: the first stage uses a gradient adaptive lattice (GAL) while the second stage employs a higher order-cumulant (HOC) based least mean squares (LMS) filter. The computational loads for these algorithms are all linearly proportional to the number of taps used. Furthermore, the second class, as various numerical examples indicate, yields very fast convergence rates and low steady state mean square errors (MSE) and intersymbol interference (ISI). MSE convergence analyses for the proposed algorithms are also provided and compared with simulation results     

Recursive least squares identification methods for multivariate pseudo-linear systems using the data filtering

This paper concerns the parameter identification methods of multivariate pseudo-linear autoregressive systems. A multivariate recursive generalized least squares algorithm is presented as a comparison. By using the data filtering technique, a multivariate pseudo-linear autoregressive system is transformed into a filtered system model and a filtered noise model, and a filtering based multivariate recursive generalized least squares algorithm is developed for estimating the parameters of these two models. The proposed algorithm achieves a higher computational efficiency than the multivariate recursive generalized least squares algorithm, and the simulation results prove that the proposed method is effective.     

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.     

Adaptive Reduced-Rank Processing Based on Joint and Iterative Interpolation, Decimation, and Filtering

We present an adaptive reduced-rank signal processing technique for performing dimensionality reduction in general adaptive filtering problems. The proposed method is based on the concept of joint and iterative interpolation, decimation and filtering. We describe an iterative least squares (LS) procedure to jointly optimize the interpolation, decimation and filtering tasks for reduced-rank adaptive filtering. In order to design the decimation unit, we present the optimal decimation scheme and also propose low-complexity decimation structures. We then develop low-complexity least-mean squares (LMS) and recursive least squares (RLS) algorithms for the proposed scheme along with automatic rank and branch adaptation techniques. An analysis of the convergence properties and issues of the proposed algorithms is carried out and the key features of the optimization problem such as the existence of multiple solutions are discussed. We consider the application of the proposed algorithms to interference suppression in code-division multiple-access (CDMA) systems. Simulations results show that the proposed algorithms outperform the best known reduced-rank schemes with lower complexity.     

Adaptive lattice bilinear filters

Two fast least-squares lattice algorithms for adaptive nonlinear filters equipped with bilinear system models are presented. The lattice filter formulation transforms the nonlinear filtering problem into an equivalent multichannel linear filtering problem, thus using multichannel lattice filtering algorithms to solve the nonlinear filtering problem. The computational complexity of the algorithms is an order of magnitude smaller than that of previously available methods. The first of the two approaches is an equation error algorithm that uses the measured desired response signal directly to compute the adaptive filter outputs. This method is conceptually very simple, but results in biased system models in the presence of measurement noise. The second is an approximate least-squares output error solution; the past samples of the output of the adaptive system itself are used to produce the filter output at the current time. Results indicate that the output error algorithm is less sensitive to output measurement noise than the equation error method     

Easy and effective stabilisation measure for fast recursive least squares algorithms for adaptive transversal filters

Fast recursive least squares (FRLS) algorithms are known for their favourable convergence characteristics. They are of special interest for the fast adaptation of transversal filters of high order N. Unfortunately FRLS algorithms have a tendency towards numeric instability. A new and effective stabilisation measure is presented for a 0(7N) FRLS algorithm which needs only one additional multiplication per iteration step.<>     

Piecewise linear system modeling based on a continuous thresholddecomposition

The continuous threshold decomposition is a segmentation operator used to split a signal into a set of multilevel components. This decomposition method can be used to represent continuous multivariate piecewise linear (PWL) functions and, therefore, can be employed to describe PWL systems defined over a rectangular lattice. The resulting filters are canonical and have a multichannel structure that can be exploited for the development of rapidly convergent algorithms. The optimum design of the class of PWL filters introduced in this paper can be postulated as a least squares problem whose variables separate into a linear and a nonlinear part. Based on this feature, parameter estimation algorithms are developed. First, a block data processing algorithm that combines linear least-squares with grid localization through recursive partitioning is introduced. Second, a time-adaptive method based on the combination of an RLS algorithm for coefficient updating and a signed gradient descent module for threshold adaptation is proposed and analyzed. A system identification problem for wave propagation through a nonlinear multilayer channel serves as a comparative example where the concepts introduced are tested against the linear, Volterra, and neural network alternatives     

Fast adaptive algorithms for AR parameters estimation using higherorder statistics

Time-varying statistics in linear filtering and linear estimation problems necessitate the use of adaptive or time-varying filters in the solution. With the rapid availability of vast and inexpensive computation power, models which are non-Gaussian even nonstationary are being investigated at increasing intensity. Statistical tools used in such investigations usually involve higher order statistics (HOS). The classical instrumental variable (IV) principle has been widely used to develop adaptive algorithms for the estimation of ARMA processes. Despite, the great number of IV methods developed in the literature, the cumulant-based procedures for pure autoregressive (AR) processes are almost nonexistent, except lattice versions of IV algorithms. This paper deals with the derivation and the properties of fast transversal algorithms. Hence, by establishing a relationship between classical (IV) methods and cumulant-based AR estimation problems, new fast adaptive algorithms, (fast transversal recursive instrumental variable-FTRIV) and (generalized least mean squares-GLMS), are proposed for the estimation of AR processes. The algorithms are seen to have better performance in terms of convergence speed and misadjustment even in low SNR. The extra computational complexity is negligible. The performance of the algorithms, as well as some illustrative tracking comparisons with the existing adaptive ones in the literature, are verified via simulations. The conditions of convergence are investigated for the GLMS     

A two-dimensional fast lattice recursive least squares algorithm

This paper is mainly devoted to the derivation of a new two-dimensional fast lattice recursive least squares (2D FLRLS) algorithm. This algorithm updates the filter coefficients in growing-order form with linear computational complexity. After appropriately defining the “order” of 2D data and exploiting the relation with 1D multichannel, “order” recursion relations and shift invariance property are derived. The geometrical approaches of the vector space and the orthogonal projection then can be used for solving this 2D prediction problem. We examine the performances of this new algorithm in comparison with other fast algorithms     

变遗忘因子递推最小二乘Hammerstein系统辨识算法

摘.要:本论文研究了单输入单输出非线性Hammerstein系统的辨识问题,提出了一种具有变遗忘因子的递推最小二乘算法.由于Hammerstein系统模型的非线性特征,传统的递推最小二乘算法无法直接用来解决该系统的辨识问题.为此,论文将Hammerstein系统参数进行了映射变换,使得变换后的系统参数与Hammerst...     

A class of least-squares filtering and identification algorithmswith systolic array architectures

A unified approach is presented for deriving a large class of new and previously known time and order recursive least-squares algorithms with systolic array architectures, suitable for high throughput rate and VLSI implementations of space-time filtering and system identification problems. The geometrical derivation given is unique in that no assumption is made concerning the rank of the sample data correlation matrix. This method utilizes and extends the concept of oblique projections, as used previously in the derivations of the least-squares lattice algorithms. Both the growing and sliding memory, exponentially weighted least-squares criteria are considered