Covariance Tapering for Interpolation of Large Spatial Datasets

Interpolation of a spatially correlated random process is used in many scientific areas. The best unbiased linear predictor, often called a kriging predictor in geostatistical science, requires the solution of a (possibly large) linear system based on the covariance matrix of the observations. In this article, we show that tapering the correct covariance matrix with an appropriate compactly supported positive definite function reduces the computational burden significantly and still leads to an asymptotically optimal mean squared error. The effect of tapering is to create a sparse approximate linear system that can then be solved using sparse matrix algorithms. Monte Carlo simulations support the theoretical results. An application to a large climatological precipitation dataset is presented as a concrete and practical illustration.     

Hierarchical Low Rank Approximation of Likelihoods for Large Spatial Datasets

Datasets in the fields of climate and environment are often very large and irregularly spaced. To model such datasets, the widely used Gaussian process models in spatial statistics face tremendous challenges due to the prohibitive computational burden. Various approximation methods have been introduced to reduce the computational cost. However, most of them rely on unrealistic assumptions for the underlying process and retaining statistical efficiency remains an issue. We develop a new approximation scheme for maximum likelihood estimation. We show how the composite likelihood method can be adapted to provide different types of hierarchical low rank approximations that are both computationally and statistically efficient. The improvement of the proposed method is explored theoretically; the performance is investigated by numerical and simulation studies; and the practicality is illustrated through applying our methods to two million measurements of soil moisture in the area of the Mississippi River basin, which facilitates a better understanding of the climate variability. Supplementary material for this article is available online.     

An EM Algorithm for Estimating Equations

This article presents an algorithm for accommodating missing data in situations where a natural set of estimating equations exists for the complete data setting. The complete data estimating equations can correspond to the score functions from a standard, partial, or quasi-likelihood, or they can be generalized estimating equations (GEEs). In analogy to the EM, which is a special case, the method is called the ES algorithm, because it iterates between an E-Step wherein functions of the complete data are replaced by their expected values, and an S-Step where these expected values are substituted into the complete-data estimating equation, which is then solved. Convergence properties of the algorithm are established by appealing to general theory for iterative solutions to nonlinear equations. In particular, the ES algorithm (and indeed the EM) are shown to correspond to examples of nonlinear Gauss-Seidel algorithms. An added advantage of the approach is that it yields a computationally simple method for estimating the variance of the resulting parameter estimates.     

Statistical Properties of Covariance Tapers

Compactly supported autocovariance functions reduce computations needed for estimation and prediction under Gaussian process models, which are commonly used to model spatial and spatial-temporal data. A critical issue in using such models is the loss in statistical efficiency caused when the true autocovariance function is not compactly supported. Theoretical results indicate the value of specifying the local behavior of the process correctly. One way to obtain a compactly supported autocovariance function that has similar local behavior to an autocovariance function K of interest is to multiply K by some smooth compactly supported autocovariance function, which is called covariance tapering. This work extends previous theoretical results showing that covariance tapering has some asymptotic optimality properties as the number of observations in a fixed and bounded domain increases. However, numerical experiments show that for purposes of parameter estimation, covariance tapering often does not work as well as the simple alternative of breaking the observations into blocks and ignoring dependence across blocks. When covariance tapering is used for spatial prediction, predictions near the boundary of the observation domain are affected most. This article proposes an approach to modifying the taper to ameliorate this edge effect. In addition, a justification for a specific approach to carrying out conditional simulations based on tapered covariances is given. Supplementary materials for this article are available online.     

A Multiresolution Gaussian Process Model for the Analysis of Large Spatial Datasets

We develop a multiresolution model to predict two-dimensional spatial fields based on irregularly spaced observations. The radial basis functions at each level of resolution are constructed using a Wendland compactly supported correlation function with the nodes arranged on a rectangular grid. The grid at each finer level increases by a factor of two and the basis functions are scaled to have a constant overlap. The coefficients associated with the basis functions at each level of resolution are distributed according to a Gaussian Markov random field (GMRF) and take advantage of the fact that the basis is organized as a lattice. Several numerical examples and analytical results establish that this scheme gives a good approximation to standard covariance functions such as the Matérn and also has flexibility to fit more complicated shapes. The other important feature of this model is that it can be applied to statistical inference for large spatial datasets because key matrices in the computations are sparse. The computational efficiency applies to both the evaluation of the likelihood and spatial predictions.     

An Inversion-Free Estimating Equations Approach for Gaussian Process Models

One of the scalability bottlenecks for the large-scale usage of Gaussian processes is the computation of the maximum likelihood estimates of the parameters of the covariance matrix. The classical approach requires a Cholesky factorization of the dense covariance matrix for each optimization iteration. In this work, we present an estimating equations approach for the parameters of zero-mean Gaussian processes. The distinguishing feature of this approach is that no linear system needs to be solved with the covariance matrix. Our approach requires solving an optimization problem for which the main computational expense for the calculation of its objective and gradient is the evaluation of traces of products of the covariance matrix with itself and with its derivatives. For many problems, this is an O(nlog?n) effort, and it is always no larger than O(n²). We prove that when the covariance matrix has a bounded condition number, our approach has the same convergence rate as does maximum likelihood in that the Godambe information matrix of the resulting estimator is at least as large as a fixed fraction of the Fisher information matrix. We demonstrate the effectiveness of the proposed approach on two synthetic examples, one of which involves more than 1 million data points.     

Tensor methods for large sparse systems of nonlinear equations

This paper introduces tensor methods for solving large sparse systems of nonlinear equations. Tensor methods for nonlinear equations were developed in the context of solving small to medium-sized dense problems. They base each iteration on a quadratic model of the nonlinear equations, where the second-order term is selected so that the model requires no more derivative or function information per iteration than standard linear model-based methods, and hardly more storage or arithmetic operations per iteration. Computational experiments on small to medium-sized problems have shown tensor methods to be considerably more efficient than standard Newton-based methods, with a particularly large advantage on singular problems. This paper considers the extension of this approach to solve large sparse problems. The key issue considered is how to make efficient use of sparsity in forming and solving the tensor model problem at each iteration. Accomplishing this turns out to require an entirely new way of solving the tensor model that successfully exploits the sparsity of the Jacobian, whether the Jacobian is nonsingular or singular. We develop such an approach and, based upon it, an efficient tensor method for solving large sparse systems of nonlinear equations. Test results indicate that this tensor method is significantly more efficient and robust than an efficient sparse Newton-based method, in terms of iterations, function evaluations, and execution time. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Work supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Computational and Technology Research, US Department of Energy, under Contract W-31-109-Eng-38, by the National Aerospace Agency under Purchase Order L25935D, and by the National Science Foundation, through the Center for Research on Parallel Computation, under Cooperative Agreement No. CCR-9120008.Research supported by AFOSR Grants No. AFOSR-90-0109 and F49620-94-1-0101, ARO Grants No. DAAL03-91-G-0151 and DAAH04-94-G-0228, and NSF Grant No. CCR-9101795.     

Efficient Covariance Approximations for Large Sparse Precision Matrices

The use of sparse precision (inverse covariance) matrices has become popular because they allow for efficient algorithms for joint inference in high-dimensional models. Many applications require the computation of certain elements of the covariance matrix, such as the marginal variances, which may be nontrivial to obtain when the dimension is large. This article introduces a fast Rao–Blackwellized Monte Carlo sampling-based method for efficiently approximating selected elements of the covariance matrix. The variance and confidence bounds of the approximations can be precisely estimated without additional computational costs. Furthermore, a method that iterates over subdomains is introduced, and is shown to additionally reduce the approximation errors to practically negligible levels in an application on functional magnetic resonance imaging data. Both methods have low memory requirements, which is typically the bottleneck for competing direct methods.     

Estimating Equations with Nuisance Parameters: Theory and Applications

In a variety of statistical problems the estimate _n of a parameter is defined as the root of a generalized estimating equation G_n(_nn)=0 where _n is an estimate of a nuisance parameter . We give sufficient conditions for the asymptotic normality of #x0398;_n defined in this way and derive their asymptotic distribution. A circumstance under which the asymptotic distribution of #x0398;_n will not be influenced by that of _n) is noted. As an example, we consider a covariance structure analysis in which both the population mean and the population fourth-order moment are nuisance parameters. Applications to pseudo maximum likelihood, generalized least squares with estimated weights, and M-estimation with an estimated scale parameter are discussed briefly.     

On element-by-element Schur complement approximations

We discuss a methodology to construct sparse approximations of Schur complements of two-by-two block matrices arising in Finite Element discretizations of partial differential equations. Earlier results from [2] are extended to more general symmetric positive definite matrices of two-by-two block form. The applicability of the method for general symmetric and nonsymmetric matrices is analysed. The paper demonstrates the applicability of the presented method providing extensive numerical experiments.     

Approximate Inverse Preconditioners for Some Large Dense Random Electrostatic Interaction Matrices

A sparse mesh-neighbour based approximate inverse preconditioner is proposed for a type of dense matrices whose entries come from the evaluation of a slowly decaying free space Green’s function at randomly placed points in a unit cell. By approximating distant potential fields originating at closely spaced sources in a certain way, the preconditioner is given properties similar to, or better than, those of a standard least squares approximate inverse preconditioner while its setup cost is only that of a diagonal block approximate inverse preconditioner. Numerical experiments on iterative solutions of linear systems with up to four million unknowns illustrate how the new preconditioner drastically outperforms standard approximate inverse preconditioners of otherwise similar construction, and especially so when the preconditioners are very sparse. AMS subject classification (2000) 65F10, 65R20, 65F35, 78A30     

An initial-value method for the determinantal equations of vibrations and flutter

In many investigations in mechanics, we must solve the equation detB()=0, where the elements of the matrixB are general functions of . A method of solution is proposed, and results of numerical experiments are given.     

Newton Methods for Quasidifferentiable Equations and Their Convergence

The Newton method and the inexact Newton method for solving quasidifferentiable equations via the quasidifferential are investigated. The notion of Q-semismoothness for a quasidifferentiable function is proposed. The superlinear convergence of the Newton method proposed by Zhang and Xia is proved under the Q-semismooth assumption. An inexact Newton method is developed and its linear convergence is shown.Project sponsored by Shanghai Education Committee Grant 04EA01 and by Shanghai Government Grant T0502.     

增算子不动点的迭代求法及其应用

设E是Banach空间 ,本文在空间C[I,E]中得到了若干新的增算子不动点的存在性定理及其不动点的迭代求法 .作为应用 ,我们研究了Banach空间上非线性积分方程最大解和最小解及其单调迭代方法     

Truncated Trust Region Methods Based on Preconditioned Iterative Subalgorithms for Large Sparse Systems of Nonlinear Equations

This paper is devoted to globally convergent methods for solving large sparse systems of nonlinear equations with an inexact approximation of the Jacobian matrix. These methods include difference versions of the Newton method and various quasi-Newton methods. We propose a class of trust region methods together with a proof of their global convergence and describe an implementable globally convergent algorithm which can be used as a realization of these methods. Considerable attention is concentrated on the application of conjugate gradient-type iterative methods to the solution of linear subproblems. We prove that both the GMRES and the smoothed COS well-preconditioned methods can be used for the construction of globally convergent trust region methods. The efficiency of our algorithm is demonstrated computationally by using a large collection of sparse test problems.     

A family of iterative methods for computing the approximate inverse of a square matrix and inner inverse of a non-square matrix

Based on a quadratical convergence method, a family of iterative methods to compute the approximate inverse of square matrix are presented. The theoretical proofs and numerical experiments show that these iterative methods are very effective. And, more importantly, these methods can be used to compute the inner inverse and their convergence proofs are given by fundamental matrix tools.     

Residual methods for the large-scale matrix pth root and some related problems

The problem of finding the pth root of a matrix has received special attention in the last few years. Standard approaches for this problem include and combine some variations of Newton’s method, which in turn involve matrix factorizations that, in general, are not suitable for large-scale problems. Motivated by some recently developed low-cost iterative schemes for nonlinear problems, we consider and analyze specialized residual methods that only require a few matrix-matrix products per iteration, and hence are suitable for the large-scale case. As a by-product we also discuss the advantages of residual methods for general nonlinear problems whose variables separate. Preliminary and encouraging numerical results are presented for computing pth roots of large-scale symmetric and positive definite matrices, for different values of p.     

Gradient based and least squares based iterative algorithms for matrix equations AXB + CXD = F

This paper develops a gradient based and a least squares based iterative algorithms for solving matrix equation AXB + CX^TD = F. The basic idea is to decompose the matrix equation (system) under consideration into two subsystems by applying the hierarchical identification principle and to derive the iterative algorithms by extending the iterative methods for solving Ax = b and AXB = F. The analysis shows that when the matrix equation has a unique solution (under the sense of least squares), the iterative solution converges to the exact solution for any initial values. A numerical example verifies the proposed theorems.     

广义时滞微分方程的渐近稳定性和数值分析

考虑了广义时滞微分方程的初值问题,分析了用线性多步法求解一类广义滞后型微分系统数值解的稳定性,在一定的Lagrange插值条件下,给出并证明了求解广义滞后型微分系统的线性多步法数值稳定的充分必要条件。