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     

Multiphase systolic algorithms for spectral decomposition

The authors propose two multiphase systolic algorithms to solve the spectral decomposition problem based on the QR algorithm. The spectral decomposition is one of the most computationally intensive modern signal processing operations. While the QR algorithm is well known to be an effective method to solve the eigenvalue problem, there is still no single systolic array architecture that can compute the unitary Q matrix readily and perform the QR algorithm efficiently. Previous methods using the QR algorithm had communication problems among different architectures. Two arrays, a triangular and a rectangular, are presented to implement the multiphase algorithms. Details on these multiphase operations of the QR algorithm as well as architectural consequences and performance evaluation are discussed. Efficient fault-tolerant schemes for these multiphase operations are also considered     

Constrained least squares in adaptive, imperfect arrays

Two new constrained deterministic least-squares algorithms are presented which are capable of enabling a narrow-band zero-order generalized sidelobe canceller (SLC), in the presence of array imperfections, to null out jammers while preserving the friendly look-direction signal with minimal a priori knowledge of the signal environment. The algorithms are capable of solving deterministic least-squares optimization problems subject to an equality constraint in an iterative, adaptive manner by imposing a `soft' constraint via the quadratic penalty function optimization method. The first algorithm is based on the matrix inversion lemma while the second is obtained by means of QR-decomposition using new three-dimensional Givens (1958) rotations and implemented with a systolic array architecture. These new constrained algorithms improve system performance when an artificial injection of a receiver noise vector is introduced     

Direction-of-arrival estimation using rank revealing QRfactorization

The authors describe a novel technique for direction-of-arrival estimation based on computing a permutation matrix E and a QR factorization RE=HB of the permuted covariance matrix R, such that a possible rank deficiency of R is revealed in the triangular factor B having a minimum norm lower right block. A subset of the columns of the orthogonal matrix, H, is shown to be orthogonal to the direction vectors of sources and hence can be used to estimate their bearings. The cost of this algorithm is only slightly more than that of one QR factorization, but is much lower than that of an eigen-decomposition. Simulation results are included to show that the proposed method performs nearly as well as MUSIC in terms of signal resolution, bias, and variance of the estimated bearings     

In the optimum design of the block adaptive FIR digital filter

A general optimum block adaptive (GOBA) algorithm for adaptive FIR (finite impulse response) filtering is presented. In this algorithm, the correction terms for the filter coefficients in each block, instead of the convergence factors, are optimized in a least squares sense. There are no constraints on the block length L and the filter tap number N. It is shown that the GOBA algorithm is reduced to the normalized LMS algorithm when L⩾N. The convergence of the GOBA algorithm can be assured if the correlation matrix of the input signal is positive definite. Computer simulations based on an efficient computing procedure confirm that the GOBA algorithm achieves faster convergence with slightly degraded convergence accuracy in stationary environments and better weight tracking capability in nonstationary environments as compared to existing block adaptive algorithms with no constraints on L and N     

Fast algorithm and architecture for constrained adaptive side-lobecancellation

An efficient implementation of auxiliary constraints for a concurrent-block least-squares adaptive side-lobe canceler is described. A QR decomposition of the auxiliary data matrix is computed, and this information is sent to one or more main beam processors, where the constraints are applied using blocking matrices and the individual residuals are computed. Structured blocking matrices are used to derive a fast algorithm and architecture for constrained main beam processing. This approach reduces the operation count of this phase of the processing from O(n³) to O(n ²), where n is the number of auxiliary sensors     

A fast quasi-Newton adaptive filtering algorithm

The convergence rate of an adaptive system is closely related to its ability to track a time-varying optimum. Basic adaptive filtering algorithms give poor convergence performance when the input to the adaptive system is colored. More sophisticated algorithms which converge very rapidly regardless of the input spectrum algorithms typically require O(N²) computation, where N is the order of the adaptive filter, a significant disadvantage for real-time applications. Also, many of these algorithms behave poorly in finite-precision implementation. An adaptive filtering algorithm is introduced which employs a quasi-Newton approach to give rapid convergence even with colored inputs. The algorithm achieves an overall computational requirement of O(N) and appears to be quite robust in finite-precision implementations     

Recursive algorithms for calculating the scattering from Nstrips or patches

Using the definition of recursive relations for the reflection operator for N strips or patches, two easily programmable recursive algorithms are developed to calculate the electromagnetic scattering by N strips or patches. One algorithm is for arbitrary excitation, and the other is for a fixed excitation. The recursive algorithms require the inversion of small matrices at each stage and hence are suitable for programming on smaller computers. If the N strips or patches are identical and equally spaced, symmetry can be exploited to speed up the algorithms. A program was developed to calculate scattering by N strips, and the result is shown to converge to scattering by a large strip when the N strips are contiguous     

Full Newton and constraint methods for semilinear signal modeling

The authors derive an expression for the Hessian matrix of the variable projection functional (VPF) and implement the Hessian using QR factorization. This is incorporated into a full Newton variable projection (FNVP) algorithm for estimating parameters in semilinear signals. They introduce a deflation technique for constraining the VPF to contain known basis vectors. For modeling exponential signals, the computational cost of the FNVP algorithm is shown to vary linearly with N, the size of the data vector, while other algorithms vary as N² or N log ₂ N     

A unified algebraic transformation approach for parallel recursiveand adaptive filtering and SVD algorithms

In this paper, a unified algebraic transformation approach is presented for designing parallel recursive and adaptive digital filters and singular value decomposition (SVD) algorithms. The approach is based on the explorations of some algebraic properties of the target algorithms' representations. Several typical modern digital signal processing examples are presented to illustrate the applications of the technique. They include the cascaded orthogonal recursive digital filter, the Givens rotation-based adaptive inverse QR algorithm for channel equalization, and the QR decomposition-based SVD algorithms. All three examples exhibit similar throughput constraints. There exist long feedback loops in the algorithms' signal flow graph representation, and the critical path is proportional to the size of the problem. Applying the proposed algebraic transformation techniques, parallel architectures are obtained for all three examples. For cascade orthogonal recursive filter, retiming transformation and orthogonal matrix decompositions (or pseudo-commutativity) are applied to obtain parallel filter architectures with critical path of five Givens rotations. For adaptive inverse QR algorithm, the commutativity and associativity of the matrix multiplications are applied to obtain parallel architectures with critical path of either four Givens rotations or three Givens rotations plus two multiply-add operations, whichever turns out to be larger. For SVD algorithms, retiming and associativity of the matrix multiplications are applied to derive parallel architectures with critical path of eight Givens rotations. The critical paths of all parallel architectures are independent of the problem size as compared with being proportional to the problem size in the original sequential algorithms. Parallelism is achieved at the expense of slight increase (or the same for the SVD case) in the algorithms' computational complexity     

A sliding window update for the basis matrix of the QRdecomposition

A method of updating the unitary basis matrix for QR decomposition by applying a sliding window to the input data is presented. The basis matrix update allows the recursive update to be applied to problems which require the tracking of a basis set, and the sliding-window feature gives this alternative update a superior nonstationary performance characteristic     

Constrained adaptive filtering algorithms: asymptotic convergenceproperties for dependent data

The convergence properties of constrained adaptive filtering algorithms are established. The constraint is in the form of a bounded set in which the filter's coefficients must lie. A recursive procedure that converges to the deterministic solution of the constrained linear mean-square estimation problem is obtained, using an appropriate contraction mapping. The recursion is used to derive the adaptive algorithm for the filter coefficients. Bounds on the mean-square error of the coefficients. Bounds on the mean-square error of the estimates of the filter coefficients and on the excess error of the input signal estimate are derived for processes that are either strong mixing or asymptotically uncorrelated. The algorithms use a moving window of size n on the data from one adaptation step to the next. However, tighter bounds can be obtained when a skipped sampling mechanism is used     

A fast recursive least squares adaptive second order Volterrafilter and its performance analysis

A fast, recursive least squares (RLS) adaptive nonlinear filter modeled using a second-order Volterra series expansion is presented. The structure uses the ideas of fast RLS multichannel filters, and has a computational complexity of O(N³) multiplications, where N-1 represents the memory span in number of samples of the nonlinear system model. A theoretical performance analysis of its steady-state behaviour in both stationary and nonstationary environments is presented. The analysis shows that, when the input is zero mean and Gaussian distributed, and the adaptive filter is operating in a stationary environment, the steady-state excess mean-squared error due to the coefficient noise vector is independent of the statistics of the input signal. The results of several simulation experiments show that the filter performs well in a variety of situations. The steady-state behaviour predicted by the analysis is in very good agreement with the experimental results     

Superlattice/superladder computational organization for linearprediction and optimal FIR filtering

A family of computational organizations for the solution of the Toeplitz systems appearing in the digital signal processing (DSP) techniques of linear prediction and optimal FIR filtering is presented. All these organizations are based on a structure called superlattice which governs the Toeplitz solving procedure and provides many possible implementations. Algorithmic schemes for the implementation of these organizations, suitable for single-processor and multiprocessor environments, are developed. Among them there are order recursive algorithms, parallel-algorithms of O(p) complexity which use O(p) processing elements, and partitioned-parallel algorithms. The last can make full use of any number of available, parallel-working processors, independently of the system order. Superlattice-type algorithms are described for many Toeplitz-based problems     

Stable and efficient lattice algorithms for adaptive IIR filtering

Previous attempts at applying lattice structures to adaptive infinite-impulse-response (IIR) filtering have met with gradient computations of O(N²) complexity. To overcome this computational burden, two new lattice-based algorithms are proposed for adaptive IIR filtering and system identification, with both algorithms of O(N) complexity. The first algorithm is a reinterpretation of the Steiglitz-McBride method (1965), while the second is a variation on the output error method. State space models are employed to make the derivations transparent, and the methods can be extended to other parameterizations if desired. The set of possible stationary points of the algorithms is shown to be consistent with the convergent points obtained from the direct-form versions of the Steiglitz-McBride and output error methods, whose properties are well studied. The derived algorithms are as computationally efficient as existing direct-form based algorithms, while overcoming the stability problems associated with time-varying direct-form filters     

Adaptive recovery of a chirped sinusoid in noise. I. Performance ofthe RLS algorithm

The authors study the ability of the exponentially weighted recursive least square (RLS) algorithm to track a complex chirped exponential signal buried in additive white Gaussian noise (power P _n). The signal is a sinusoid whose frequency is drifting at a constant rate Ψ. lt is recovered using an M-tap adaptive predictor. Five principal aspects of the study are presented: the methodology of the analysis; proof of the quasi-deterministic nature of the data-covariance estimate R(k); a new analysis of RLS for an inverse system modeling problem; a new analysis of RLS for a deterministic time-varying model for the optimum filter; and an evaluation of the residual output mean-square error (MSE) resulting from the nonoptimality of the adaptive predictor (the misadjustment) in terms of the forgetting rate (β) of the RLS algorithm. It is shown that the misadjustment is dominated by a lag term of order β^-2 and a noise term of order β. Thus, a value β_opt exists which yields a minimum misadjustment. It is proved that β_opt={(M+1)ρΨ²} ^1/3, and the minimum misadjustment is equal to (3/4)P_n(M+1)β_opt, where ρ is the input signal-to-noise ratio (SNR)     

Adaptive set-membership identification in O(m)time for linear-in-parameters models

Some fundamental contributions to the theory and applicability of optimal bounding ellipsoid (OBE) algorithms for signal processing are described. All reported OBE algorithms are placed in a general framework that demonstrates the relationship between the set-membership principles and least square error identification. Within this framework, flexible measures for adding explicit adaptation capability are formulated and demonstrated through simulation. Computational complexity analysis of OBE algorithms reveals that they are of O(m²) complexity per data sample with m the number of parameters identified. Two very different approaches are described for rendering a specific OBE algorithm, the set-membership weighted recursive least squares algorithm, of O(m) complexity. The first approach involves an algorithmic solution in which a suboptimal test for innovation is employed. The performance is demonstrated through simulation. The second method is an architectural approach in which complexity is reduced through parallel competition     

Schur type algorithms for spatial LS estimation with highlypipelined architectures

A family of Schur-type spatial least-squares algorithms is presented for solving the spatial LS estimation problem, in which the correlation matrix is neither Toeplitz nor near-Toeplitz, by order recursion. Normalized spatial Levinson- and Schur-type algorithms are also derived. Highly pipelined architectures are designed to realize these recursions. The reflection coefficients are first computed using the spatial Schur type recursions. Then, the forward and backward filter parameters are calculated by the spatial Levinson-type recursions. A pyramid systolic array is demonstrated to calculate not only the filter parameters but also the LDU decomposition of the inverse cross-correlation matrix at every clock phase. This pyramid array can be mapped onto a two-dimensional systolic array which has a simpler structure. A square systolic array is developed to implement the Levinson- and Schur-type temporal recursive LS (RLS) algorithms. A highly concurrent architecture which exploits the parallelism of the spatial Schur-type recursions is illustrated to perform the LDU decomposition of the cross-correlation matrix     

A stable and distortion-free IIR echo and howling canceler

The authors propose a configuration for an infinite impulse response (IIR) adaptive echo and howling canceller, which consists of a two-channel maximum entropy lattice filter and its inverse filter. The echo is canceled by the adaptive lattice filter, while the signal distortion is eliminated by the inverse lattice. With stability guaranteed without the necessity of testing, the structure costs O (N) multiplications per sampling period. The algorithm can also be greatly simplified for white input cases     

A unified fast recursive algorithm for data shuffling in variousorders

Data shuffling in a particular order is frequently required in signal processing applications. The authors present fast recursive algorithms, of order O(N), for shuffling a data sequence in various orders, e.g. bit reversed, Gray code, and other related orders, under a unified framework. These algorithms are computationally efficient in that every permutation index is essentially computed by a single logical or arithmetic operation between a previous index and a proper offset. The proposed algorithms can be used for the fast Fourier transform, fast Hartley transform, and mutual conversion among three typical forms of the Walsh transform