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.     

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.     

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

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

A numerically stable fast Newton-type adaptive filter based on order recursive least squares algorithm

This paper presents a numerically stable fast Newton-type adaptive filter algorithm. Two problems are dealt with in the paper. First, we derive the proposed algorithm from an order-recursive least squares algorithm. The result of the proposed algorithm is equivalent to that of the fast Newton transversal filter (FNTF) algorithm. However, the derivation process is different. Instead of extending a covariance matrix of the input based on the min-max and the max-min criteria, the derivation shown in this paper is to solve an optimum extension problem of the gain vector based on the information of the Mth-order forward or backward predictor. The derivation provides an intuitive explanation of the FNTF algorithm, which may be easier to understand. Second, we present stability analysis of the proposed algorithm using a linear time-variant state-space method. We show that the proposed algorithm has a well-analyzable stability structure, which is indicated by a transition matrix. The eigenvalues of the ensemble average of the transition matrix are proved all to be asymptotically less than unity. This results in a much-improved numerical performance of the proposed algorithm compared with the combination of the stabilized fast recursive least squares (SFRLS) and the FNTF algorithms. Computer simulations implemented by using a finite-precision arithmetic have confirmed the validity of our analysis.     

Regularized fast recursive least squares algorithms for adaptivefiltering

Fast recursive least squares (FRLS) algorithms are developed by using factorization techniques which represent an alternative way to the geometrical projections approach or the matrix-partitioning-based derivations. The estimation problem is formulated within a regularization approach, and priors are used to achieve a regularized solution which presents better numerical stability properties than the conventional least squares one. The numerical complexity of the presented algorithms is explicitly related to the displacement rank of the a priori covariance matrix of the solution. It then varies between O(5m) and that of the slow RLS algorithms to update the Kalman gain vector, m being the order of the solution. An important advantage of the algorithms is that they admit a unified formulation such that the same equations may equally treat the prewindowed and the covariance cases independently from the used priors. The difference lies only in the involved numerical complexity, which is modified through a change of the dimensions of the intervening variables. Simulation results are given to illustrate the performances of these algorithms     

Optimal linear estimation fusion .I. Unified fusion rules

This paper deals with data (or information) fusion for the purpose of estimation. Three estimation fusion architectures are considered: centralized, distributed, and hybrid. A unified linear model and a general framework for these three architectures are established. Optimal fusion rules based on the best linear unbiased estimation (BLUE), the weighted least squares (WLS), and their generalized versions are presented for cases with complete, incomplete, or no prior information. These rules are more general and flexible, and have wider applicability than previous results. For example, they are in a unified form that is optimal for all of the three fusion architectures with arbitrary correlation of local estimates or observation errors across sensors or across time. They are also in explicit forms convenient for implementation. The optimal fusion rules presented are not limited to linear data models. Illustrative numerical results are provided to verify the fusion rules and demonstrate how these fusion rules can be used in cases with complete, incomplete, or no prior information.     

QR methods of O(N) complexity in adaptive parameter estimation

Recent attention in adaptive least squares parameter estimation has been focused on methods derived from the QR factorization owing to the fact that the QR-based algorithms are much more numerically stable and accurate than the traditional pseudo-inverse-based algorithms, also known as normal equation-based algorithms, even though the former is usually much slower than the latter. This paper presents a fast adaptive least squares algorithm for the parameter estimation of linear and some nonlinear time-varying systems. The algorithm is based on Householder transformations. As verified by simulation results, this algorithm exhibits good numerical stability and accuracy. In addition, the new algorithm requires computation and storage with order of O(N) rather than O(N²) where N is the number of unknown parameters to be estimated. This algorithm can be easily extended to construct other kinds of algorithms, such as the generalized adaptive least squares algorithm, the augmented matrix algorithm, and the maximum likelihood algorithm     

A family of computationally efficient algorithms for multichannel signal processing—A tutorial review

This paper is concerned with the solution of block linear systems arising in multichannel digital signal processing. First the general problem of block matrix inversion and linear system solution is considered and a corresponding algorithm, recursive in nature, is developed, together with a block form of triangularization theorem. Subsequently these general schemes are specialized to block Toeplitz structures yielding most existing efficient algorithms. To this respect, matrices related to multichannel Wiener filtering, AR and ARMA modelling as well as s+1 steps ahead prediction are examined and related algorithms are described. Finally block banded Toeplitz systems are considered and two new efficient algorithms are presented, one recursive in nature and the other FFT based. They constitute natural extensions of methods already available for the single channel case and their derivation is simple due to the unified approach introduced in this paper.     

Fast adaptive algorithms for multichannel filtering and systemidentification

Fast transversal and lattice least squares algorithms for adaptive multichannel filtering and system identification are developed. Models with different orders for input and output channels are allowed. Four topics are considered: multichannel FIR filtering, rational IIR filtering, ARX multichannel system identification, and general linear system identification possessing a certain shift invariance structure. The resulting algorithms can be viewed as fast realizations of the recursive prediction error algorithm. Computational complexity is then reduced by an order of magnitude as compared to standard recursive least squares and stochastic Gauss-Newton methods. The proposed transversal and lattice algorithms rely on suitable order step-up-step-down updating procedures for the computation of the Kalman gain. Stabilizing feedback for the control of numerical errors together with long run simulations are included     

The Averaged, Overdetermined, and Generalized LMS Algorithm

This paper provides and exploits one possible formal framework in which to compare and contrast the two most important families of adaptive algorithms: the least-mean square (LMS) family and the recursive least squares (RLS) family. Existing and well-known algorithms, belonging to any of these two families, like the LMS algorithm and the RLS algorithm, have a natural position within the proposed formal framework. The proposed formal framework also includes - among others - the LMS/overdetermined recursive instrumental variable (ORIV) algorithm and the generalized LMS (GLMS) algorithm, which is an instrumental variable (IV) enable LMS algorithm. Furthermore, this formal framework allows a straightforward derivation of new algorithms, with enhanced properties respect to the existing ones: specifically, the ORIV algorithm is exported to the LMS family, resulting in the derivation of the averaged, overdetermined, and generalized LMS (AOGLMS) algorithm, an overdetermined LMS algorithm able to work with an IV. The proposed AOGLMS algorithm overcomes - as we analytically show here - the limitations of GLMS and possesses a much lower computational burden than LMS/ORIV, being in this way a better alternative to both algorithms. Simulations verify the analysis.     

On adaptive HMM state estimation

New online adaptive hidden Markov model (HMM) state estimation schemes are developed, based on extended least squares (ELS) concepts and recursive prediction error (RPE) methods. The best of the new schemes exploit the idempotent nature of Markov chains and work with a least squares prediction error index, using a posterior estimates, more suited to Markov models than traditionally used in identification of linear systems. These new schemes learn the set of N Markov chain states, and the a posteriori probability of being in each of the states at each time instant. They are designed to achieve the strengths, in terms of computational effort and convergence rates, of each of the two classes of earlier proposed adaptive HMM schemes without the weaknesses of each in these areas. The computational effort is of order N. Implementation aspects of the proposed algorithms are discussed, and simulation studies are presented to illustrate convergence rates in comparison to earlier proposed online schemes     

Regularized fast recursive least squares algorithms for finitememory filtering

Novel fast recursive least squares algorithms are developed for finite memory filtering, by using a sliding data window. These algorithms allow the use of statistical priors about the solution, and they maintain a balance between a priori and data information. They are well suited for computing a regularized solution, which has better numerical stability properties than the conventional least squares solution. The algorithms have a general matrix formulation, such that the same equations are suitable for the prewindowed as well as the covariance case, regardless of the a priori information used. Only the initialization step and the numerical complexity change through the dimensions of the intervening matrix variables. The lower bound of O (16m) is achieved in the prewindowed case when the estimated coefficients are assumed to be uncorrelated, m being the order of the estimated model. It is shown that a saving of 2m multiplications per recursion can always be obtained. The lower bound of the resulting numerical complexity becomes O(14m ), but then the general matrix formulation is lost     

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     

Optimal tracking of time-varying channels: a frequency domainapproach for known and new algorithms

In this paper, we developed a systematic frequency domain approach to analyze adaptive tracking algorithms for fast time-varying channels. The analysis is performed with the help of two new concepts, a tracking filter and a tracking error filter, which are used to calculate the mean square identification error (MSIE). First, we analyze existing algorithms, the least mean squares (LMS) algorithm, the exponential windowed recursive least squares (EW-RLS) algorithm and the rectangular windowed recursive least squares (RW-RLS) algorithm. The equivalence of the three algorithms is demonstrated by employing the frequency domain method. A unified expression for the MSIE of all three algorithms is derived. Secondly, we use the frequency domain analysis method to develop an optimal windowed recursive least squares (OW-RLS) algorithm. We derive the expression for the MSIE of an arbitrary windowed RLS algorithm and optimize the window shape to minimize the MSIE. Compared with an exponential window having an optimized forgetting factor, an optimal window results in a significant improvement in the h MSIE. Thirdly, we propose two types of robust windows, the average robust window and the minimax robust window. The RLS algorithms designed with these windows have near-optimal performance, but do not require detailed statistics of the channel     

A delta least squares lattice algorithm for fast sampling

Most shift operator-based adaptive algorithms exhibit poor numerical behavior when the input discrete time process is obtained from a continuous time process by fast sampling. This includes the shift operator based least squares lattice algorithm. We develop a delta least squares lattice algorithm. This algorithm has a low computational complexity compared with the delta Levinson RLS algorithm and shows better numerical properties compared with the shift least squares lattice algorithm under fast sampling. Computer simulations show that the new algorithm also outperforms an existing delta least squares lattice algorithm     

Recursive Extended Least Squares Parameter Estimation for Wiener Nonlinear Systems with Moving Average Noises

Many control algorithms are based on the mathematical models of dynamic systems. System identification is used to determine the structures and parameters of dynamic systems. Some identification algorithms (e.g., the least squares algorithm) can be applied to estimate the parameters of linear regressive systems or linear-parameter systems with white noise disturbances. This paper derives two recursive extended least squares parameter estimation algorithms for Wiener nonlinear systems with moving average noises based on over-parameterization models. The simulation results indicate that the proposed algorithms are effective.     

SER and outage of threshold-based hybrid selection/maximal-ratio combining over generalized fading channels

The average symbol-error rate and outage probability of threshold-based hybrid selection/maximal-ratio combining (T-HS/MRC) in generalized fading environments are analyzed. A T-HS/MRC combiner chooses the combined branches according to a predetermined normalized threshold and the strength of the instantaneous signal-to-noise ratio (SNR) of each branch. Therefore, the number of combined branches is a random variable, rather than a fixed number, as in conventional hybrid selection/maximal-ratio combining (H-S/MRC). Using the moment generating function method, a unified analysis of T-HS/MRC over various slow and frequency-nonselective fading channels is presented. Both independent, identically distributed and independent, nonidentically distributed diversity branches are considered. The derivation allows different M-ary linear modulation schemes. The theory is illustrated using coherent M-ary phase-shift keying in Nakagami-m fading as an example. It is shown that previous published results are incorrect.     

High precision approximate analytical solutions to ODE using LS-SVM

The problem of solving differential equations and the properties of solutions have always been an important content of differential equation the study. In practical application and scientific research, it is difficult to obtain analytical solutions for most differential equations. In recent years, with the development of computer technology, some new intelligent algorithms have been used to solve differential equations. They overcomes the drawback of traditional methods and provide the approximate solution in closed form (i.e., continuous and differentiable). The least squares support vector machine (LS-SVM) has nice properties in solving differential equations. In order to further improve the accuracy of approximate analytical solutions and facilitative calculation, a novel method based on numerical methods and LS-SVM methods is presented to solve linear ordinary differential equations (ODEs). In our approach, a high precise of the numerical solution is added as a constraint to the nonlinear LS-SVM regression model, and the optimal parameters of the model are adjusted to minimize an appropriate error function. Finally, the approximate solution in closed form is obtained by solving a system of linear equations. The numerical experiments demonstrate that our proposed method can improve the accuracy of approximate solutions.     

Majorization-minimization algorithms for wavelet-based image restoration.

Standard formulations of image/signal deconvolution under wavelet-based priors/regularizers lead to very high-dimensional optimization problems involving the following difficulties: the non-Gaussian (heavy-tailed) wavelet priors lead to objective functions which are nonquadratic, usually nondifferentiable, and sometimes even nonconvex; the presence of the convolution operator destroys the separability which underlies the simplicity of wavelet-based denoising. This paper presents a unified view of several recently proposed algorithms for handling this class of optimization problems, placing them in a common majorization-minimization (MM) framework. One of the classes of algorithms considered (when using quadratic bounds on nondifferentiable log-priors) shares the infamous "singularity issue" (SI) of "iteratively reweighted least squares" (IRLS) algorithms: the possibility of having to handle infinite weights, which may cause both numerical and convergence issues. In this paper, we prove several new results which strongly support the claim that the SI does not compromise the usefulness of this class of algorithms. Exploiting the unified MM perspective, we introduce a new algorithm, resulting from using l1 bounds for nonconvex regularizers; the experiments confirm the superior performance of this method, when compared to the one based on quadratic majorization. Finally, an experimental comparison of the several algorithms, reveals their relative merits for different standard types of scenarios.     

A linear, time-varying system framework for noniterativediscrete-time band-limited signal extrapolation

A technique for the analysis and design of noniterative algorithms for discrete-time, band-limited signal extrapolation is described. The approach involves modeling the extrapolation process as a linear, time-varying (LTV) system, or filter. Together with a previously developed Fourier theory for LTV systems, this model provides a frequency-domain transfer function representation for the extrapolation system. This representation serves as a powerful tool for characterizing and comparing the reconstruction properties of several well-known least squares optimal algorithms for band-limited extrapolation. Moreover, the frequency-domain setting provides a conceptually attractive means for understanding the process of extrapolation itself. Additionally, a least squares approximation methodology for designing LTV filters for band-limited extrapolation is developed. The design technique is shown to unify a broad class of algorithms for extrapolating discrete-time data and, further, to provide a means for designing new and improved extrapolation algorithms