A mesh-independence principle for operators equations and the Steffensen method

In this study we prove the mesh-independence principle via Steffensen’s method. This principle asserts that when Steffensen’s method is applied to a nonlinear equation between some Banach spaces, as well as to some finite-dimensional discretization of that equation, then the behavior of the discretized process is asymptotically the same as that for the original iteration. Local and semilocal convergence results as well as an error analysis for Steffensen’s method are also provided.     

Acceleration of the EM algorithm using the vector epsilon algorithm

The expectation–maximization (EM) algorithm is a very general and popular iterative computational algorithm to find maximum likelihood estimates from incomplete data and broadly used to statistical analysis with missing data, because of its stability, flexibility and simplicity. However, it is often criticized that the convergence of the EM algorithm is slow. The various algorithms to accelerate the convergence of the EM algorithm have been proposed. The vector ε algorithm of Wynn (Math Comp 16:301–322, 1962) is used to accelerate the convergence of the EM algorithm in Kuroda and Sakakihara (Comput Stat Data Anal 51:1549–1561, 2006). In this paper, we provide the theoretical evaluation of the convergence of the ε-accelerated EM algorithm. The ε-accelerated EM algorithm does not use the information matrix but only uses the sequence of estimates obtained from iterations of the EM algorithm, and thus it keeps the flexibility and simplicity of the EM algorithm.     

A Component-Wise EM Algorithm for Mixtures

Maximum likelihood estimation in finite mixture distributions is typically approached as an incomplete data problem to allow application of the expectation-maximization (EM) algorithm. In its general formulation, the EM algorithm involves the notion of a complete data space, in which the observed measurements and incomplete data are embedded. An advantage is that many difficult estimation problems are facilitated when viewed in this way. One drawback is that the simultaneous update used by standard EM requires overly informative complete data spaces, which leads to slow convergence in some situations. In the incomplete data context, it has been shown that the use of less informative complete data spaces, or equivalently smaller missing data spaces, can lead to faster convergence without sacrifying simplicity. However, in the mixture case, little progress has been made in speeding up EM. In this article we propose a component-wise EM for mixtures. It uses, at each iteration, the smallest admissible missing data space by intrinsically decoupling the parameter updates. Monotonicity is maintained, although the estimated proportions may not sum to one during the course of the iteration. However, we prove that the mixing proportions will satisfy this constraint upon convergence. Our proof of convergence relies on the interpretation of our procedure as a proximal point algorithm. For performance comparison, we consider standard EM as well as two other algorithms based on missing data space reduction, namely the SAGE and AECME algorithms. We provide adaptations of these general procedures to the mixture case. We also consider the ECME algorithm, which is not a data augmentation scheme but still aims at accelerating EM. Our numerical experiments illustrate the advantages of the component-wise EM algorithm relative to these other methods.     

Speed-up for the expectation-maximization algorithm for clustering categorical data

In model-based cluster analysis, the expectation-maximization (EM) algorithm has a number of desirable properties, but in some situations, this algorithm can be slow to converge. Some variants are proposed to speed-up EM in reducing the time spent in the E-step, in the case of Gaussian mixture. The main aims of such methods is first to speed-up convergence of EM, and second to yield same results (or not so far) than EM itself. In this paper, we compare these methods from categorical data, with the latent class model, and we propose a new variant that sustains better results on synthetic and real data sets, in terms of convergence speed-up and number of misclassified objects.     

On the Orderings and Groupings of Conditional Maximizations within ECM-Type Algorithms

Abstract

The ECM and ECME algorithms are generalizations of the EM algorithm in which the maximization (M) step is replaced by several conditional maximization (CM) steps. The order that the CM-steps are performed is trivial to change and generally affects how fast the algorithm converges. Moreover, the same order of CM-steps need not be used at each iteration and in some applications it is feasible to group two or more CM-steps into one larger CM-step. These issues also arise when implementing the Gibbs sampler, and in this article we study them in the context of fitting log-linear and random-effects models with ECM-type algorithms. We find that some standard theoretical measures of the rate of convergence can be of little use in comparing the computational time required, and that common strategies such as using a random ordering may not provide the desired effects. We also develop two algorithms for fitting random-effects models to illustrate that with careful selection of CM-steps, ECM-type algorithms can be substantially faster than the standard EM algorithm.     

An hybrid method that improves the accessibility of Steffensen’s method

Steffensen’s method is known for its fast speed of convergence and its difficulty in applying it in Banach spaces. From the analysis of the accessibility of this method, we see that we can improve it by using the simplified secant method for predicting the initial approximation of Steffensen’s method. So, from both methods, we construct an hybrid iterative method which guarantees the convergence of Steffensen’s method from approximations given by the simplified secant method. We also emphasize that the study presented in this work is valid for equations with differentiable operators and non-differentiable operators.     

Monotonically Overrelaxed EM Algorithms

We explore the idea of overrelaxation for accelerating the expectation-maximization (EM) algorithm, focusing on preserving its simplicity and monotonic convergence properties. It is shown that in many cases, a trivial modification in the M-step results in an algorithm that maintains monotonic increase in the log-likelihood, but can have an appreciably faster convergence rate, especially when EM is very slow. The method is applicable to more general fixed point algorithms. Its simplicity and effectiveness are illustrated with several statistical problems, including probit regression, least absolute deviations regression, Poisson inverse problems, and finite mixtures. This article has supplemental materials available online.     

An efficient ECM algorithm for maximum likelihood estimation in mixtures of t-factor analyzers

Mixture of t factor analyzers (MtFA) have been shown to be a sound model-based tool for robust clustering of high-dimensional data. This approach, which is deemed to be one of natural parametric extensions with respect to normal-theory models, allows for accommodation of potential noise components, atypical observations or data with longer-than-normal tails. In this paper, we propose an efficient expectation conditional maximization (ECM) algorithm for fast maximum likelihood estimation of MtFA. The proposed algorithm inherits all appealing properties of the ordinary EM algorithm such as its stability and monotonicity, but has a faster convergence rate since its CM steps are governed by a much smaller fraction of missing information. Numerical experiments based on simulated and real data show that the new procedure outperforms the commonly used EM and AECM algorithms substantially in most of the situations, regardless of how the convergence speed is assessed by the computing time or number of iterations.     

Comparison of the EM algorithm and alternatives

The Expectation-Maximization (EM) algorithm is widely used also in industry for parameter estimation within a Maximum Likelihood (ML) framework in case of missing data. It is well-known that EM shows good convergence in several cases of practical interest. To the best of our knowledge, results showing under which conditions EM converges fast are only available for specific cases. In this paper, we analyze the connection of the EM algorithm to other ascent methods as well as the convergence rates of the EM algorithm in general including also nonlinear models and apply this to the PMHT model. We compare the EM with other known iterative schemes such as gradient and Newton-type methods. It is shown that EM reaches Newton-convergence in case of well-separated objects and a Newton-EM combination turns out to be robust and efficient even in cases of closely-spaced targets.     

Efficient ML Estimation of the Multivariate Normal Distribution from Incomplete Data

It is well known that the maximum likelihood estimates (MLEs) of a multivariate normal distribution from incomplete data with a monotone pattern have closed-form expressions and that the MLEs from incomplete data with a general missing-data pattern can be obtained using the Expectation-Maximization (EM) algorithm. This article gives closed-form expressions, analogous to the extension of the Bartlett decomposition, for both the MLEs of the parameters and the associated Fisher information matrix from incomplete data with a monotone missing-data pattern. For MLEs of the parameters from incomplete data with a general missing-data pattern, we implement EM and Expectation-Constrained-Maximization-Either (ECME), by augmenting the observed data into a complete monotone sample. We also provide a numerical example, which shows that the monotone EM (MEM) and monotone ECME (MECME) algorithms converge much faster than the EM algorithm.     

Monte Carlo EM加速算法

EM算法是近年来常用的求后验众数的估计的一种数据增广算法, 但由于求出其E步中积分的显示表达式有时很困难, 甚至不可能, 限制了其应用的广泛性. 而Monte Carlo EM算法很好地解决了这个问题, 将EM算法中E步的积分用Monte Carlo模拟来有效实现, 使其适用性大大增强. 但无论是EM算法, 还是Monte Carlo EM算法, 其收敛速度都是线性的, 被缺损信息的倒数所控制, 当缺损数据的比例很高时, 收敛速度就非常缓慢. 而Newton-Raphson算法在后验众数的附近具有二次收敛速率. 本文提出Monte Carlo EM加速算法, 将Monte Carlo EM算法与Newton-Raphson算法结合, 既使得EM算法中的E步用Monte Carlo模拟得以实现, 又证明了该算法在后验众数附近具有二次收敛速度. 从而使其保留了Monte Carlo EM算法的优点, 并改进了Monte Carlo EM算法的收敛速度. 本文通过数值例子, 将Monte Carlo EM加速算法的结果与EM算法、Monte Carlo EM算法的结果进行比较, 进一步说明了Monte Carlo EM加速算法的优良性.     

Convergence analysis of an accelerated expectation‐maximization algorithm for ill‐posed integral equations

The maximum‐likelihood expectation‐maximization (EM) algorithm has attracted considerable interest in single‐photon emission computed tomography, because it produces superior images in addition to be being flexible, simple, and allowing a physical interpretation. However, it often needs a large number of calculations because of the algorithm's slow rate of convergence. Therefore, there is a large body of literature concerning the EM algorithm's acceleration. One of the accelerated means is increasing an overrelaxation parameter, whereas we have not found any analysis in this method that would provide an immediate answer to the questions of the convergence. In this paper, our main focus is on the continuous version of an accelerated EM algorithm based on Lewitt and Muehllenner. We extend their conclusions to the infinite‐dimensional space and interpret and analyze the convergence of the accelerated EM algorithm. We also obtain some new properties of the modified algorithm. Copyright © 2015 John Wiley & Sons, Ltd.     

An Interval Analysis Approach to the EM Algorithm

Abstract

The EM algorithm is widely used in incomplete-data problems (and some complete-data problems) for parameter estimation. One limitation of the EM algorithm is that, upon termination, it is not always near a global optimum. As reported by Wu (1982), when several stationary points exist, convergence to a particular stationary point depends on the choice of starting point. Furthermore, convergence to a saddle point or local minimum is also possible. In the EM algorithm, although the log-likelihood is unknown, an interval containing the gradient of the EM q function can be computed at individual points using interval analysis methods. By using interval analysis to enclose the gradient of the EM q function (and, consequently, the log-likelihood), an algorithm is developed that is able to locate all stationary points of the log-likelihood within any designated region of the parameter space. The algorithm is applied to several examples. In one example involving the t distribution, the algorithm successfully locates (all) seven stationary points of the log-likelihood.     

定数截尾混合指数分布在恒加应力下的MCEM加速算法

应用Monte Carlo EM加速算法给出了混合指数分布在恒加应力水平下,在定数截尾场合的参数估计问题,并通过模拟试验说明利用Monte Carlo EM加速算法来估计混合指数分布比EM算法更有效,收敛速度更快.     

An Asynchronous Distributed Expectation Maximization Algorithm for Massive Data: The DEM Algorithm

The family of expectation--maximization (EM) algorithms provides a general approach to fitting flexible models for large and complex data. The expectation (E) step of EM-type algorithms is time-consuming in massive data applications because it requires multiple passes through the full data. We address this problem by proposing an asynchronous and distributed generalization of the EM called the distributed EM (DEM). Using DEM, existing EM-type algorithms are easily extended to massive data settings by exploiting the divide-and-conquer technique and widely available computing power, such as grid computing. The DEM algorithm reserves two groups of computing processes called workers and managers for performing the E step and the maximization step (M step), respectively. The samples are randomly partitioned into a large number of disjoint subsets and are stored on the worker processes. The E step of DEM algorithm is performed in parallel on all the workers, and every worker communicates its results to the managers at the end of local E step. The managers perform the M step after they have received results from a γ-fraction of the workers, where γ is a fixed constant in (0, 1]. The sequence of parameter estimates generated by the DEM algorithm retains the attractive properties of EM: convergence of the sequence of parameter estimates to a local mode and linear global rate of convergence. Across diverse simulations focused on linear mixed-effects models, the DEM algorithm is significantly faster than competing EM-type algorithms while having a similar accuracy. The DEM algorithm maintains its superior empirical performance on a movie ratings database consisting of 10 million ratings. Supplementary material for this article is available online.     

A family of Steffensen type methods with seventh-order convergence

In this paper, based on some known fourth-order Steffensen type methods, we present a family of three-step seventh-order Steffensen type iterative methods for solving nonlinear equations and nonlinear systems. For nonlinear systems, a development of the inverse first-order divided difference operator for multivariable function is applied to prove the order of convergence of the new methods. Numerical experiments with comparison to some existing methods are provided to support the underlying theory.     

An improved local convergence analysis for Newton–Steffensen-type method

We provide a local convergence analysis for Newton–Steffensen-type algorithm for solving nonsmooth perturbed variational inclusions in Banach spaces. Under new center–conditions and the Aubin continuity property, we obtain the linear local convergence of Newton–Steffensen method. Our results compare favorably with related obtained in (Argyros and Hilout, 2007 submitted; Hilout in J. Math. Anal. Appl. 339:753–761, 2008).     

A nonlinearly preconditioned conjugate gradient algorithm for rank‐R canonical tensor approximation

Alternating least squares (ALS) is often considered the workhorse algorithm for computing the rank‐R canonical tensor approximation, but for certain problems, its convergence can be very slow. The nonlinear conjugate gradient (NCG) method was recently proposed as an alternative to ALS, but the results indicated that NCG is usually not faster than ALS. To improve the convergence speed of NCG, we consider a nonlinearly preconditioned NCG (PNCG) algorithm for computing the rank‐R canonical tensor decomposition. Our approach uses ALS as a nonlinear preconditioner in the NCG algorithm. Alternatively, NCG can be viewed as an acceleration process for ALS. We demonstrate numerically that the convergence acceleration mechanism in PNCG often leads to important pay‐offs for difficult tensor decomposition problems, with convergence that is significantly faster and more robust than for the stand‐alone NCG or ALS algorithms. We consider several approaches for incorporating the nonlinear preconditioner into the NCG algorithm that have been described in the literature previously and have met with success in certain application areas. However, it appears that the nonlinearly PNCG approach has received relatively little attention in the broader community and remains underexplored both theoretically and experimentally. Thus, this paper serves several additional functions, by providing in one place a concise overview of several PNCG variants and their properties that have only been described in a few places scattered throughout the literature, by systematically comparing the performance of these PNCG variants for the tensor decomposition problem, and by drawing further attention to the usefulness of nonlinearly PNCG as a general tool. In addition, we briefly discuss the convergence of the PNCG algorithm. In particular, we obtain a new convergence result for one of the PNCG variants under suitable conditions, building on known convergence results for non‐preconditioned NCG. Copyright © 2014 John Wiley & Sons, Ltd.     

双边定时截尾样本下广义逆指数分布形状参数的估计

先给出了广义逆指数分布在双边定时截尾样本下形状参数的最大似然估计,并不能得到估计的显式表达式,但证明了参数在(0,+∞)上最大似然估计是唯一存在的.其次提出用EM算法求出形状参数的估计且该估计具有良好的收敛性,还给出了形状参数的EM估计的渐近方差和近似置信区间;最后通过数值模拟,对形状参数的最大似然估计和EM估计的效果进行了比较,说明了用EM算法求形状参数的估计是可行的,并且模拟效果相对比较好.     

凸可行问题的平行近似次梯度投影算法

对凸可行问题提出了包括上松弛的平行近似次梯度投影算法和加速平行近似次梯度投影算法．与序列近似次梯度投影算法相比, 平行近似次梯度投影算法(每次迭代同时运用多个凸集的近似次梯度超平面上的投影)能够保证迭代序列收敛到离各个凸集最近的点． 上松弛的迭代技术和含有外推因子的加速技术的应用, 减少了数据存储量, 提高了收 敛速度. 最后在较弱的条件下证明了算法的收敛性, 数值实验结果验证了算法的有效性和优越性.