Squared Extrapolation Methods (SQUAREM): A New Class of Simple and Efficient Numerical Schemes for Accelerating the Convergence of the EM Algorithm

We derive a new class of iterative schemes for accelerating the convergence of the EM algorithm, by exploiting the connection between fixed point iterations and extrapolation methods. First, we present a general formulation of one-step iterative schemes, which are obtained by cycling with the extrapolation methods. We, then square the one-step schemes to obtain the new class of methods, which we call SQUAREM. Squaring a one-step iterative scheme is simply applying it twice within each cycle of the extrapolation method. Here we focus on the first order or rank-one extrapolation methods for two reasons, (1) simplicity, and (2) computational efficiency. In particular, we study two first order extrapolation methods, the reduced rank extrapolation (RRE1) and minimal polynomial extrapolation (MPE1). The convergence of the new schemes, both one-step and squared, is non-monotonic with respect to the residual norm. The first order one-step and SQUAREM schemes are linearly convergent, like the EM algorithm but they have a faster rate of convergence. We demonstrate, through five different examples, the effectiveness of the first order SQUAREM schemes, SqRRE1 and SqMPE1, in accelerating the EM algorithm. The SQUAREM schemes are also shown to be vastly superior to their one-step counterparts, RRE1 and MPE1, in terms of computational efficiency. The proposed extrapolation schemes can fail due to the numerical problems of stagnation and near breakdown. We have developed a new hybrid iterative scheme that combines the RRE1 and MPE1 schemes in such a manner that it overcomes both stagnation and near breakdown. The squared first order hybrid scheme, SqHyb1, emerges as the iterative scheme of choice based on our numerical experiments. It combines the fast convergence of the SqMPE1, while avoiding near breakdowns, with the stability of SqRRE1, while avoiding stagnations. The SQUAREM methods can be incorporated very easily into an existing EM algorithm. They only require the basic EM step for their implementation and do not require any other auxiliary quantities such as the complete data log likelihood, and its gradient or hessian. They are an attractive option in problems with a very large number of parameters, and in problems where the statistical model is complex, the EM algorithm is slow and each EM step is computationally demanding.

About the Use of the HdHr Algorithm Group in Integrating the Movement Equation with Nonlinear Terms

This work summarizes the HdHr group of Hermitian integration algorithms for dynamic structural analysis applications. It proposes a procedure for their use when nonlinear terms are present in the equilibrium equation. The simple pendulum problem is solved as a first example and the numerical results are discussed. Directions to be pursued in future research are also mentioned. Copyright (C) 2009 H.M. Bottura and A. C. Rigitano.

A Simple Algorithm for Unique Representation of Chemical Structures - Cyclic/ Acyclic Functionalized Achiral Hydrocarbons

An algorithm, based on ‘vertex priority values’ has been proposed to uniquely sequence and represent connectivity matrix of chemical structures of cyclic/ acyclic functionalized achiral hydrocarbons and their derivatives. In this method ‘vertex priority values’ have been assigned in terms of atomic weights, subgraph lengths, loops, and heteroatom contents. Subsequently the terminal vertices have been considered upon completing the sequencing of the core vertices. This approach provides a multilayered connectivity graph, which can be put to use in comparing two or more structures or parts thereof for any given purpose. Furthermore the basic vertex connection tables generated here are useful in the computation of characteristic matrices/ topological indices, automorphism groups, and in storing, sorting and retrieving of chemical structures from databases.

Minimum-order stable recursive filter design via the genetic algorithm approach

In this paper, the minimum-order stable recursive filter design problem is proposed and investigated. This problem is playing an important role in pipeline implementation sin signal processing. Here, the existence of a high-order stable recursive filter is proved theoretically, in which the upper bound for the highest order of stable filters is given. Then the minimum-order stable linear predictor is obtained via solving an optimization problem. In this paper, the popular genetic algorithm approach is adopted since it is a heuristic probabilistic optimization technique and has been widely used in engineering designs. Finally, an illustrative example is sued to show the effectiveness of the proposed algorithm.

A study on the encryption algorithm for RFID tag (SEED : 8 Rounds × 64 bits block)

Although it is always weak between RFID Tag and Terminal in focus of the security, there are no security skills in RFID Tag. Recently there are a lot of studying in order to protect it, but because it has some physical limitation of RFID, that is it should be low electric power and high speed, it is impossible to protect with the skills. At present, the methods of RFID security are using a security server, a security policy and security. One of them the most famous skill is the security module, then they has an authentication skill and an encryption skill. In this paper, we designed and implemented after modification original SEED into 8 Round and 64 bits for Tag.

The simple economics of risk-sharing agreements between the NHS and the pharmaceutical industry

The Janssen-Cilag proposal for a risk-sharing agreement regarding bortezomib received a welcome signal from NICE. The Office of Fair Trading report included risk-sharing agreements as an available tool for the National Health Service. Nonetheless, recent discussions have somewhat neglected the economic fundamentals underlying risk-sharing agreements. We argue here that risk-sharing agreements, although attractive due to the principle of paying by results, also entail risks. Too many patients may be put under treatment even with a low success probability. Prices are likely to be adjusted upward, in anticipation of future risk-sharing agreements between the pharmaceutical company and the third-party payer. An available instrument is a verification cost per patient treated, which allows obtaining the first-best allocation of patients to the new treatment, under the risk sharing agreement. Overall, the welfare effects of risk-sharing agreements are ambiguous, and care must be taken with their use.

Glasses' makeup: the simple and the combined effect of color and shape on perceived volume and beverage intake

A Work Project, presented as part of the requirements for the Award of a Masters Degree in Management from the NOVA – School of Business and Economics

Reconstructing historical forest cover change in the Lower Amazon floodplains using the LandTrendr algorithm

ABSTRACTThe Amazon várzeas are an important component of the Amazon biome, but anthropic and climatic impacts have been leading to forest loss and interruption of essential ecosystem functions and services. The objectives of this study were to evaluate the capability of the Landsat-based Detection of Trends in Disturbance and Recovery (LandTrendr) algorithm to characterize changes in várzeaforest cover in the Lower Amazon, and to analyze the potential of spectral and temporal attributes to classify forest loss as either natural or anthropogenic. We used a time series of 37 Landsat TM and ETM+ images acquired between 1984 and 2009. We used the LandTrendr algorithm to detect forest cover change and the attributes of "start year", "magnitude", and "duration" of the changes, as well as "NDVI at the end of series". Detection was restricted to areas identified as having forest cover at the start and/or end of the time series. We used the Support Vector Machine (SVM) algorithm to classify the extracted attributes, differentiating between anthropogenic and natural forest loss. Detection reliability was consistently high for change events along the Amazon River channel, but variable for changes within the floodplain. Spectral-temporal trajectories faithfully represented the nature of changes in floodplain forest cover, corroborating field observations. We estimated anthropogenic forest losses to be larger (1.071 ha) than natural losses (884 ha), with a global classification accuracy of 94%. We conclude that the LandTrendr algorithm is a reliable tool for studies of forest dynamics throughout the floodplain.

Reliability of the interpretation of coronary angiography by the simple visual method

OBJECTIVE: Evaluation of inter and intraobserver reproducibility of by the visual method interpretation of cineangiogram in a clinically based context. METHODS: Five interventional cardiologists analyzed 11 segments of 8 coronary cineangiograms at a two month apart sessions. The percent luminal reduction by the lesions were analyzed by two different classifications: in one (A) the lesions were graded in 0% = absent, 1-50% = mild, 51 - 69 = moderate, and > or = 70% = severe; the other classification (B) was a dichotomic one : <70% = nonsignificant and > or = 70%=significant lesions. The agreement were measured by the kappa (k) index. RESULTS: Interobserver agreement was moderate for classification A (1st measurement, k = 0.36 -- 0.63, k m = 0.49; 2nd measurement, k = 0.39-0.68, k m = 0.52) and good for classification B (1st measurement, k = 0.55-0.73, k m = 0.63; 2nd measurement, k = 0.37-0.82, k m = 0.61). Intraobserver levels of agreement were k = 0.57-0.95 for classification A and 0.62-1.0 for classification B. CONCLUSION: The higher level of reproducibility obtained by adopting the dichotomous criteria usually considered for ischemic limits demonstrates that in the present clinical context, the reliability of the simple visual method is adequate for the identification of patients with clinically significant lesions and candidates for myocardial revascularization procedures.

Mycobacterium avium restriction fragment lenght polymorphism-IS IS1245 and the simple double repetitive element polymerase chain reaction typing method to screen genetic diversity in Brazilian strains

Simple double repetitive element polymerase chain reaction (MaDRE-PCR) and Pvu II-IS1245 restriction fragment length polymorphism (RFLP) typing methods were used to type 41 Mycobacterium avium isolates obtained from 14 Aids inpatients and 10 environment and animals specimens identified among 53 mycobacteria isolated from 237 food, chicken, and pig. All environmental and animals strains showed orphan patterns by both methods. By MaDRE-PCR four patients, with multiple isolates, showed different patterns, suggesting polyclonal infection that was confirmed by RFLP in two of them. This first evaluation of MaDRE-PCR on Brazilian M. avium strains demonstrated that the method seems to be useful as simple and less expensive typing method for screening genetic diversity in M. avium strains on selected epidemiological studies, although with limitation on analysis identical patterns except for one band.