Variational Bayes With Intractable Likelihood

Variational Bayes (VB) is rapidly becoming a popular tool for Bayesian inference in statistical modeling. However, the existing VB algorithms are restricted to cases where the likelihood is tractable, which precludes their use in many interesting situations such as in state--space models and in approximate Bayesian computation (ABC), where application of VB methods was previously impossible. This article extends the scope of application of VB to cases where the likelihood is intractable, but can be estimated unbiasedly. The proposed VB method therefore makes it possible to carry out Bayesian inference in many statistical applications, including state--space models and ABC. The method is generic in the sense that it can be applied to almost all statistical models without requiring too much model-based derivation, which is a drawback of many existing VB algorithms. We also show how the proposed method can be used to obtain highly accurate VB approximations of marginal posterior distributions. Supplementary material for this article is available online.     

Insights into the interior-point methods

In this paper, we study the search directions of three important interior-point algorithms, namely, the primal-affine scaling method (with logarithmic barrier function), the dual-affine scaling method (with logarithmic barrier function), and the primal-dual interior point method. From an algebraic point of view, we show that the search directions of these three algorithms are merely Newton directions along three different paths that lead to a solution of the Karush-Kuhn-Tucker conditions of a given linear programming problem. From a geometric point of view, we show that these directions can be obtained by solving certain well-defined subproblems. Both views provide a general platform for studying the existing interior-point methods and deriving new interior-point algorithms. We illustrate the derivation of new interior-point algorithms by replacing the logarithmic barrier function with an entropic barrier function. The results have been generalized and discussed.This work is partially supported by the North Carolina Supercomputing Center 1990 Cray Grant Program sponsored by Cray Research.     

修正的TV-Stokes模型的新快速算法

基于Tai等人的前期工作,本文研究修正的TV-Stokes图像去噪模型,提出一些新的求解该两步模型的快速算法.我们利用对偶形式和多重网格方法得到一个求解第1步的快速算法.给出另外一种新的求解光滑的切向量场的保不可压性质的算法.在第2步中,我们提出一类有效的全新算法:首先通过计算Poisson方程得到具有光滑法向量场的函数g,然后利用Jia和Zhao的方法得到恢复的图像.新算法的运算速度非常快,用于图像恢复的CPU时间少于0.1 s.数值结果显示新的快速算法是有效的和稳定的,恢复图像的质量也超过了一般去噪方法.     

On Early Stopping in Gradient Descent Learning

In this paper we study a family of gradient descent algorithms to approximate the regression function from reproducing kernel Hilbert spaces (RKHSs), the family being characterized by a polynomial decreasing rate of step sizes (or learning rate). By solving a bias-variance trade-off we obtain an early stopping rule and some probabilistic upper bounds for the convergence of the algorithms. We also discuss the implication of these results in the context of classification where some fast convergence rates can be achieved for plug-in classifiers. Some connections are addressed with Boosting, Landweber iterations, and the online learning algorithms as stochastic approximations of the gradient descent method.     

Decomposition method for solving multi-species reactive transport problems coupled with first-order kinetics applicable to a chain with identical reaction rates

A new method for decomposing of multiple solute transport equations, coupled by first-order reactions, is developed. The approach is based on the semigroup theory and reduces the multi-species problem to single-species equations with various initial and boundary conditions. Analytical formulas are derived for all reactants. This new method overcomes some of the limitations that were implicit in previously published algorithms. More exactly, the derivation of closed formulas for a reaction chain with identical reaction rates is possible. The proposed approach is flexible for solving one-, two- or three-dimensional advection-dispersion systems. The methodology is demonstrated on the reductive biodegradation of chlorinated solvents, such as tetrachloroethene (PCE) and trichloroethene (TCE).     

Fast algorithms for floating-point interval matrix multiplication

We discuss several methods for real interval matrix multiplication. First, earlier studies of fast algorithms for interval matrix multiplication are introduced: naive interval arithmetic, interval arithmetic by midpoint-radius form by Oishi-Rump and its fast variant by Ogita-Oishi. Next, three new and fast algorithms are developed. The proposed algorithms require one, two or three matrix products, respectively. The point is that our algorithms quickly predict which terms become dominant radii in interval computations. We propose a hybrid method to predict which algorithm is suitable for optimizing performance and width of the result. Numerical examples are presented to show the efficiency of the proposed algorithms.     

Reconstructing small perturbations of an obstacle for acoustic waves from boundary measurements on the perturbed shape itself

We derive relationships between the shape deformation of an impenetrable obstacle and boundary measurements of scattering fields on the perturbed shape itself. Our derivation is rigorous by using a systematic way, based on layer potential techniques and the field expansion (FE) method (formal derivation). We extend these techniques to derive asymptotic expansions of the Dirichlet-to-Neumann (DNO) and Neumann-to-Dirichlet (NDO) operators in terms of the small perturbations of the obstacle as well as relationships between the shape deformation of an obstacle and boundary measurements of DNO or NDO on the perturbed shape itself. All relationships lead us to very effective algorithms for determining lower order Fourier coefficients of the shape perturbation of the obstacle.     

The Equality Constrained Indefinite Least Squares Problem: Theory and Algorithms

We present theory and algorithms for the equality constrained indefinite least squares problem, which requires minimization of an indefinite quadratic form subject to a linear equality constraint. A generalized hyperbolic QR factorization is introduced and used in the derivation of perturbation bounds and to construct a numerical method. An alternative method is obtained by employing a generalized QR factorization in combination with a Cholesky factorization. Rounding error analysis is given to show that both methods have satisfactory numerical stability properties and numerical experiments are given for illustration. This work builds on recent work on the unconstrained indefinite least squares problem by Chandrasekaran, Gu, and Sayed and by the present authors.     

PARALLEL IMPLEMENTATIONS OF THE FAST SWEEPING METHOD

The fast sweeping method is an efficient iterative method for hyperbolic problems. It combines Gauss-Seidel iterations with alternating sweeping orderings. In this paper several parallel implementations of the fast sweeping method are presented. These parallel algorithms are simple and efficient due to the causality of the underlying partial different equations. Numerical examples are used to verify our algorithms.     

Approximation of kernel matrices by circulant matrices and its application in kernel selection methods

This paper focuses on developing fast numerical algorithms for selection of a kernel optimal for a given training data set. The optimal kernel is obtained by minimizing a cost functional over a prescribed set of kernels. The cost functional is defined in terms of a positive semi-definite matrix determined completely by a given kernel and the given sampled input data. Fast computational algorithms are developed by approximating the positive semi-definite matrix by a related circulant matrix so that the fast Fourier transform can apply to achieve a linear or quasi-linear computational complexity for finding the optimal kernel. We establish convergence of the approximation method. Numerical examples are presented to demonstrate the approximation accuracy and computational efficiency of the proposed methods.     

Certification aspects of the fast gradient method for solving the dual of parametric convex programs

This paper examines the computational complexity certification of the fast gradient method for the solution of the dual of a parametric convex program. To this end, a lower iteration bound is derived such that for all parameters from a compact set a solution with a specified level of suboptimality will be obtained. For its practical importance, the derivation of the smallest lower iteration bound is considered. In order to determine it, we investigate both the computation of the worst case minimal Euclidean distance between an initial iterate and a Lagrange multiplier and the issue of finding the largest step size for the fast gradient method. In addition, we argue that optimal preconditioning of the dual problem cannot be proven to decrease the smallest lower iteration bound. The findings of this paper are of importance in embedded optimization, for instance, in model predictive control.     

Identification of small amplitude perturbations in the electromagnetic parameters from partial dynamic boundary measurements

We consider the inverse problem of reconstructing small amplitude perturbations in the conductivity for the wave equation from partial (on part of the boundary) dynamic boundary measurements. Through construction of appropriate test functions by a geometrical control method we provide a rigorous derivation of the inverse Fourier transform of the perturbations in the conductivity as the leading order of an appropriate averaging of the partial dynamic boundary perturbations. This asymptotic formula is generalized to the full time-dependent Maxwell's equations. Our formulae may be expected to lead to very effective computational identification algorithms, aimed at determining electromagnetic parameters of an object based on partial dynamic boundary measurements.     

Fast algorithms for hierarchically semiseparable matrices

Semiseparable matrices and many other rank‐structured matrices have been widely used in developing new fast matrix algorithms. In this paper, we generalize the hierarchically semiseparable (HSS) matrix representations and propose some fast algorithms for HSS matrices. We represent HSS matrices in terms of general binary HSS trees and use simplified postordering notation for HSS forms. Fast HSS algorithms including new HSS structure generation and HSS form Cholesky factorization are developed. Moreover, we provide a new linear complexity explicit ULV factorization algorithm for symmetric positive definite HSS matrices with a low‐rank property. The corresponding factors can be used to solve the HSS systems also in linear complexity. Numerical examples demonstrate the efficiency of the algorithms. All these algorithms have nice data locality. They are useful in developing fast‐structured numerical methods for large discretized PDEs (such as elliptic equations), integral equations, eigenvalue problems, etc. Some applications are shown. Copyright © 2009 John Wiley & Sons, Ltd.     

非线性玻尔兹曼方程的傅里叶谱方法

玻尔兹曼方程作为空气动理学中最基本的方程之一,是连接微观牛顿力学和宏观连续介质力学的重要桥梁.该方程描述了一个由大量粒子组成的复杂系统的非平衡态时间演化:除了基本的输运项,其最重要的特性是粒子间的相互碰撞由一个高维,非局部且非线性的积分算子来描述,从而给玻尔兹曼方程的数值求解带来非常大的挑战.在过去的二十年间,基于傅里叶级数的谱方法成为了数值求解玻尔兹曼方程的一种很受欢迎且有效的确定性算法.这主要归功于谱方法的高精度及它可以被快速傅里叶变换加速的特质.本文将回顾玻尔兹曼方程的傅里叶谱方法,具体包括方法的导出,稳定性和收敛性分析,快速算法,以及在一大类基于碰撞的空气动理学方程中的推广.     

一类奇性积分方程的多尺度配置快速算法

This paper develops fast multiscale collocation methods for a class of Fredholm integral equations of the second kind with singular kernels. A truncation strategy for the coefficient matrix of the corresponding discrete system is proposed, which forms a basis for fast algorithms. The convergence, stability and computational complexity of these algorithms are analyzed.     

A fast direct algorithm for implementing a high-order finite element method on rectangles as applied to boundary value problems for the Poisson equation

Fast direct and inverse algorithms for expansion in terms of eigenvectors of one-dimensional eigenvalue problems for a high-order finite element method (FEM) are proposed based on the fast discrete Fourier transform. They generalize logarithmically optimal Fourier algorithms for solving boundary value problems for Poisson-type equations on rectangular meshes to high-order FEM. The algorithms can be extended to the multidimensional case and can be applied to nonstationary problems.     

Complexity Theory for Lie-Group Solvers

Commencing with a brief survey of Lie-group theory and differential equations evolving on Lie groups, we describe a number of numerical algorithms designed to respect Lie-group structure: Runge–Kutta–Munthe-Kaas schemes, Fer and Magnus expansions. This is followed by derivation of the computational cost of Fer and Magnus expansions, whose conclusion is that for order four, six, and eight an appropriately discretized Magnus method is always cheaper than a Fer method of the same order. Each Lie-group method of the kind surveyed in this paper requires the computation of a matrix exponential. Classical methods, e.g., Krylov-subspace and rational approximants, may fail to map elements in a Lie algebra to a Lie group. Therefore we survey a number of approximants based on the splitting approach and demonstrate that their cost is compatible (and often superior) to classical methods.     

Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem

M-convex functions, introduced by Murota (Adv. Math. 124 (1996) 272; Math. Prog. 83 (1998) 313), enjoy various desirable properties as “discrete convex functions.” In this paper, we propose two new polynomial-time scaling algorithms for the minimization of an M-convex function. Both algorithms apply a scaling technique to a greedy algorithm for M-convex function minimization, and run as fast as the previous minimization algorithms. We also specialize our scaling algorithms for the resource allocation problem which is a special case of M-convex function minimization.     

Fast state space algorithms for matrix Nehari and Nehari-Takagi interpolation problems

Numerical algorithms with complexityO(n ²) operations are proposed for solving matrix Nehari and Nehari-Takagi problems withn interpolation points. The algorithms are based on explicit formulas for the solutions and on theorems about cascade decomposition of rational matrix function given in a state space form. The method suggests also fast algorithms for LDU factorizations of structured matrices. The numerical behavior of the designed algorithms is studied for a wide set of examples.