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     

Convergence of stochastic-approximation-based algorithms for blindchannel identification

We develop adaptive algorithms for multichannel (single-input-multiple-output, or SIMO) blind identification with both statistic and deterministic models. In these algorithms, the estimates are continuously improved while receiving new signals. Therefore, the algorithms can track the channel continuously and thus are amenable to real applications such as wireless communications. At each step, only a small amount of computation is involved. The algorithms are based on stochastic-approximation methods. The convergence properties of these algorithms are proved. Simulation examples are presented to show the performance of the algorithms     

Convergence analysis of blind equalization algorithms using constellation-matching

Two modified blind equalization algorithms are analyzed for performance. These algorithms add a constellationmatched error term to the cost functions of the generalized Sato and multimodulus algorithms. The dynamic convergence behavior and steady-state performance of these algorithms, and of a related version of the constant modulus algorithm, are characterized. The analysis establishes the improved performance of the proposed algorithms.     

Analysis of conjugate gradient algorithms for adaptive filtering

The paper presents and analyzes two approaches to the implementation of the conjugate gradient (CG) algorithm for filtering where several modifications to the original CG method are proposed. The convergence rates and misadjustments for the two approaches are compared. An analysis in the z-domain is used in order to find the asymptotic performance, and stability bounds are established. The behavior of the algorithms in finite word-length computation are described, and dynamic range considerations are discussed. It is shown that in finite word-length computation and close to steady state, the algorithms' behaviors are similar to the steepest descent algorithm, where the stalling phenomenon is observed. Using 16-bit fixed-point number representation, our simulations show that the algorithms are numerically stable     

Convergence studies on iterative algorithms for image reconstruction

We introduce a general iterative scheme for image reconstruction based on Landweber's method. In our configuration, a sequential block-iterative (SeqBI) version can be readily formulated from a simultaneous block-iterative (SimBI) version, and vice versa. This provides a mechanism to derive new algorithms from known ones. It is shown that some widely used iterative algorithms, such as the algebraic reconstruction technique (ART), simultaneous ART (SART), Cimmino's, and the recently designed diagonal weighting and component averaging algorithms, are special examples of the general scheme. We prove convergence of the general scheme under conditions more general than assumed in earlier studies, for its SeqBI and SimBI versions in the consistent and inconsistent cases, respectively. Our results suggest automatic relaxation strategies for the SeqBI and SimBI versions and characterize the dependence of the limit image on the initial guess. It is found that in all cases the limit is the sum of the minimum norm solution of a weighted least-squares problem and an oblique projection of the initial image onto the null space of the system matrix.     

Convergence theorem for a general class of power-control algorithms

We consider the convergence issues of distributed power-control algorithms for mobile cellular systems. A convergence theorem for power-control algorithms of canonical type is proved. Our result generalizes Yates' framework and provides a new outlook on the problem. The general applicability of the theorem is demonstrated by showing that many well-known distributed algorithms are canonical. Furthermore, by devising some new discrete algorithms, we exemplify how the theorem can be used to aid new design.     

Convergence of EM image reconstruction algorithms with Gibbs smoothing

P.J. Green has defined an OSL (one-step late) algorithm that retains the E-step of the EM algorithm (for image reconstruction in emission tomography) but provides an approximate solution to the M-step. Further modifications of the OSL algorithm guarantee convergence to the unique maximum of the log posterior function. Convergence is proved under a specific set of sufficient conditions. Several of these conditions concern the potential function of the Gibb's prior, and a number of candidate potential functions are identified. Generalization of the OSL algorithm to transmission tomography is also considered.     

融合梯度特性与置信度的立体匹配算法

针对现有局部立体匹配算法在计算匹配代价时, 不能很好区分强弱纹理区域,及在视差计算过程 中,不能很好的解决视差歧义问题,提出一种融合梯度特性与置信度的立体匹配算法。首先 计算梯度特 征,并根据梯度特征信息选择匹配代价计算的匹配窗口,针对强弱不同纹理区域选择不同尺 寸的匹配窗 口,有效的提高了立体匹配精度,降低了误匹配率;然后在视差计算中引入置信度约束条件 ,解决了视差 计算中视差歧义的问题,提高了立体匹配算法的稳定性与精度;最后使用水平与垂直方向交 叉区域检测进 行奇异值的修正。实验结果表明,该算法在Middlebury数据集中31对 立体图像对的平均误匹配率为7.96%,有效的提高了立体匹配精度。     

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.     

A new class of gradient adaptive step-size LMS algorithms

The gradient adaptive step-size least-mean-square (LMS) algorithms [an important family of variable step-size LMS (VSLMS) algorithms] are revisited. We propose a simplification to a class of the studied algorithms and show that this leads to a new class of VSLMS algorithms with reduced complexity but with no observable loss in performance     

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.     

Convergence analysis of adaptive filtering algorithms with singulardata covariance matrix

The paper provides a rigorous analysis of the behavior of adaptive filtering algorithms when the covariance matrix of the filter input is singular. The analysis is done in the context of adaptive plant identification. The considered algorithms are LMS, RLS, sign (SA), and signed regressor (SRA) algorithms. Both the signal and weight behavior of the algorithms are considered. The signal behavior is evaluated in terms of the moments of the excess output error of the filter. The weight behavior is evaluated in terms of the moments of the filter weight misalignment vector. It is found that the RLS and SRA diverge when the input covariance matrix is singular. The steady-state signal behavior of the LMS and SA can be made arbitrarily fine by using sufficiently small step sizes of the algorithms. Indeed, the long-term average of the mean square excess error of the LMS is proportional to the algorithm step size. The long-term average of the mean absolute excess error of the SA is proportional to the square root of the algorithm step size. On the other hand, the steady-state weight behavior of both the LMS and SA have biases that depend on the weight initialization. The analytical results of the paper are supported by simulations     

Convergence and stability assessment of Newton-Kantorovichreconstruction algorithms for microwave tomography

For newly developed iterative Newton-Kantorovitch reconstruction techniques, the quality of the final image depends on both experimental and model noise. Experimental noise is inherent to any experimental acquisition scheme, while model noise refers to the accuracy of the numerical model, used in the reconstruction process, to reproduce the experimental setup. This paper provides a systematic assessment of the major sources of experimental and model noise on the quality of the final image. This assessment is conducted from experimental data obtained with a microwave circular scanner operating at 2.33 GHz. Targets to be imaged include realistic biological structures, such as a human forearm, as well as calibrated samples for the sake of accuracy evaluation. The results provide a quantitative estimation of the effect of experimental factors, such as temperature of the immersion medium, frequency, signal-to-noise ratio, and various numerical parameters     

Improved convergence performance of RSER algorithms with modified gradient filtering

A modified gradient filtering technique is applied to a class of recursive sequential regression (RSER) algorithms, in order to improve the convergence performance. The performance behaviour of the new class of algorithms is studied using both all-pole and pole-zero examples.     

The exponentiated Weibull family: a graphical approach

The exponentiated Weibull family extends the two-parameter Weibull distribution. The shape of the Weibull plotting-paper plots are discussed, and a parametric characterization of the pdf and the failure rate for the exponentiated Weibull family are carried out. Such a study is very relevant to deciding if a given data set can be adequately modeled by such a distribution     

Averaged stochastic gradient algorithms for adaptive blindmultiuser detection in DS/CDMA systems

In this paper, we present a blind adaptive gradient (BAG) algorithm for code-aided suppression of multiple-access interference (MAI) and narrow-band interference (NBI) in direct-sequence/code-division multiple-access (DS/CDMA) systems. This BAG algorithm is based on the concept of accelerating the convergence of a stochastic gradient algorithm by averaging. This ingenious concept of averaging was invented by Polyak and Juditsky (1992)-this paper examines its application to blind multiuser detection and NBI suppression in DS/CDMA systems. We prove that BAG has identical convergence and tracking properties to recursive least squares (LMS) but has a computational cost similar to the least mean squares (LMS) algorithm-i.e., an order of magnitude lower computational cost than RLS. Simulations are used to compare our averaged gradient algorithm with the blind LMS and LMS schemes     

Convergence of the conjugate gradient method when applied to matrix equations representing electromagnetic scattering problems

An iterative procedure based on the conjugate gradient method is used to solve a variety of matrix equations representing electromagnetic scattering problems, in an attempt to characterize the typical rate of convergence of that method. It is found that this rate depends on the cell density per wavelength used in the discretization, the presence of symmetries in the solution, and the degree to which mixed cell sizes are used in the models. Assuming cell densities used in the discretization are in the range of ten per linear wavelength, the iterative algorithm typically requiresN/4toN/2steps to converge to necessary accuracy, whereNis the order of the matrix under consideration.     

Stochastic gradient algorithms for design of minimum error-rate linear dispersion codes in MIMO wireless systems

Linear dispersion (LD) codes are a good candidate for high-data-rate multiple-input multiple-ouput (MIMO) signaling. Traditionally LD codes were designed by maximizing the average mutual information, which cannot guarantee good error performance. This paper presents a new design scheme for LD codes that directly minimizes the block error rate (BLER) in MIMO channels with arbitrary fading statistics and various detection algorithms. For MIMO systems employing LD codes, the error rate does not admit an explicit form. Therefore, we cannot use deterministic optimization methods to design the minimum-error-rate LD codes. In this paper, we propose a simulation-based optimization methodology for the design of LD codes through stochastic approximation and simulation-based gradient estimation. The gradient estimation is done using the score function method originally developed in the discrete-event-system community. The proposed method can be applied to design the minimum-error-rate LD codes for a variety of detector structures including the maximum-likelihood (ML) detector and several suboptimal detectors. It can also design optimal codes under arbitrary fading channel statistics; in particular, it can take into account the knowledge of spatial fading correlation at the transmitter and receiver ends. Simulation results show that codes generated by the proposed new design paradigm generally outperform the codes designed based on algebraic number theory.