A family of adaptive filter algorithms with decorrelatingproperties

Although the normalized least mean square (NLMS) algorithm is robust, it suffers from low convergence speed if driven by highly correlated input signals. One method presented to overcome this problem is the Ozeki/Umeda (1984) affine projection (AP) algorithm. The algorithm applies update directions that are orthogonal to the last P input vectors and thus allows decorrelation of an AR(P) input process, speeding up the convergence. This article presents a simple approach to show this property, which furthermore leads to the construction of new algorithms that can handle other kinds of correlations such as MA and ARMA processes. A statistical analysis is presented for this family of algorithms. Similar to the AP algorithm, these algorithms also suffer a possible increase in the noise energy caused by their pre-whitening filters     

Projected gradient descent based on soft thresholding in matrix completion

Matrix completion is the extension of compressed sensing. In compressed sensing, we solve the underdetermined equations using sparsity prior of the unknown signals. However, in matrix com- pletion, we solve the underdetermined equations based on sparsity prior in singular values set of the unknown matrix, which also calls low-rank prior of the unknown matrix. This paper firstly introduces basic concept of matrix completion, analyses the matrix suitably used in matrix completion, and shows that such matrix should satisfy two conditions： low rank and incoherence property. Then the paper provides three reconstruction algorithms commonly used in matrix completion： singular value thresholding algorithm, singular value projection, and atomic decomposition for minimum rank ap- proximation, puts forward their shortcoming to know the rank of original matrix. The Projected Gradient Descent based on Soft Thresholding （STPGD）, proposed in this paper predicts the rank of unknown matrix using soft thresholding, and iteratives based on projected gradient descent, thus it could estimate the rank of unknown matrix exactly with low computational complexity, this is verified by numerical experiments. We also analyze the convergence and computational complexity of the STPGD algorithm, point out this algorithm is guaranteed to converge, and analyse the number of it- erations needed to reach reconstruction error. Compared the computational complexity of the STPGD algorithm to other algorithms, we draw the conclusion that the STPGD algorithm not only reduces the computational complexity, but also improves the precision of the reconstruction solution.     

A set of algorithms linking NLMS and block RLS algorithms

This paper describes a set of block processing algorithms which contains as extremal cases the normalized least mean squares (NLMS) and the block recursive least squares (BRLS) algorithms. All these algorithms use small block lengths, thus allowing easy implementation and small input-output delay. It is shown that these algorithms require a lower number of arithmetic operations than the classical least mean squares (LMS) algorithm, while converging much faster. A precise evaluation of the arithmetic complexity is provided, and the adaptive behavior of the algorithm is analyzed. Simulations illustrate that the tracking characteristics of the new algorithm are also improved compared to those of the NLMS algorithm. The conclusions of the theoretical analysis are checked by simulations, illustrating that, even in the case where noise is added to the reference signal, the proposed algorithm allows altogether a faster convergence and a lower residual error than the NLMS algorithm. Finally, a sample-by-sample version of this algorithm is outlined, which is the link between the NLMS and recursive least squares (RLS) algorithms     

An Affine Projection Sign Algorithm Robust Against Impulsive Interferences

A new affine projection sign algorithm (APSA) is proposed, which is robust against non-Gaussian impulsive interferences and has fast convergence. The conventional affine projection algorithm (APA) converges fast at a high cost in terms of computational complexity and it also suffers performance degradation in the presence of impulsive interferences. The family of sign algorithms (SAs) stands out due to its low complexity and robustness against impulsive noise. The proposed APSA combines the benefits of the APA and SA by updating its weight vector according to the $L_{1}$-norm optimization criterion while using multiple projections. The features of the APA and the $L_{1}$-norm minimization guarantee the APSA an excellent candidate for combatting impulsive interference and speeding up the convergence rate for colored inputs at a low computational complexity. Simulations in a system identification context show that the proposed APSA outperforms the normalized least-mean-square (NLMS) algorithm, APA, and normalized sign algorithm (NSA) in terms of convergence rate and steady-state error. The robustness of the APSA against impulsive interference is also demonstrated.      

Low-Complexity Non-Uniform Penalized Affine Projection Algorithm for Sparse System Identification

In this paper, an improved sparse-aware affine projection (AP) algorithm for sparse system identification is proposed and investigated. The proposed sparse AP algorithm is realized by integrating a non-uniform norm constraint into the cost function of the conventional AP algorithm, which can provide a zero attracting on the filter coefficients according to the value of each filter coefficient. Low complexity is obtained by using a linear function instead of the reweighting term in the modified AP algorithm to further improve the performance of the proposed sparse AP algorithm. The simulation results demonstrate that the proposed sparse AP algorithm outperforms the conventional AP and previously reported sparse-aware AP algorithms in terms of both convergence speed and steady-state error when the system is sparse.     

Design of IIR digital filters in the complex domain by transforming the desired response

In this paper, we present a new design method of infinite impulse response (IIR) digital filters with quasi-equiripple absolute error in the complex domain. This method is based on solving a least squares solution iteratively. At each iteration, the desired response for the least squares approximation is transformed to have equiripple error. This algorithm is efficient because there is no need for any initial value or complex optimization algorithm. By this method, a quasi-equiripple solution is obtained very quickly with less computational complexity. Moreover, by multiplying an arbitrary weighting function on the desired responses of passband and stopband, respectively, the error at the passband and stopband can be controlled. Finally, we show some examples to validate the proposed method.     

Analysis of gradient algorithms for TLS-based adaptive IIR filters

Steepest descent gradient algorithms for unbiased equation error adaptive infinite impulse response (IIR) filtering are analyzed collectively for both the total least squares and mixed least squares-total least squares framework. These algorithms have a monic normalization that allows for a direct filtering implementation. We show that the algorithms converge to the desired filter coefficient vector. We achieve the convergence result by analyzing the stability of the equilibrium points and demonstrate that only the desired solution is locally stable. Additionally, we describe a region of initialization under which the algorithm converges to the desired solution. We derive the results using interlacing relationships between the eigenvalues of the data correlation matrices and their respective Schur complements. Finally, we illustrate the performance of these new approaches through simulation.     

Variable Step Size Affine Projection Algorithm for Adaptive Multiuser DS-CDMA MMSE Receiver

In this paper, we consider the use of affine projection algorithm (APA) for interference suppression in direct sequence code-division multiple-access (DS-CDMA) system. We first derive the multiuser fixed step-size APA (FSS-APA) algorithm. The computational complexity offered by the APA algorithm is linear in terms of the number of taps with additional terms of O (L ²) and a matrix inversion of dimension L, where L is known as the order of the filter. The value of L is chosen very small as compared to the number of filter-taps N _T . We next propose a novel variable step-size APA (VSS-APA) algorithm, which further improves the performance of the FSS-APA algorithm with very small increase in computational complexity as compared to the FSS-APA. It is demonstrated that the performance of the APA based minimum mean-square error (MMSE) receivers is far superior to that of the normalized least-mean-square (NLMS) based receivers. Though, the recursive-least-square (RLS) algorithm based adaptive receivers offer better performance but at the cost of much higher computational complexity.     

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     

基于可变阶数的集员滤波仿射投影算法

为了解决传统集员滤波仿射投影(SM-AP)算法收敛速度与稳态失调和计量复杂度之间的矛盾,提出一种新的数据选择性仿射投影算法。此算法在传统SM-AP算法的基础上,引入可变阶数(也称数据重用因子),称为基于可变数据重用因子的集员滤波仿射投影(VDRF-SM-AP)算法。通过利用步长提供的信息,此算法可以自动地分配数据重用因子,实现了在初始阶段数据重用因子大,收敛后数据重用因子小的目标,从而既保证了收敛速度又降低了稳态失调。通过理论分析和仿真验证,新算法的整体复杂度比其他传统的SM-AP算法低很多,同时保留了传统的SM-AP算法的快速收敛特性,但是却能达到更小的稳态失调。     

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     

Rapid computation of the continuous wavelet transform by obliqueprojections

We introduce a fast simple method for computing the real continuous wavelet transform (CWT). The approach has the following attractive features: it achieves O(N) complexity per scale, the filter coefficients can be analytically obtained by a simple integration, and the algorithm is faster than a least squares approach with negligible loss in accuracy. Our method is to use P wavelets per octave and to approximate them with their oblique projection onto a space defined by a compactly supported scaling function. The wavelet templates are expanded to larger sizes (octaves) using the two-scale relation and zero-padded filtering. Error bounds are presented to justify the use of an oblique projection over an orthogonal one. All the filters are FIR with the exception of one filter, which is implemented using a fast recursive algorithm     

采用归一化最小均方误差准则的LM-BP算法

传统神经网络通常以最小均方误差(LMS)或最小二乘（RLS）为收敛准则,而在自适应均衡等一些应用中,使用归一化最小均方误差（NLMS）准则可以使神经网络性能更加优越。本文在NLMS准则基础上,提出了一种以Levenberg-Marquardt（LM）训练的神经网络收敛算法。通过将神经网络的误差函数归一化,然后采用LM算法作为训练算法,实现了神经网络的快速收敛。理论分析和实验仿真表明,与采用最速下降法的NLMS准则和采用LM算法的LMS准则相比,本文算法收敛速度快,归一化均方误差更小,应用于神经网络水印系统中实现了水印信息的盲提取,能更好的抵抗噪声、低通滤波和重量化等攻击,性能平均提高了4%。      

Convergence behavior of affine projection algorithms

A class of equivalent algorithms that accelerate the convergence of the normalized LMS (NLMS) algorithm, especially for colored inputs, has previously been discovered independently. The affine projection algorithm (APA) is the earliest and most popular algorithm in this class that inherits its name. The usual APA algorithms update weight estimates on the basis of multiple, unit delayed, input signal vectors. We analyze the convergence behavior of the generalized APA class of algorithms (allowing for arbitrary delay between input vectors) using a simple model for the input signal vectors. Conditions for convergence of the APA class are derived. It is shown that the convergence rate is exponential and that it improves as the number of input signal vectors used for adaptation is increased. However, the rate of improvement in performance (time-to-steady-state) diminishes as the number of input signal vectors increases. For a given convergence rate, APA algorithms are shown to exhibit less misadjustment (steady-state error) than NLMS. Simulation results are provided to corroborate the analytical results     

A multichannel hierarchical approach to adaptive Volterra filters employing filtered-X affine projection algorithms

It is shown in this paper how the use of a recently introduced algebra, called V-vector algebra, can directly lead to the implementation of Volterra filters of any order P in the form of a multichannel filterbank. Each channel in this approach is modeled as a finite impulse response (FIR) filter, and the channels are hierarchically arranged according to the number of the filter coefficients. In such a way, it is also possible to devise models of reduced complexity by cutting the less relevant channels. This model is then used to derive efficient adaptation algorithms in the context of nonlinear active noise control. In particular, it is shown how the affine projection (AP) algorithms used in the linear case can be extended to a Volterra filter of any order P. The derivation of the so-called Filtered-X AP algorithms for nonlinear active noise controllers is easily obtained using the elements of the V-vector algebra. These algorithms can efficiently replace the standard LMS and NLMS algorithms usually applied in this field, especially when, in practical applications, a reduced-complexity multichannel structure can be exploited.     

Pairwise Optimal Weight Realization—Acceleration Technique for Set-Theoretic Adaptive Parallel Subgradient Projection Algorithm

The adaptive parallel subgradient projection (PSP) algorithm was proposed in 2002 as a set-theoretic adaptive filtering algorithm providing fast and stable convergence, robustness against noise, and low computational complexity by using weighted parallel projections onto multiple time-varying closed half-spaces. In this paper, we present a novel weighting technique named pairwise optimal weight realization (POWER) for further acceleration of the adaptive PSP algorithm. A simple closed-form formula is derived to compute the projection onto the intersection of two closed half-spaces defined by a triplet of vectors. Using the formula inductively, the proposed weighting technique realizes a good direction of update. The resulting weights turn out to be pairwise optimal in a certain sense. The proposed algorithm has the inherently parallel structure composed of q primitive functions, hence its total computational complexity O(qrN) is reduced to O(rN) with q concurrent processors (r: a constant positive integer). Numerical examples demonstrate that the proposed technique for r=1 yields significantly faster convergence than not only adaptive PSP with uniform weights, affine projection algorithm, and fast Newton transversal filters but also the regularized recursive least squares algorithm     

一种新NLMS自适应滤波算法及其在多路回波消除中的应用

提出一种NLMS改进算法并对其收敛性进行了证明。该算法计算复杂度低于Sankaran(1997)所提出的带有正交改正因子的归一化算法(NLMS-OCF)和仿射投影算法(APA),并具有易于实现等特点。仿真结果表明,以单路语音信号作输入时,新算法具有比NLMS-OCF算法更好的收敛速度和精度,而在收敛速度和精度相当的情况下,新算法比APA算法所占用的CPU时间少。将新算法扩展成两路算法后,扩展算法仍然保持了这些特点,与Sankaran(1999)两路NLMS-OCF及Benesty(1996)所提多路仿射算法(APA-MC)相比,新算法更适合于应用到多路回波消除等实时性要求高的场合。1     

A Normalized Least Mean Square Algorithm Based on the Arctangent Cost Function Robust Against Impulsive Interference

In this paper, a normalized least mean square (NLMS) adaptive filtering algorithm based on the arctangent cost function that improves the robustness against impulsive interference is proposed. Owing to the excellent characteristics of the arctangent cost function, the adaptive update of the weight vector stops automatically in the presence of impulsive interference. Thus, this eliminates the likelihood of updating the weight vector based on wrong information resulting from the impulsive interference. When the priori error is small, the NLMS algorithm based on the arctangent cost function operates as the conventional NLMS algorithm. Simulation results show that the proposed algorithm can achieve better performance than the traditional NLMS algorithm, the normalized least logarithmic absolute difference algorithm and the normalized sign algorithm in system identification experiments that include impulsive interference and abrupt changes.     

Low-complexity data reusing methods in adaptive filtering

Most adaptive filtering algorithms couple performance with complexity. Over the last 15 years, a class of algorithms, termed "affine projection" algorithms, have given system designers the capability to tradeoff performance with complexity. By changing parameters and the size/scale of data used to update the coefficients of an adaptive filter but without fundamentally changing the algorithm structure, a system designer can radically change the performance of the adaptive algorithm. This paper discusses low-complexity data reusing algorithms that are closely related to affine projection algorithms. This paper presents various low-complexity and highly flexible schemes for improving convergence rates of adaptive algorithms that utilize data reusing strategies. All of these schemes are unified by a row projection framework in existence for more than 65 years. This framework leads to the classification of all data reusing and affine projection methods for adaptive filtering into two categories: the Kaczmarz and Cimmino methods. Simulation and convergence analysis results are presented for these methods under a number of conditions. They are compared in terms of convergence rate performance and computational complexity.     

Robust Regularization for Normalized LMS Algorithms

We present a novel normalized least mean square (NLMS) algorithm with robust regularization. The proposed algorithm dynamically updates the regularization parameter that is fixed in the conventional$epsilon $-NLMS algorithms. By exploiting the gradient descent direction we derive a computationally efficient and robust update scheme for the regularization parameter. Through experiments we demonstrate that the proposed algorithm outperforms conventional NLMS algorithms in terms of the convergence rate and the misadjustment error.