Class of recursive sequential regression algorithms

A class of sequential regression algorithms for recursive or infinite impulse response (IIR) adaptive filters is discussed. Results using these algorithms are given for an all-pole and a pole-zero example.     

A class of recursive maximum-likelihood algorithms

This letter features the derivation of a new recursive maximum-likelihood (RML) algorithm. A simplified version of this algorithm is the same as the RML algorithm proposed in [1]. The relative performance of these algorithms is studied with the help of an example in spectral estimation.     

Restructured recursive DCT and DST algorithms

The discrete cosine transform (DCT) and the discrete sine transform (DST) have found wide applications in speech and image processing, as well as telecommunication signal processing for the purpose of data compression, feature extraction, image reconstruction, and filtering. In this paper, we present new recursive algorithms for the DCT and the DST. The proposed method is based on certain recursive properties of the DCT coefficient matrix, and can be generalized to design recursive algorithms for the 2-D DCT and the 2-D DST. These new structured recursive algorithms are able to decompose the DCT and the DST into two balanced lower-order subproblems in comparison to previous research works. Therefore, when converting our algorithms into hardware implementations, we require fewer hardware components than other recursive algorithms. Finally, we propose two parallel algorithms for accelerating the computation     

Strong diffusion approximations for recursive stochastic algorithms

Lai and Robbins (1978) prove strong diffusion approximations for the Robbins-Monro stochastic approximation algorithm. We show that similar strong approximations hold for stochastic algorithms at the level of generality proposed in the monograph of Benveniste, Metivier and Priouret (1990), wherein algorithms with generally discontinous right-hand sides driven by conditionally Markovian data are considered. The relevance of our result is demonstrated on an estimation algorithm with a discontinuous right-hand side which is used in data communication. The technique of adaptive delta modulation used in digital communication is considered     

Initial convergence of recursive maximum-likelihood identification algorithms

The effects of modifications proposed by S?derstr?m on the performance of the well known approximate maximum-likelihood identification algorithm based on recursive least squares arc tested on short records. The modified algorithm is found to be susceptible to instability and slow convergence.     

Mixed modality recursive least squares and radial basisfunction-based scheme for transit time estimation in multiphaseflow

Estimation of transit time in multiphase flow from a number of sensor measurements has major importance in the oil and chemical industries. A new mixed modality scheme is proposed which employs recursive least squares adaptive filtering together with a radial basis function network to estimate, in real-time, multiphase flow transit time. The technique also provides a measure of the turbulence within the flow and an output which indicates the confidence in the estimates. The performance of the network is demonstrated on multiphase flow measurement datasets     

Efficient order recursive algorithms for multichannel least squaresfiltering

Four efficient order-recursive algorithms for least-squares (LS) multichannel FIR filtering and multivariable system identification are developed. The need for such algorithms arises when the system model assigns an unequal number of delay elements to each input channel. All proposed schemes provide considerable improvements over overparametrization or the zero padding approach. First, a block-structures algorithm is derived. It operates on boxes, or blocks, whose dimensions successively increase until their size equals the number of input channels. As a result, it requires linear system solvers and matrix multiplications. The second algorithm manages to get free of block operations by proper decomposition of each block step involved in the first method into a number of scalar steps equal to the size of the block. The third and the fourth algorithms provide highly concurrent alternatives that reduce processing time by an order magnitude. An illustrative example from multichannel autoregressive spectral estimation is supplied     

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     

A class of modified adaptive recursive filter algorithms

A new class or adaptive infinite impulse response ( IIR) or recursive filter algorithms is obtained by incorporating a simple modification in the correction vectors of some existing algorithms. The resulting class of algorithms explores the inherent parallelism present in their coefficient update equations, and hence the possibility of faster initial convergence. Two IIR filter algorithms are considered for discussion and simulation.     

Fast recursive algorithms for short-time discrete cosine transform

Local adaptive signal processing can be carried out using the short-time discrete cosine transform (DCT). Two fast recursive algorithms for computing the short-time DCT are presented. The algorithms are based on a recursive relationship between three subsequent local DCT spectra. The computational complexity of the algorithms is compared with that of fast DCT algorithms     

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     

Underdetermined-order recursive least-squares adaptive filtering:the concept and algorithms

Underdetermined recursive least-squares (URLS) adaptive filtering is introduced. In particular, the URLS algorithm is derived and shown to be a direct consequence of the principle of minimal disturbance. By exploiting the Hankel structure of the filter input matrix, the fast transversal filter (FTF) version of the URLS algorithm (URLS-FTF) is derived including sliding window and growing window types. The computational complexity is reduced to O(N)+O(m), where N is the adaptive filter length, and m is the order of the URLS algorithm. In addition, the efficient URLS (EURLS) algorithm, which does not compute the filter coefficients explicitly, thereby significantly reducing the computational load, is presented. Some earlier adaptive algorithms such as the averaged LMS, filtered-X LMS, and fast conjugate gradient are shown to be suboptimal approximations of the URLS algorithm. Instrumental variable approximations are also discussed. The URLS algorithm has a whitening effect on the input, signal, which provides immunity to the eigenvalue spread of the input signal correlation matrix. Although the algorithm is sensitive to observation noise, it has good tracking characteristics, and tradeoffs can be found by tuning the step size. The utility of the URLS algorithms, in its basic form and FTF realization, depends heavily on the practical applicability of the mth-order sliding window estimate of the covariance matrix and mth-order PTF relations. The feasibility of the URLS family in practical applications is demonstrated in channel equalization and acoustic echo cancellation     

Some new algorithms for recursive estimation in constant linear systems

Recursive least-squares estimates for processes that can be generated from finite-dimensional linear systems are usually obtained via ann times nmatrix Riccati differential equation, wherenis the dimension of the state space. In general, this requires the solution ofn(n + 1)/2simultaneous nonlinear differential equations. For constant parameter systems, we present some new algorithms that in several cases require only the solution of less than2nporn(m + p)simultaneous nonlinear differential equations, wheremandpare the dimensions of the input and observation processes, respectively. These differential equations are said to be of Chandrasekhar type, because they are similar to certain equations introduced in 1948 by the astrophysicist S. Chandrasekhar, to solve finite-interval Wiener-Hopf equations arising in radiative transfer. Our algorithms yield the gain matrix for the Kalman filter directly without having to solve separately for the error-covariance matrix and potentially have other computational benefits. The simple method used to derive them also suggests various extensions, for example, to the solution of nonsymmetric Riccati equations.     

Fast recursive algorithms for morphological operators based on thebasis matrix representation

A real-time implementation method for the most general morphological system, the so-called grayscale function processing (FP) system is presented. The proposed method is an extension of our previous works (1993, 1995) using the matrix representation of the FP system with a basis matrix (BM) and a block basis matrix (BBM) composed of grayscale structuring elements (GSE). In order to further improve the computational efficiency of the basis matrix representation, we propose recursive algorithms based on the observation of the BM and BBM. The efficiency of the proposed algorithms is gained by avoiding redundant steps in computing overlapping local maximum or minimum operations. It is shown that, with the proposed scheme, both opening and closing can be determined in real time by 2N-2 additions and 2N-2 comparisons, and OC and CO by 4N-4 additions and 4N-4 comparisons, when the size of the GSE is equal to N. It is also shown that the proposed recursive opening and closing require only 3N-3 memory elements.     

Randomized consensus algorithms over large scale networks

Various randomized consensus algorithms have been proposed in the literature. In some case randomness is due to the choice of a randomized network communication protocol. In other cases, randomness is simply caused by the potential unpredictability of the environment in which the distributed consensus algorithm is implemented. Conditions ensuring the convergence of these algorithms have already been proposed in the literature. As far as the rate of convergence of such algorithms, two approaches can be proposed. One is based on a mean square analysis, while a second is based on the concept of Lyapunov exponent. In this paper, by some concentration results, we prove that the mean square convergence analysis is the right approach when the number of agents is large. Differently from the existing literature, in this paper we do not stick to average preserving algorithms. Instead, we allow to reach consensus at a point which may differ from the average of the initial states. The advantage of such algorithms is that they do not require bidirectional communication among agents and thus they apply to more general contexts. Moreover, in many important contexts it is possible to prove that the displacement from the initial average tends to zero, when the number of agents goes to infinity.     

Two recursive algorithms for computing the weight distribution ofcertain irreducible cyclic codes

Two recursive algorithms for computing the weight distributions of certain binary irreducible cyclic codes of length n in the so-called index 2 case are presented. The running times of these algorithms are smaller than O(log²r) where r=2^m and n is a factor of r-1     

Design of two-dimensional recursive filters with arbitrary support using quarter-plane design algorithms

In this note we examine reversible mappings between recursively computable two-dimensional digital filters with arbitrary regions of support and associated filters with quarter-plane support. These mappings allow quarter-plane design algorithms to be used to design more general recursive filters. This treatment applies equally to rectangularly sampled and hexagonally sampled systems.     

On 2-D recursive LMS algorithms using ARMA prediction for ADPCMencoding of images

A two-dimensional (2D) linear predictor which has an autoregressive moving average (ARMA) representation well as a bias term is adapted for adaptive differential pulse code modulation (ADPCM) encoding of nonnegative images. The predictor coefficients are updated by using a 2D recursive LMS (TRLMS) algorithm. A constraint on optimum values for the convergence factors and an updating algorithm based on the constraint are developed. The coefficient updating algorithm can be modified with a stability control factor. This realization can operate in real time and in the spatial domain. A comparison of three different types of predictors is made for real images. ARMA predictors show improved performance relative to an AR algorithm.     

Failure time analysis for LMS algorithms

Few results are available in the literature on failure time (in contrast with long time average) analysis of the least mean square (LMS) adaptive algorithms (filters). Such analysis is extremely important when failure of the algorithm could cause failure of the entire system in which they are employed. A system may fail upon the first occurrence of a large error (any value far from 0), or upon staying far from 0 for a period of time (a clump of large errors). We use a Poisson approximation to study excursions (failure) of the LMS algorithm and its three signed variants. The distribution and the mean of the first excursion are approximated with the mean and distribution of an exponential distribution. The number of excursions in n units of time is approximated by a Poisson distribution. We also approximate the mean of an excursion length (clump size). The approximations are derived asymptotically as the excursion-defining set converges to the empty set, and as the algorithm step size converges to 0