Stochastic analysis of the LMS algorithm for cyclostationary colored Gaussian and non-Gaussian inputs

This paper studies the stochastic behavior of the LMS algorithm in a system identification framework for a cyclostationary colored input without assuming a Gaussian distribution for the input. The input cyclostationary signal is modeled by a colored random process with periodically time-varying power. The generation of the colored non-Gaussian random process is parametrized in novel manner by passing a Gaussian random process through a coloring filter followed by a zero memory nonlinearity. The unknown system parameters are fixed in most of the cases studied here. Mathematical models are derived for the behavior of the mean and mean-square-deviation (MSD) and the excess mean-square error (EMSE) of the adaptive weights as a function of the input cyclostationarity. The models display the dependence of the algorithm upon the input nonlinearity and coloration. Three nonlinearities that are studied in detail with Monte Carlo simulations provide strong support for the theory.     

Mean-square stability of the Normalized Least-Mean Fourth algorithm for white Gaussian inputs

Normalized forms of adaptive algorithms are usually sought in order to obtain convergence properties independent of the input signal power. Such is the case of the well-known Normalized LMS (NLMS) algorithm. The Least-Mean Fourth (LMF) adaptive algorithm has been shown to outperform LMS in different situations. However, the LMF stability is dependent on both the signal power and on the adaptive weights initialization. This paper studies the behavior of two normalized forms of the LMF algorithm for Gaussian inputs. Contrary to what could be expected, the mean-square stability of both normalized algorithms is shown to be dependent upon the input signal power. Thus, the usefulness of the NLMF algorithm is open to question.     

Stochastic modeling of the NLMS algorithm for complex Gaussian input data and nonstationary environment

This paper presents a stochastic model for the normalized least-mean-square (NLMS) algorithm operating in a nonstationary environment with complex-valued Gaussian input data. To derive this model, several approximations commonly used in the modeling of algorithms with normalized step size are avoided, thus giving rise to very accurate model expressions describing the algorithm behavior in both transient and steady-state phases. Such accuracy comes mainly from the strategy used for computing the normalized autocorrelation-like matrices arising from the model development, for which analytical solutions are also derived here. In addition, based on the proposed model expressions, the impact of the algorithm parameters on its performance is discussed, clarifying the tracking properties of the NLMS algorithm in a nonstationary environment. Through simulation results, the effectiveness of the proposed model is assessed for different operating scenarios.     

Improved analysis of the greedy algorithm for stochastic matching

The stochastic matching problem with applications in online dating and kidney exchange was introduced by Chen et al. (2009) [1] together with a simple greedy strategy. They proved it is a 4-approximation, but conjectured that the greedy algorithm is in fact a 2-approximation. In this paper we confirm this hypothesis.     

Stochastic convergence analysis and parameter selection of the standard particle swarm optimization algorithm

This letter presents a formal stochastic convergence analysis of the standard particle swarm optimization (PSO) algorithm, which involves with randomness. By regarding each particle's position on each evolutionary step as a stochastic vector, the standard PSO algorithm determined by non-negative real parameter tuple {ω,c₁,c₂} is analyzed using stochastic process theory. The stochastic convergent condition of the particle swarm system and corresponding parameter selection guidelines are derived.     

Stochastic averaging analysis of a steepest-descent-type adaptive time-delay estimation algorithm

In this paper stochastic averaging analysis tools are used to study an adaptive time-delay estimation algorithm. Analyzing such an algorithm is very difficult because of its nonlinear, infinite-dimensional, and time-variant nature. By stochastic averaging analysis, we show that for the time-invariant delay case, the adaptive algorithm output converges weakly to the solution of an ordinary differential equation. Local convergence is demonstrated by showing that the solution of this differential equation converges exponentially to the true delay under reasonable initial conditions. Implementation of the algorithm is also discussed. Guided by the averaging results, a modified algorithm is proposed to eliminate the bias of the delay estimation. Second-order analysis is carried out and the results provide a theoretical justification of the observations made by other researchers with simulation and heuristic argument. Computer simulations are also included to support the analysis.     

The particle swarm optimization algorithm: convergence analysis and parameter selection

The particle swarm optimization algorithm is analyzed using standard results from the dynamic system theory. Graphical parameter selection guidelines are derived. The exploration-exploitation tradeoff is discussed and illustrated. Examples of performance on benchmark functions superior to previously published results are given.     

Stochastic algorithms for robustness of control performances

In recent years, there has been a growing interest in developing statistical learning methods to provide approximate solutions to “difficult” control problems. In particular, randomized algorithms have become a very popular tool used for stability and performance analysis as well as for design of control systems. However, as randomized algorithms provide an efficient solution procedure to the “intractable” problems, stochastic methods bring closer to understanding the properties of the real systems. The topic of this paper is the use of stochastic methods in order to solve the problem of control robustness: the case of parametric stochastic uncertainty is considered. Necessary concepts regarding stochastic control theory and stochastic differential equations are introduced. Then a convergence analysis is provided by means of the Chernoff bounds, which guarantees robustness in mean and in probability. As an illustration, the robustness of control performances of example control systems is computed.     

Low complexity LMS-type adaptive algorithm with selective coefficient update for stereophonic acoustic echo cancellation

Stereophonic acoustic echo cancellation (SAEC) has brought up recently much attention and found a viable place in a number of hands-free applications. In this paper, we propose an LMS-type algorithm for SAEC based on decomposing the long adaptive filter of each channel of the SAEC system into smaller subfilters. We further reduce the complexity of the algorithm by employing the selective coefficient update (SCU) method in each subfilter. This leads to a significant improvement in the convergence rate of the algorithm with low computational overhead. However, the algorithm has a high final mean-square error (MSE) at steady-state that increases as number of subfilters increases. A combined-error algorithm is presented that achieves fast convergence without compromising the steady state error level. Simulations demonstrate the convergence speed advantages of the combined-error algorithm.     

Transient and steady-state MSE analysis of the IMPNLMS algorithm

Several techniques have been proposed in the literature to accelerate the convergence of adaptive algorithms for the identification of sparse impulse responses (i.e., with energy concentrated in a few coefficients). Among these techniques, the improved μ-law proportionate normalized least mean squares (IMPNLMS) algorithm is one of the most effective. This paper presents an accurate transient analysis of this algorithm and derives an estimate of its steady-state MSE, without requiring the assumption of white Gaussian input signals.     

Simplified tight analysis of Johnson's algorithm

In their paper “Tight bound on Johnson's algorithm for maximum satisfiability” [J. Comput. System Sci. 58 (3) (1999) 622-640] Chen, Friesen and Zheng provided a tight bound on the approximation ratio of Johnson's algorithm for Maximum Satisfiability [J. Comput. System Sci. 9 (3) (1974) 256-278]. We give a simplified proof of their result and investigate to what extent it may be generalized to non-Boolean domains.     

A new analysis of the false positive rate of a Bloom filter

A Bloom filter is a space-efficient data structure used for probabilistic set membership testing. When testing an object for set membership, a Bloom filter may give a false positive. The analysis of the false positive rate is a key to understanding the Bloom filter and applications that use it. We show experimentally that the classic analysis for false positive rate is wrong. We formally derive a correct formula using a balls-and-bins model and show how to numerically compute the new, correct formula in a stable manner. We also prove that the new formula always results in a predicted greater false positive rate than the classic formula. This correct formula is numerically compared to the classic formula for relative error - for a small Bloom filter the prediction of false positive rate will be in error when the classic formula is used.     

Stochastic simulation-based genetic algorithm for chance constraint programming problems with continuous random variables

In this article, we present a stochastic simulation-based genetic algorithm for solving chance constraint programming problems, where the random variables involved in the parameters follow any continuous distribution. Generally, deriving the deterministic equivalent of a chance constraint is very difficult due to complicated multivariate integration and is only possible if the random variables involved in the chance constraint follow some specific distribution such as normal, uniform, exponential and lognormal distribution. In the proposed method, the stochastic model is directly used. The feasibility of the chance constraints are checked using stochastic simulation, and the genetic algorithm is used to obtain the optimal solution. A numerical example is presented to prove the efficiency of the proposed method.     

Mean analysis of an online algorithm for the vertex cover problem

In 2005, Demange and Paschos proposed in [M. Demange, V.Th. Paschos, On-line vertex-covering, Theoret. Comput. Sci. 332 (2005) 83-108] an online algorithm (noted LR here) for the classical vertex cover problem. They shown that, for any graph of maximum degree Δ, LR constructs a vertex cover whose size is at most Δ times the optimal one (this bound is tight in the worst case).Very recently, two of the present authors have shown in [F. Delbot, C. Laforest, A better list heuristic for vertex cover, Inform. Process. Lett. 107 (2008) 125-127] that LR has interesting properties (it is a good “list algorithm” and it can easily be distributed). In addition, LR has good experimental behavior in spite of its Δ approximation (or competitive) ratio and the fact that it can be executed without the knowledge of the full instance at the beginning.In this paper we analyze it deeper and we show that LR has good “average” performances: we prove that its mean approximation ratio is strictly less than 2 for any graph and is equal to 1+e−2≈1.13 in paths. LR is then a very interesting algorithm for constructing small vertex covers, despite its bad worst case behavior.     

A new recursive identification algorithm for singularity free adaptive control

Reportedly, guaranteeing the controllability of the estimated system is a crucial problem in adaptive control. In this paper, we introduce a least-squares-based identification algorithm for stochastic SISO systems, which secures the uniform controllability of the estimated system and presents closed-loop identification properties similar to those of the least-squares algorithm. The proposed algorithm is recursive and, therefore, easily implementable. Its use, however, is confined to cases in which the parameter uncertainly is highly structured.     

水声信道盲均衡的最小平方峭度恒模算法

用误差信号峭度定义了平方峭度代价函数，提出了盲均衡器权系数更新的最小平方峭度恒模算法，该算法更新方程中含有的误差信号峰度因子有效地消除了高斯性误差信号的影响，加快了收敛，减小了收敛后的均方误差和码间干扰。用负声速梯度水声信道，对算法的性能进行了仿真研究。结果表明：该算法在收敛速度，收敛后的均方误差及码间干扰等方面的性能优于常数模算法与最小平均峭度恒模算法。     

The Pair Completion algorithm for the Homogeneous Set Sandwich Problem

A homogeneous set is a non-trivial module of a graph, i.e., a non-empty, non-unitary, proper vertex subset such that all its elements present the same outer neighborhood. Given two graphs G₁(V,E₁) and G₂(V,E₂), the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a graph GS(V,ES), E₁⊆ES⊆E₂, which has a homogeneous set. This paper presents an algorithm that uses the concept of bias graph [S. Tang, F. Yeh, Y. Wang, An efficient algorithm for solving the homogeneous set sandwich problem, Inform. Process. Lett. 77 (2001) 17-22] to solve the problem in time, thus outperforming the other known HSSP deterministic algorithms for inputs where .     

On the longest path algorithm for reconstructing trees from distance matrices

Culberson and Rudnicki [J.C. Culberson, P. Rudnicki, A fast algorithm for constructing trees from distance matrices, Inform. Process. Lett. 30 (4) (1989) 215-220] gave an algorithm that reconstructs a degree d restricted tree from its distance matrix. According to their analysis, it runs in time O(dnlogdn) for topological trees. However, this turns out to be false; we show that the algorithm takes time in the topological case, giving tight examples.     

Stochastic adaptive pole-zero assignment with convergence analysis

The adaptive control u_n is designed for the stochastic system A(z)y_n+1 = B(z)u_n+C(z)w_n+1 with unknown constant matrix coefficients in the polynomials A(z), B(z) and C(z) in the shift-back operator with the purposes that (1) the unknown matrices are strongly consistently estimated and (2) the poles and zeros are replaced in such a way that the system itself is transferred to A⁰(z)y_n+1 = B⁰(z)u_n⁰+_n+1 with given A⁰(z), B⁰(z) and u_n⁰ so that the pole-zero assignment error {_n+1} is minimized. The problem of adaptive pole-zero assignment combined with tracking is also considered in this paper. Conditions used are imposed only on A(z), B(z) and C(z).     

A high-gain adaptive observer for detecting Li-ion battery terminal voltage collapse

We use a high-gain adaptive observer and a trend filtering algorithm to detect early stages that lead to terminal voltage collapses in Li-ion batteries. This approach allows accurate detection without having sophisticated battery models. Theoretical analysis proves that the physical Li-ion battery becomes unstable when the estimated states of the observer enter instability. The trend filtering algorithm is able to detect such instability under large perturbations from the discharge current. Extensive simulation and experimental results demonstrate the effectiveness of the algorithms and its robustness under realistic perturbations.