Multichannel recursive least squares adaptive filtering without adesired signal

The author presents a pair of adaptive QR decomposition-based algorithms for the adaptive mixed filter in which no desired signal is available, but the signal-to-data cross-correlation vector is known. The algorithms are derived by formulating the recursive mixed filter as a least-squares problem and then applying orthogonal QR-based techniques in its solution. This leads to algorithms with the performance, numerical, and structural advantages of the RLS/ QR algorithm, but without the requirement of a desired signal. Both Givens and square-root-free Givens rotations are used in implementing the recursive QR decomposition. Because of their structural regularity, the algorithms are easily implemented by triangular systolic array structures. Simulations show that these algorithms require fewer computations and less precision than recursive sample matrix inversion approaches     

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     

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     

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     

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     

The generalized eigenproblem: pole-zero computation

A modification-decomposition (MD) method is used to compute linear system transfer function poles and zeros by transforming an N-dimensional generalized eigenvalue problem to an M-dimensional standard eigenvalue problem with M⩾ r, where r is the lesser of the ranks of the dynamic or nondynamic component matrix of the system. Hence, network eigenvalue problems normally solved by applying the QZ algorithm directly, or after deflation preprocessing, are solvable with the more efficient QR algorithm. It is shown that the flop (floating-point operations) count for MD-QR algorithms is always less than the flop count for the most efficient deflation-QZ algorithms. For r⩽N, the MD-QR algorithms are exceptionally efficient. Using a parameter matrix decomposition of the dynamic or nondynamic component matrix, the MD method gives physical insight, and it provides a general proof of manifold constraints relating network time constants and poles and zeros. From these relations, accurate dominant and subdominant pole approximations are derived. A general eigenvalue sensitivity formula and a very flexible method for computing eigenvectors is developed and applied to pole sensitivity computation     

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     

Solution to the problem of instability in banded Toeplitz solvers

The author presents a numerically stable approach to solving banded Toeplitz systems of n linear equations. The algorithm is fast in that it requires only O(nq) operations, where q is the bandwidth of the matrix. An earlier version of the banded Toeplitz algorithm presented in the literature suffers from numerical instability. The author solves the instability problem by developing numerically stable alternatives to the back substitution process. These new algorithms have roughly the same number of calculations as simple back substitution, O(nq), and therefore can be used effectively in place of back substitution. The stabilization procedures described have been used to find accurate solutions to systems of order several thousand     

Parallel VLSI matrix pencil algorithm for high resolution directionfinding

Algorithms to find the directions of arrival (DOAs) of multiple signals from measurements on an array of antenna doublets (ESPRIT method) and their parallel VLSI implementation are discussed. In particular, algorithms that allow large-scale pipelining and use only robust, unitary transformations are identified. This problem is solved by a matrix pencil approach in which the generalized eigenvalues of a pair of data matrices are determined. A modified Stewart Jacobi approach is used for which convergence is improved and parameter computations are simplified. The resulting architecture is a two-layer Jacobi array that can handle all the subproblems: two QR factorizations, two SVDs, and a single generalized Schur decomposition. The mapping of the subproblems on a single parallel array of CORDIC processors is considered     

A system for systolic modules for the MUSIC algorithm

The authors believe that special-purpose architectures for digital signal processing (DSP) real-time applications will use closely coupled processing elements as array processor modules to implement the various portions of the new algorithms, and several such modules will cooperate in a pipelined manner to implement complete algorithms. Such an architecture, based upon systolic modules, for the MUSIC algorithm is presented. The architecture is suitable for VLSI implementation. The throughput of the pipelined approach is O(N), whereas the sequential approach is O(N³)     

Restoring a δ-pulse train by spectral fitting

The problem of restoring a δ-pulse train h(t ) from its bandpass filtered and noise-corrupted version is considered. A spectral fitting approach is described which fits terms of the form ρ_ke exp(-jωτk) to the estimated spectrum of h(t). This fitting problem can be efficiently solved using the FFT algorithm. The error in the estimated pulse positions is discussed by analyzing the fluctuation of the peak position of the cross correlation function. Computer simulation results are presented which indicate the validity of these calculations and analyses     

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     

Quadtree-structured recursive plane decomposition coding of images

The approximation of two-dimensional highly correlated grey value functions can be performed using a linear model of the type f( x, y)=a+bx+cy. The set of plane parameters (PPs) [a, b, c] can be determined in the least squares sense for a block of size N×N pixels, for example. Starting with a block size of 2×2 pixels, it is shown that the PPs obey a recursive law such that the PPs of a 2N×2N block can be computed recursively when only the PPs of the four adjacent subblocks of size N×N in the lower decomposition level are known. This concept of recursive plane decomposition (RPD) is embedded in a quadtree data structure to obtain a new variable block size image coding algorithm that offers a high performance at a low computational cost. Extensive comparisons to other state-of-the-art image coding algorithms are reported     

An updating algorithm for subspace tracking

In certain signal processing applications it is required to compute the null space of a matrix whose rows are samples of a signal with p components. The usual tool for doing this is the singular value decomposition. However, the singular value decomposition has the drawback that it requires O(p³) operations to recompute when a new sample arrives. It is shown that a different decomposition, called the URV decomposition, is equally effective in exhibiting the null space and can be updated in O( p²) time. The updating technique can be run on a linear array of p processors in O(p) time     

Systolic arrays for the discrete Hartley transform

Recently, R.N. Bracewell (1983) introduced the discrete Hartley transform (DHT) as an alternative to the discrete Fourier transform (DFT). Two linear systolic array models for the (DHT) are derived. One model requires O(2N-1) in the computational phase and O(N) in the preloading phase. The other model requires O(2N-1) in the computational phase and O(N) in the output phase. A square systolic array for two-dimensional DHT is also constructed by combining the individual advantages of each model. The CORDIC algorithm is proposed as an alternative to conventional multipliers. To speed up the systolic array, two-level pipelining with CORDIC is also possible     

A geometric approach to root finding in GT(qm)

The problem of finding roots in F of polynomials in F [x] for F=GF(q^m), where q is a prime or prime power and m is a positive integer greater than 1 is considered. The problem is analyzed by making use of the finite affine geometry AG(m,q). A new method is proposed for finding roots of polynomials over finite extension fields. It is more efficient than previous algorithms when the degree of the polynomial whose roots are to be found is less than dimension m of the extension field. Implementation of the algorithm can be enhanced in cases in which optimal normal bases for the coefficient field are available     

Delay analysis of continuous bit rate traffic over an ATM network

A packet multiplexer is modeled for continuous bit rate (CBR) traffic in an asynchronous transfer mode (ATM) network as an nD/D/1 queue. The efficiencies of various algorithms for finding the delay distribution are compared. In particular, a new algorithm is proposed whose time complexity is O(n²), where n is the number of voice sources being multiplexed. The use of the central limit theorem can reduce the time complexity to O(n) for large n . An asymptotic formula is found whose time complexity is independent of n and it works well (for practical purposes) over a wide range of parameter values. The authors examine and comment on the use of the M/D/1 results as an approximation. In addition to comparing the performances of these algorithms, they show that the buffer requirements for such a queue are significantly less than the theoretical maximum (even when the requirement on the call disruption probability is very low). This result has important implications in the design of buffer size. The buffer requirement is relatively insensitive to the design criterion (call disruption probability)     

Distributed cochannel interference control in cellular radiosystems

Distributed power control algorithms that use only the carrier-to-interference ratios (C/I ratios) in those links actually in use are investigated. An algorithm that successfully approximates the behavior of the best known algorithms is proposed. The algorithm involves a novel distributed C/I-balancing scheme. Numerical results show that capacity gains on the order of 3-4 times can be reached also with these distributed schemes. Further, the effects of imperfect C/I estimates due to noise vehicle mobility, and fast multipath fading are considered. Results show that the balancing procedure is very robust to measurement noise, in particular if C/I requirements are low or moderate. However, for required high C/I levels or for a rapidly changing path loss matrix, convergence may be too slow to achieve substantial capacity improvements     

New array codes for multiple phased burst correction

An optimal family of array codes over GF(q) for correcting multiple phased burst errors and erasures, where each phased burst corresponds to an erroneous or erased column in a code array, is introduced. As for erasures, these array codes have an efficient decoding algorithm which avoids multiplications (or divisions) over extension fields, replacing these operations with cyclic shifts of vectors over GF(q). The erasure decoding algorithm can be adapted easily to handle single column errors as well. The codes are characterized geometrically by means of parity constraints along certain diagonal lines in each code array, thus generalizing a previously known construction for the special case of two erasures. Algebraically, they can be interpreted as Reed-Solomon codes. When q is primitive in GF(q), the resulting codes become (conventional) Reed-Solomon codes of length P over GF(q^p-1), in which case the new erasure decoding technique can be incorporated into the Berlekamp-Massey algorithm, yielding a faster way to compute the values of any prescribed number of errors