Convergence properties of Gauss-Newton iterative algorithms in nonlinear image restoration

Nonlinear image restoration is a complicated problem that is receiving increasing attention. Since every image formation system involves a built-in nonlinearity, nonlinear image restoration finds applications in a wide variety of research areas. Iterative algorithms have been well established in the corresponding linear restoration problem. In this paper, a generalized analysis regarding the convergence properties of nonlinear iterative algorithms is introduced. Moreover, the applications of the iterative Gauss-Newton (GN) algorithm in nonlinear image restoration are considered. The convergence properties of a general class of nonlinear iterative algorithms are rigorously studied through the Global Convergence Theorem (GCT). The derivation of the convergence properties is based on the eigen-analysis, rather than on the norm analysis. This approach offers a global picture of the evolution and the convergence properties of an iterative algorithm. Moreover, the generalized convergence-analysis introduced may be interpreted as a link towards the integration of minimization and projection algorithms. The iterative GN algorithm for the solution of the least-squares optimization problem is introduced. The computational complexity of this algorithm is enormous, making its implementation very difficult in practical applications. Structural modifications are introduced, which drastically reduce the computational complexity while preserving the convergence rate of the GN algorithm. With the structural modifications, the GN algorithm becomes particularly useful in nonlinear optimization problems. The convergence properties of the algorithms introduced are readily derived, on the basis of the generalized analysis through the GCT. The application of these algorithms on practical problems, is demonstrated through several examples.     

哈默斯坦非线性时变系统的加权学习辨识方法

针对有限区间哈默斯坦(Hammerstein)非线性时变系统,该文提出一种加权迭代学习算法用以估计系统时变参数。首先将Hammerstein系统输入非线性部分进行多项式展开,采用迭代学习最小二乘算法辨识系统的时变参数。为了防止数据饱和,采用带遗忘因子的迭代学习最小二乘算法,进而引入权矩阵,采用加权迭代学习最小二乘算法改进系统跟踪误差,以提高辨识精度。该文分别给出3种算法的推导过程并进行仿真验证。结果表明,与迭代学习最小二乘算法和带遗忘因子迭代学习最小二乘算法相比,加权迭代学习最小二乘算法具有辨识精度高、跟踪误差小以及迭代次数少等优点。     

一类 Wiener 非线性时变系统的迭代学习辨识

针对Wiener非线性时变系统的参数辨识问题,该文提出一种基于重复轴的迭代学习算法来实现对时变甚至突变参数的估计。文中将维纳系统输出非线性部分的反函数进行多项式展开,进而构造了回归模型,未知参数及中间变量用其估计替代,分别给出了采用迭代学习梯度算法和迭代学习最小二乘算法实现时变参数辨识的方法。仿真结果表明,与带遗忘因子的递推算法和迭代学习梯度算法相比,迭代学习最小二乘算法更具有参数估计收敛速度快,辨识精度高,系统输出误差小等优势,验证了所提学习算法的有效性。     

Adaptive Reduced-Rank Processing Based on Joint and Iterative Interpolation, Decimation, and Filtering

We present an adaptive reduced-rank signal processing technique for performing dimensionality reduction in general adaptive filtering problems. The proposed method is based on the concept of joint and iterative interpolation, decimation and filtering. We describe an iterative least squares (LS) procedure to jointly optimize the interpolation, decimation and filtering tasks for reduced-rank adaptive filtering. In order to design the decimation unit, we present the optimal decimation scheme and also propose low-complexity decimation structures. We then develop low-complexity least-mean squares (LMS) and recursive least squares (RLS) algorithms for the proposed scheme along with automatic rank and branch adaptation techniques. An analysis of the convergence properties and issues of the proposed algorithms is carried out and the key features of the optimization problem such as the existence of multiple solutions are discussed. We consider the application of the proposed algorithms to interference suppression in code-division multiple-access (CDMA) systems. Simulations results show that the proposed algorithms outperform the best known reduced-rank schemes with lower complexity.     

Nonlinear adaptive prediction of speech with a pipelined recurrentneural network

New learning algorithms for an adaptive nonlinear forward predictor that is based on a pipelined recurrent neural network (PRNN) are presented. A computationally efficient gradient descent (GD) learning algorithm, together with a novel extended recursive least squares (ERLS) learning algorithm, are proposed. Simulation studies based on three speech signals that have been made public and are available on the World Wide Web (WWW) are used to test the nonlinear predictor. The gradient descent algorithm is shown to yield poor performance in terms of prediction error gain, whereas consistently improved results are achieved with the ERLS algorithm. The merit of the nonlinear predictor structure is confirmed by yielding approximately 2 dB higher prediction gain than a linear structure predictor that employs the conventional recursive least squares (RLS) algorithm     

Least squares based and gradient based iterative identification for Wiener nonlinear systems

This paper derives a least squares-based and a gradient-based iterative identification algorithms for Wiener nonlinear systems. These methods separate one bilinear cost function into two linear cost functions, estimating directly the parameters of Wiener systems without re-parameterization to generate redundant estimates. The simulation results confirm that the proposed two algorithms are valid and the least squares-based iterative algorithm has faster convergence rates than the gradient-based iterative algorithm.     

A general class of preconditioners for statistical iterativereconstruction of emission computed tomography

A major drawback of statistical iterative image reconstruction for emission computed tomography is its high computational cost. The ill-posed nature of tomography leads to slow convergence for standard gradient-based iterative approaches such as the steepest descent or the conjugate gradient algorithm. Here, new theory and methods for a class of preconditioners are developed for accelerating the convergence rate of iterative reconstruction. To demonstrate the potential of this class of preconditioners, a preconditioned conjugate gradient (PCG) iterative algorithm for weighted least squares reconstruction (WLS) was formulated for emission tomography. Using simulated positron emission tomography (PET) data of the Hoffman brain phantom, it was shown that the convergence rate of the PCG can reduce the number of iterations of the standard conjugate gradient algorithm by a factor of 2-8 times depending on the convergence criterion     

Finite word-length effects in recursive least squares algorithms with application to adaptive equalization

In this paper we provide a summary of recent and new results on finite word length effects in recursive least squares adaptive algorithms. We define the numerical accuracy and numerical stability of adaptive recursive least squares algorithms and show that these two properties are related to each other, but are not equivalent. The numerical stability of adaptive recursive least squares algorithms is analyzed theoretically and the numerical accuracy with finite word length is investigated by computer simulation. It is shown that the conventional recursive least squares algorithm gives poor numerical accuracy when a short word length is used. A new form of a recursive least squares lattice algorithm is presented which is more robust to round-off errors compared to the conventional form. Optimum scaling of recursive least squares algorithms for fixedpoint implementation is also considered.     

A general class of nonlinear normalized adaptive filteringalgorithms

The normalized least mean square (NLMS) algorithm is an important variant of the classical LMS algorithm for adaptive linear filtering. It possesses many advantages over the LMS algorithm, including having a faster convergence and providing for an automatic time-varying choice of the LMS stepsize parameter that affects the stability, steady-state mean square error (MSE), and convergence speed of the algorithm. An auxiliary fixed step-size that is often introduced in the NLMS algorithm has the advantage that its stability region (step-size range for algorithm stability) is independent of the signal statistics. In this paper, we generalize the NLMS algorithm by deriving a class of nonlinear normalized LMS-type (NLMS-type) algorithms that are applicable to a wide variety of nonlinear filter structures. We obtain a general nonlinear NLMS-type algorithm by choosing an optimal time-varying step-size that minimizes the next-step MSE at each iteration of the general nonlinear LMS-type algorithm. As in the linear case, we introduce a dimensionless auxiliary step-size whose stability range is independent of the signal statistics. The stability region could therefore be determined empirically for any given nonlinear filter type. We present computer simulations of these algorithms for two specific nonlinear filter structures: Volterra filters and the previously proposed class of Myriad filters. These simulations indicate that the NLMS-type algorithms, in general, converge faster than their LMS-type counterparts     

The extended least squares criterion: minimization algorithms andapplications

The least squares (LS) estimation criterion on one hand, and the total LS (TLS), constrained TLS (CTLS) and structured TLS (STLS) criteria on the other hand, can be viewed as opposite limiting cases of a more general criterion, which we term “extended LS” (XLS). The XLS criterion distinguishes measurement errors from modeling errors by properly weighting and balancing the two error sources. In the context of certain models (termed “pseudo-linear”), we derive two iterative algorithms for minimizing the XLS criterion: One is a straightforward “alternating coordinates” minimization, and the other is an extension of an existing CTLS algorithm. The algorithms exhibit different tradeoffs between convergence rate, computational load, and accuracy. The XLS criterion can be applied to popular estimation problems, such as identifying an autoregressive (AR) with exogenous noise (ARX) system from noisy input/output measurements or estimating the parameters of an AR process from noisy measurements. We demonstrate the convergence properties and performance of the algorithms with examples of the latter     

On the convergence of generalized simultaneous iterative reconstruction algorithms.

In this paper, we generalize the widely used simultaneous block iterative reconstruction algorithm and show that it converges, at a linear rate, to a weighted least-squares and weighted minimum-norm reconstruction. Our theoretical result provides a much simpler proof of the convergence properties obtained by Jiang and Wang and covers a much more general class of algorithms. The frequency domain iterative reconstruction algorithm is then introduced as a special application of our theory.     

A regularized iterative image restoration algorithm

The development of the algorithm is based on a set theoretic approach to regularization. Deterministic and/or statistical information about the undistorted image and statistical information about the noise are directly incorporated into the iterative procedure. The restored image is the center of an ellipsoid bounding the intersection of two ellipsoids. The proposed algorithm, which has the constrained least squares algorithm as a special case, is extended into an adaptive iterative restoration algorithm. The spatial adaptivity is introduced to incorporate properties of the human visual system. Convergence of the proposed iterative algorithms is established. For the experimental results which are shown, the adaptively restored images have better quality than the nonadaptively restored ones based on visual observations and on an objective criterion of merit which accounts for the noise masking property of the visual system     

Application of Least Squares Lattice Algorithms to Adaptive Equalization

In many applications of adaptive data equalization, rapid initial convergence of the adaptive equalizer is of paramount importance. Apparently, the fastest known equalizer adaptation algorithm is based on a recursive least squares estimation algorithm. In this paper we show how the least squares lattice algorithms, recently introduced by Morf and Lee, can be adapted to the equalizer adjustment algorithm. The resulting algorithm, although computationally more complex than certain other equalizer algorithms (including the fast Kalman algorithm), has a number of desirable features which should prove useful in many applications.     

Echo Cancellation of Voiceband Data Signals Using Recursive Least Squares and Stochastic Gradient Algorithms

The convergence properties of adaptive least squares (LS) and stochastic gradient (SG) algorithms are studied in the context of echo cancellation of voiceband data signals. The algorithms considered are the SG transversal, SG lattice, LS transversal (fast Kalman), and LS lattice. It is shown that for the channel estimation problem considered here, LS algorithms converge in approximately2Niterations whereNis the order of the filter. In contrast, both SG algorithms display inferior convergence properties due to their reliance upon statistical averages. Simulations are presented to verify this result, and indicate that the fast Kalman algorithm frequently displays numerical instability which can be circumvented by using the lattice structure. Finally, the equivalence between an LS algorithm and a fast converging modified SG algorithm which uses a maximum length input data sequence is shown.     

Iterative space-time processing for multiuser detection in multipath CDMA channels

Space-time processing and multiuser detection are two promising techniques for combating multipath distortion and multiple-access interference in code division multiple access (CDMA) systems. To overcome the computational burden that rises very quickly with increasing numbers of users and receive antennas in applying such techniques, iterative implementations of several space-time multiuser detection algorithms are considered here. These algorithms include iterative linear space-time multiuser detection, Cholesky iterative decorrelating decision-feedback space-time multiuser detection, multistage interference canceling space-time multiuser detection, and expectation-maximization (EM)-based iterative space-time multiuser detection. A new space-time multiuser receiver structure that allows for efficient implementation of iterative processing is also introduced. Fully exploiting various types of diversity through joint space-time processing and multiuser detection brings substantial gain over single-receiver-antenna or single-user-based methods. It is shown that iterative implementation of linear and nonlinear space-time multiuser detection schemes discussed in this paper realizes this substantial gain and approaches the optimum performance with reasonable complexity. Among the iterative space-time multiuser receivers considered in this paper, the EM-based (SAGE) iterative space-time multiuser receiver introduced here achieves the best performance with excellent convergence properties.     

Parallelizable Bayesian tomography algorithms with rapid,guaranteed convergence

Bayesian tomographic reconstruction algorithms generally require the efficient optimization of a functional of many variables. In this setting, as well as in many other optimization tasks, functional substitution (FS) has been widely applied to simplify each step of the iterative process. The function to be minimized is replaced locally by an approximation having a more easily manipulated form, e.g., quadratic, but which maintains sufficient similarity to descend the true functional while computing only the substitute. We provide two new applications of FS methods in iterative coordinate descent for Bayesian tomography. The first is a modification of our coordinate descent algorithm with one-dimensional (1-D) Newton-Raphson approximations to an alternative quadratic which allows convergence to be proven easily. In simulations, we find essentially no difference in convergence speed between the two techniques. We also present a new algorithm which exploits the FS method to allow parallel updates of arbitrary sets of pixels using computations similar to iterative coordinate descent. The theoretical potential speed up of parallel implementations is nearly linear with the number of processors if communication costs are neglected.     

MRL-filters: a general class of nonlinear systems and their optimaldesign for image processing

A class of morphological/rank/linear (MRL)-filters is presented as a general nonlinear tool for image processing. They consist of a linear combination between a morphological/rank filter and a linear filter. A gradient steepest descent method is proposed to optimally design these filters, using the averaged least mean squares (LMS) algorithm. The filter design is viewed as a learning process, and convergence issues are theoretically and experimentally investigated. A systematic approach is proposed to overcome the problem of nondifferentiability of the nonlinear filter component and to improve the numerical robustness of the training algorithm, which results in simple training equations. Image processing applications in system identification and image restoration are also presented, illustrating the simplicity of training MRL-filters and their effectiveness for image/signal processing.     

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.     

卫星通信中快速非线性信道RLS均衡算法

幅度相位联合调制(Amplitude Phase Shift Keying, APSK)信号经过卫星信道时容易引起非线性失真,产生码间串扰。为此,本文将Wiener均衡应用于APSK卫星通信中,并提出了一种快速非线性信道递归最小二乘(Nonlinear Channel Recursive Least Squares, NCRLS)均衡算法,在传统NCRLS算法的基础上,建立了遗忘因子与步长因子的关系,推出了变遗忘因子的非线性信道递归最小二乘(Variable Forgetting Factor Nonlinear Channel Recursive Least Squares, VFFNCRLS)均衡算法,有效地提高了收敛速度。仿真结果表明,VFFNCRLS算法有效地纠正了非线性失真信号的星座扭曲和频谱再生,解决了卫星通信系统中有记忆非线性信道失真的问题,相比传统算法,具有较快的收敛速度和较好的稳定性。      

基于最小二乘和牛顿迭代法的空中目标定位

在对远程高速运动目标进行定位的过程中,提高定位精度是工程研究的重要内容之一.针对最小二乘法受测量误差影响较大的问题,提出了基于最小二乘和牛顿迭代法的混合算法.该算法结合了最小二乘法估计性好和牛顿迭代法收敛速度快的优点.仿真结果表明,时差测量精度为5ns时,均方根误差较最小二乘法定位结果减少了43m.