Past input reconstruction in fast least-squares algorithms

This paper solves the following problem: given the computed variables in a fast least-squares prediction algorithm, determine all past input sequences that would have given rise to the variables in question. This problem is motivated by the backward consistency approach to numerical stability in this algorithm class; the set of reachable variables in exact arithmetic is known to furnish a stability domain. Our problem is equivalent to a first- and second-order interpolation problem introduced by Mullis and Roberts (1976) and studied by others. Our solution differs in two respects. First, relations to classical interpolation theory are brought out, which allows us to parametrize all solutions. By-products of our formulation are correct necessary and sufficient conditions for the problem to be solvable, in contrast to previous works, whose claimed sufficient conditions are shown to fall short. Second, our solution obtains any valid past input as the impulse response of an appropriately constrained orthogonal filter, whose rotation parameters derive in a direct manner from the computed variables in a fast least-squares prediction algorithm. Formulas showing explicitly the form of all valid past inputs should facilitate the study of what past input perturbation is necessary to account for accumulated arithmetic errors in this algorithm class. This, in turn, is expected to have an impact in studying accuracy aspects in fast least-squares algorithms     

Efficient damping method for least-squares algorithms

A damping method for least-squares algorithms is reported. The method is based on an extension of existing damping techniques. Examples are given to illustrate typical performance improvement provided by the algorithm.     

Sliding window order-recursive least-squares algorithms

Order-recursive least-squares (ORLS) algorithms employing a sliding window (SW) are presented. The authors demonstrate that standard architectures that are well known for growing memory ORLS estimation, e.g., triangular array, lattice, and multichannel lattice, also apply to sliding window ORLS estimation. A specific SW-ORLS algorithm is the combination of two independent attributes: its global architecture and its local cell implementation. Various forms of local cell implementation based on efficient time-recursions of time-varying coefficients are discussed. In particular, the authors show that time and order updates of any order-recursive sliding window least-squares algorithm can be realized solely in terms of 3×3 hyperbolic Householder transformations (HHT). Finally, the authors present two HHT-based algorithms: the HHT triangular array algorithm and the HHT lattice algorithm     

Projected least-squares algorithms for constrained FIR filter design

Constrained finite-impulse response (FIR) filter design with time- and frequency-domain linear constraints can be generally transformed into a, or a series of, constrained least-squares problems, which can be generally reformulated as positive definite quadratic programming (QP) problems. This paper presents a novel algorithm referred to as a projected least-squares (PLS) algorithm for the positive definite QP problems. The PLS algorithm essentially projects the unconstrained (least-squares) minimization solution successively onto the boundaries of active constraints that are identified by an active-set strategy. The PLS algorithm has been applied to the constrained least-squares design of FIR filters directly, and to the constrained Chebyshev design of FIR filters in an iterative fashion. The PLS algorithm is compared with the most widely used interior-point methods and an active-set method through design examples of low-pass filters with specified passband and stopband ripples, Nyquist filter constraints and step response constraints. All these examples demonstrate the high efficiency of the PLS algorithm.     

A fast least-squares algorithm for linearly constrained adaptivefiltering

An extension of the field of fast least-squares techniques is presented. It is shown that the adaptation gain, which is updated with a number of operations proportional to the number of transversal filter coefficients, can be used to update the coefficients of a linearly constrained adaptive filter. An algorithm that is robust to round-off errors is derived. It is general and flexible. It can handle multiple constraints and multichannel signals. Its performance is illustrated by simulations and compared with the classical LMS-based Frost (1972) algorithm     

采用简化SIFT算法实现快速图像匹配

SIFT(Scale Invariant Feature Transform)算子因其良好的尺度、旋转、光照等不变特性而广泛应用于图像匹配中,但用128维向量来表征每个特征点降低了算法的实时性。为了提高匹配速度,介绍了一种基于SIFT的简化算法(SSIFT),采用基于圆形窗口的12维向量有效地表示一个特征点。实验结果显示,算法在保持较好匹配率的同时能降低时间复杂度,适合运用在对实时性要求较高的场合。     

Efficient and fast iterative reweighted least-squares nonrecursivefilters

An efficient and fast technique for designing L_p approximation filters using the iterative reweighted least-squares (IRLS) algorithm is proposed. This technique introduces an extra frequency response which implicitly includes the weighting function such that the filter coefficients can be obtained with O(N²) complexity     

Simplified Newton-type adaptive estimation algorithms

A new adaptive estimation algorithm is presented. It is the result of a combination of the LMS and the fast Newton transversal filters (FNTF) class. The main characteristic of the proposed algorithm is its improved convergence rate as compared to LMS, for cases where it is known that LMS behaves poorly. This improved characteristic is achieved in expense of a slight increase in the computational complexity while the overall algorithmic structure is very simple (LMS type). The proposed algorithm seems also to compare relatively well against RLS and FNTF     

Two algorithms for fast approximate subspace tracking

New fast algorithms are presented for tracking singular values, singular vectors, and the dimension of a signal subspace through an overlapping sequence of data matrices. The basic algorithm is called fast approximate subspace tracking (FAST). The algorithm is derived for the special case in which the matrix is changed by deleting the oldest column, shifting the remaining columns to the left, and adding a new column on the right. A second algorithm (FAST2) is specified by modifying FAST to trade reduced accuracy for higher speed. The speed and accuracy are compared with the PL algorithm, the PAST and PASTd algorithms, and the FST algorithm. An extension to multicolumn updates for the FAST algorithm is also discussed     

On fast address-lookup algorithms

The growth of the Internet and its acceptance has sparkled keen interest in the research community in respect to many apparent scaling problems for a large infrastructure based on IP technology. A self-contained problem of considerable practical and theoretical interest is the longest-prefix lookup operation, perceived as one of the decisive bottlenecks. Several novel approaches have been proposed to speed up this operation that promise to scale forwarding technology into gigabit speeds. This paper surveys these new lookup algorithms and classifies them based on applied techniques, accompanied by a set of practical requirements that are critical to the design of high-speed routing devices. We also propose several new algorithms to provide lookup capability at gigabit speeds. In particular, we show the theoretical limitations of routing table size and show that one of our new algorithms is almost optimal, while requiring only a small number of memory accesses to perform each address lookup     

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     

On MLSE algorithms for unknown fast time-varying channels

We consider maximum-likelihood sequence estimation (MLSE) algorithms for unknown, time-varying intersymbol interference communication channels. We assume a statistical channel model, and marginalize over model parameters to derive expectation-maximization (EM) algorithms for both time-independent Gaussian and Gauss-Markov models, and we contrast these with direct MLSE and computationally efficient per-survivor processing implementations. We identify a general concern associated with the convergence of EM-based discrete parameter (e.g., symbol) estimators.     

On fast Hartley transform algorithms

This letter discusses the equivalence between the pre- and post-permutation algorithms for the fast Hartley transform (FHT). Some improvements are made to two recently published FHT programs.     

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     

Recursive least-squares algorithms of modified Gram-Schmidt typefor parallel weight extraction

This paper presents some new algorithms for parallel weight extraction in the recursive least-squares (RLS) estimation based on the modified Gram-Schmidt (MGS) method. These are the counterparts of the algorithms using an inverse QR decomposition based on the Givens rotations and do not contain the square root operation. Systolic-array implementations of the algorithms are considered on a 2-D rhombic array. Simulation results are also presented to compare the finite word-length effect of these new algorithms and existing algorithms     

Simplified frame structure for MMSE-based fast burstsynchronisation in OFDM systems

A simplified frame structure is proposed for fast burst synchronisation in orthogonal frequency division multiplexing systems. A simpler and shorter synchronisation symbol and minimum mean square error algorithm is exploited to estimate the frame starting position. The performance of the proposed frame is confirmed by simulation for QPSK systems     

Two fast nearest neighbor searching algorithms for image vectorquantization

In this paper, two efficient codebook searching algorithms for vector quantization (VQ) are presented. The first fast search algorithm utilizes the compactness property of signal energy on transform domain and the geometrical relations between the input vector and every codevector to eliminate those codevectors that have no chance to be the closest codeword of the input vector. It achieves a full search equivalent performance. As compared with other fast methods of the same kind, this algorithm requires the fewest multiplications and the least total times of distortion measurements. Then, a suboptimal searching method, which sacrifices the reconstructed signal quality to speed up the search of nearest neighbor, is presented. This algorithm performs the search process on predefined small subcodebooks instead of the whole codebook for the closest codevector. Experimental results show that this method not only needs less CPU time to encode an image but also encounters less loss of reconstructed signal quality than tree-structured VQ does     

Vector-extrapolated fast maximum likelihood estimation algorithms for emission tomography

A new class of fast maximum-likelihood estimation (MLE) algorithms for emission computed tomography (ECT) is developed. In these cyclic iterative algorithms, vector extrapolation techniques are integrated with the iterations in gradient-based MLE algorithms, with the objective of accelerating the convergence of the base iterations. This results in a substantial reduction in the effective number of base iterations required for obtaining an emission density estimate of specified quality. The mathematical theory behind the minimal polynomial and reduced rank vector extrapolation techniques, in the context of emission tomography, is presented. These extrapolation techniques are implemented in a positron emission tomography system. The new algorithms are evaluated using computer experiments, with measurements taken from simulated phantoms. It is shown that, with minimal additional computations, the proposed approach results in substantial improvement in reconstruction.     

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     

Filter design and comparison for two fast CWT algorithms

The continuous wavelet transform (CWT) is a powerful technique for signal analysis. Direct CWT computation by FFT requires O(N log₂ N) operations per scale, where N is the data length. The a trous algorithm and the Shensa (1992) algorithm are two fast methods to compute CWT recursively that require only O(N) operations per scale. Both of them can be described by the multiresolution analysis (MRA) structure but with different MRA filters. This paper proposes methods to design the MRA filters of the two algorithms to improve their accuracy on CWT computation. We begin with the formulation of the CWT computation error using the MRA structure. The MRA filters of the two algorithms are then designed to minimize the error. In either algorithm, both the lowpass and bandpass MRA filters can be optimized. The a trous algorithm has closed-form solutions for the two filters. The Shensa algorithm, on the other hand, has an analytic solution for the bandpass filter only. Finding the optimum lowpass filter requires a multidimensional numerical search. Simulation studies show that by using the proposed optimum filters, the Shensa algorithm, in general, outperforms the a trous algorithm