Spectral properties of MCMC algorithms for Bayesian linear regression with generalized hyperbolic errors

We study MCMC algorithms for Bayesian analysis of a linear regression model with generalized hyperbolic errors. The Markov operators associated with the standard data augmentation algorithm and a sandwich variant of that algorithm are shown to be trace-class.     

A theory for the multiset sampler

The multiset sampler (MSS) can be viewed as a new data augmentation scheme and it has been applied successfully to a wide range of statistical inference problems. The key idea of the MSS is to augment the system with a multiset of the missing components, and construct an appropriate joint distribution of the parameters of interest and the missing components to facilitate the inference based on Markov chain Monte Carlo. The standard data augmentation strategy corresponds to the MSS with multiset size one. This paper provides a theoretical comparison of the MSS with different multiset sizes. We show that the MSS converges to the target distribution faster as the multiset size increases. This explains the improvement in convergence rate for the MSS with large multiset sizes over the standard data augmentation scheme.     

Wavelet Galerkin method for eigenvalue problem of a compact integral operator

We consider the approximation of eigenfunctions of a compact integral operator with a smooth kernel by the Galerkin method using wavelet bases. By truncating the Galerkin operator, we obtain a sparse representation of a matrix eigenvalue problem. We prove that the error bounds for the eigenvalues and for the distance between the spectral subspaces are of the orders O(nμ^-2nr) and O(μ^-nr), respectively, where μ⁻ⁿ denotes the norm of the partition and r denotes the order of the wavelet basis functions. By iterating the eigenvectors, we show that the error bounds for the eigenvectors are of the order O(nμ^-2nr). We illustrate our results with numerical results.     

Bayesian and Maximum Likelihood Estimation for Gaussian Processes on an Incomplete Lattice

This article proposes a new approach for Bayesian and maximum likelihood parameter estimation for stationary Gaussian processes observed on a large lattice with missing values. We propose a Markov chain Monte Carlo approach for Bayesian inference, and a Monte Carlo expectation-maximization algorithm for maximum likelihood inference. Our approach uses data augmentation and circulant embedding of the covariance matrix, and provides likelihood-based inference for the parameters and the missing data. Using simulated data and an application to satellite sea surface temperatures in the Pacific Ocean, we show that our method provides accurate inference on lattices of sizes up to 512 × 512, and is competitive with two popular methods: composite likelihood and spectral approximations.     

An Artificial Allocations Based Solution to the Label Switching Problem in Bayesian Analysis of Mixtures of Distributions

Label switching is a well-known problem occurring in MCMC outputs in Bayesian mixture modeling. In this article we propose a formal solution to this problem by considering the space of the artificial allocation variables. We show that there exist certain subsets of the allocation space leading to a class of nonsymmetric distributions that have the same support with the symmetric posterior distribution and can reproduce it by simply permuting the labels. Moreover, we select one of these distributions as a solution to the label switching problem using the simple matching distance between the artificial allocation variables. The proposed algorithm can be used in any mixture model and its computational cost depends on the length of the simulated chain but not on the parameter space dimension. Real and simulated data examples are provided in both univariate and multivariate settings. Supplemental material for this article is available online.     

Multilevel augmentation methods for solving the sine-Gordon equation

In this paper we develop the multilevel augmentation method for solving nonlinear operator equations of the second kind and apply it to solving the one-dimensional sine-Gordon equation. We first give a general setting of the multilevel augmentation method for solving the second kind nonlinear operator equations and prove that the multilevel augmentation method preserves the optimal convergence order of the projection method while reducing computational cost significantly. Then we describe the semi-discrete scheme and the fully-discrete scheme based on multiscale methods for solving the sine-Gordon equation, and apply the multilevel augmentation method to solving the discrete equation. A complete analysis for convergence order is proposed. Finally numerical experiments are presented to confirm the theoretical results and illustrate the efficiency of the method.     

CONVERGENCE RATES FOR A CLASS OF EVOLUTIONARY ALGORITHMS WITH ELITIST STRATEGY

1 IntroductionOne of tlle fundamental issues about the theory of evolutionary algorithIns is their conver-gence. At present, the theoretical basis about evolutionary computation is still yery wcak['--'],especial1y for the researches into the convergeIlce rates of evolutionary a1gorithm8. Accord-illg to the literature, tllere are few results about the convergence rates[4--9], but this research..area i8 very importallt in both theory and practice. Xu and Li[l0] pointed out that the studyof the…     

Eigenvalue problems and fixed point theorems for a class of positive nonlinear operators

We study the eigenvalue problems for a class of positive nonlinear operators defined on a cone in a Banach space. Using projective metric techniques and Schauder’s fixed-point theorem, we establish existence, uniqueness, monotonicity and continuity results for the eigensolutions. Moreover, the method leads to a result on the existence of a unique fixed point of the operator. Applications to nonlinear boundary-value problems, to differential delay equations and to matrix equations are considered.      

Bayesian estimation of stochastic volatility models based on OU processes with marginal Gamma law

This paper discusses practical Bayesian estimation of stochastic volatility models based on OU processes with marginal Gamma laws. Estimation is based on a parameterization which is derived from the Rosiński representation, and has the advantage of being a non-centered parameterization. The parameterization is based on a marked point process, living on the positive real line, with uniformly distributed marks. We define a Markov chain Monte Carlo (MCMC) scheme which enables multiple updates of the latent point process, and generalizes single updating algorithm used earlier. At each MCMC draw more than one point is added or deleted from the latent point process. This is particularly useful for high intensity processes. Furthermore, the article deals with superposition models, where it discuss how the identifiability problem inherent in the superposition model may be avoided by the use of a Markov prior. Finally, applications to simulated data as well as exchange rate data are discussed.     

General Methods for Monitoring Convergence of Iterative Simulations

Abstract

We generalize the method proposed by Gelman and Rubin (1992a) for monitoring the convergence of iterative simulations by comparing between and within variances of multiple chains, in order to obtain a family of tests for convergence. We review methods of inference from simulations in order to develop convergence-monitoring summaries that are relevant for the purposes for which the simulations are used. We recommend applying a battery of tests for mixing based on the comparison of inferences from individual sequences and from the mixture of sequences. Finally, we discuss multivariate analogues, for assessing convergence of several parameters simultaneously.     

Subgeometric ergodicity for continuous-time Markov chains

In this paper, subgeometric ergodicity is investigated for continuous-time Markov chains. Several equivalent conditions, based on the first hitting time or the drift function, are derived as the main theorem. In its corollaries, practical drift criteria are given for ?-ergodicity and computable bounds on subgeometric convergence rates are obtained for stochastically monotone Markov chains. These results are illustrated by examples.     

Cluster Algorithms for Spatial Point Processes with Symmetric and Shift Invariant Interactions

Abstract

In this article, Swendsen–Wang–Wolff algorithms are extended to simulate spatial point processes with symmetric and stationary interactions. Convergence of these algorithms is considered. Some further generalizations of the algorithms are discussed. The ideas presented in this article can also be useful in handling some large and complicated systems.     

Mean Convergence Time of Inhomogeneous Genetic Algorithm with Elitism

The theoretical study of a genetic algorithm (GA) has focused mainly on establishing its convergence in probability and almost always to the global optimum. In this article, we establishsufficient conditions for the finiteness of convergence mean time of the genetic algorithm with elitism. We obtain bounds for the probability of convergence to the global optimum in the first n iterations as a by-product.     

On reparametrization and the Gibbs sampler

Gibbs samplers derived under different parametrizations of the target density can have radically different rates of convergence. In this article, we specify conditions under which reparametrization leaves the convergence rate of a Gibbs chain unchanged. An example illustrates how these results can be exploited in convergence rate analyses.     

Resource augmentation for online bounded space bin packing

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0,1] into a small number of bins of size b1. Its performance is measured by comparing the produced packing against the optimal offline packing of the list L into bins of size 1.We present a complete solution to this problem: For every bin size b1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound ρ(b). Moreover, we prove that no online bounded space algorithm can perform better than ρ(b) in the worst case.     

Numerical comparisons of two effective methods for mixed complementarity problems

Recently there have two different effective methods proposed by Kanzow et al. in (Kanzow, 2001 [8]) and (Kanzow and Petra, 2004 [9]), respectively, which commonly use the Fischer-Burmeister (FB) function to recast the mixed complementarity problem (MCP) as a constrained minimization problem and a nonlinear system of equations, respectively. They all remark that their algorithms may be improved if the FB function is replaced by other NCP functions. Accordingly, in this paper, we employ the generalized Fischer-Burmeister (GFB) where the 2-norm in the FB function is relaxed to a general p-norm (p>1) for the two methods and investigate how much the improvement is by changing the parameter p as well as which method is influenced more when we do so, by the performance profiles of iterations and function evaluations for the two methods with different p on MCPLIB collection.     

Error estimates for Hermite interpolation on spheres

In this paper, we prove convergence rates for spherical spline Hermite interpolation on the sphere S^d−1 via an error estimate given in a technical report by Luo and Levesley. The functionals in the Hermite interpolation are either point evaluations of pseudodifferential operators or rotational differential operators, the desirable feature of these operators being that they map polynomials to polynomials. Convergence rates for certain derivatives are given in terms of maximum point separation.     

求解变分不等式的Ishikawa类迭代算法

本文讨论Banach空间中子集非紧的情况下的变分不等式数值解.提出了求解相应问题的Ishikawa类迭代算法,证明了算法的子列收敛性和全局收敛性.同时也证明了变分不等式解的存在性.     

Robustness and applicability of Markov chain Monte Carlo algorithms for eigenvalue problems

In this paper we analyse applicability and robustness of Markov chain Monte Carlo algorithms for eigenvalue problems. We restrict our consideration to real symmetric matrices.

Almost Optimal Monte Carlo (MAO) algorithms for solving eigenvalue problems are formulated. Results for the structure of both – systematic and probability error are presented. It is shown that the values of both errors can be controlled independently by different algorithmic parameters. The results present how the systematic error depends on the matrix spectrum. The analysis of the probability error is presented. It shows that the close (in some sense) the matrix under consideration is to the stochastic matrix the smaller is this error. Sufficient conditions for constructing robust and interpolation Monte Carlo algorithms are obtained. For stochastic matrices an interpolation Monte Carlo algorithm is constructed.

A number of numerical tests for large symmetric dense matrices are performed in order to study experimentally the dependence of the systematic error from the structure of matrix spectrum. We also study how the probability error depends on the balancing of the matrix.     

Eigentime identity for transient Markov chains

An eigentime identity is proved for transient symmetrizable Markov chains. For general Markov chains, if the trace of Green matrix is finite, then the expectation of first leap time is uniformly bounded, both of which are proved to be equivalent for single birth processes. For birth-death processes, the explicit formulas are presented. As an application, we give the bounds of exponential convergence rates of (sub-) Markov semigroup Pt from l_∞ to l_∞.