Likelihood-Based Analysis of Linear State-Space Models Using the Cholesky Decomposition

Data associated with the linear state-space model can be assembled as a matrix whose Cholesky decomposition leads directly to a likelihood evaluation. It is possible to build several matrices for which this is true. Although the chosen matrix or assemblage can be very large, rows and columns can usually be rearranged so that sparse matrix factorization is feasible and provides an alternative to the Kalman filter. Moreover, technology for calculating derivatives of the log-likelihood using backward differentiation is available, and hence it is possible to maximize the likelihood using the Newton–Raphson approach. Emphasis is given to the estimation of dispersion parameters by both maximum likelihood and restricted maximum likelihood, and an illustration is provided for an ARMA(1,1) model.     

Statistically and Computationally Efficient Estimating Equations for Large Spatial Datasets

For Gaussian process models, likelihood-based methods are often difficult to use with large irregularly spaced spatial datasets, because exact calculations of the likelihood for n observations require O(n³) operations and O(n²) memory. Various approximation methods have been developed to address the computational difficulties. In this article, we propose new, unbiased estimating equations (EE) based on score equation approximations that are both computationally and statistically efficient. We replace the inverse covariance matrix that appears in the score equations by a sparse matrix to approximate the quadratic forms, then set the resulting quadratic forms equal to their expected values to obtain unbiased EE. The sparse matrix is constructed by a sparse inverse Cholesky approach to approximate the inverse covariance matrix. The statistical efficiency of the resulting unbiased EE is evaluated both in theory and by numerical studies. Our methods are applied to nearly 90,000 satellite-based measurements of water vapor levels over a region in the Southeast Pacific Ocean.     

On symbolic factorization of partitioned sparse symmetric matrices

Partitioning a sparse matrix A is a useful device employed by a number of sparse matrix techniques. An important problem that arises in connection with some of these methods is to determine the block structure of the Cholesky factor L of A, given the partitioned A. For the scalar case, the problem of determining the structure of L from A, so-called symbolic factorization, has been extensively studied. In this paper we study the generalization of this problem to the block case. The problem is interesting because an assumption relied on in the scalar case no longer holds; specifically, the product of two nonzero scalars is always nonzero, but the product of two nonnull sparse matrices may yield a zero matrix. Thus, applying the usual symbolic factorization techniques to a partitioned matrix, regarding each submatrix as a scalar, may yield a block structure of L which is too full. In this paper an efficient algorithm is provided for determining the block structure of the Cholesky factor of a partitioned matrix A, along with some bounds on the execution time of the algorithm.     

A Class of Incomplete Orthogonal Factorization Methods. I: Methods and Theories

We present a class of incomplete orthogonal factorization methods based on Givens rotations for large sparse unsymmetric matrices. These methods include: Incomplete Givens Orthogonalization (IGO-method) and its generalisation (GIGO-method), which drop entries from the incomplete orthogonal and upper triangular factors by position; Threshold Incomplete Givens Orthogonalization (TIGO()-method), which drops entries dynamically by their magnitudes; and its generalisation (GTIGO(,p)-method), which drops entries dynamically by both their magnitudes and positions. Theoretical analyses show that these methods can produce a nonsingular sparse incomplete upper triangular factor and either a complete orthogonal factor or a sparse nonsingular incomplete orthogonal factor for a general nonsingular matrix. Therefore, these methods can potentially generate efficient preconditioners for Krylov subspace methods for solving large sparse systems of linear equations. Moreover, the upper triangular factor is an incomplete Cholesky factorization preconditioner for the normal equations matrix from least-squares problems.     

Sparse Steinian Covariance Estimation

We consider a new method for sparse covariance matrix estimation which is motivated by previous results for the so-called Stein-type estimators. Stein proposed a method for regularizing the sample covariance matrix by shrinking together the eigenvalues; the amount of shrinkage is chosen to minimize an unbiased estimate of the risk (UBEOR) under the entropy loss function. The resulting estimator has been shown in simulations to yield significant risk reductions over the maximum likelihood estimator. Our method extends the UBEOR minimization problem by adding an ?₁ penalty on the entries of the estimated covariance matrix, which encourages a sparse estimate. For a multivariate Gaussian distribution, zeros in the covariance matrix correspond to marginal independences between variables. Unlike the ?₁-penalized Gaussian likelihood function, our penalized UBEOR objective is convex and can be minimized via a simple block coordinate descent procedure. We demonstrate via numerical simulations and an analysis of microarray data from breast cancer patients that our proposed method generally outperforms other methods for sparse covariance matrix estimation and can be computed efficiently even in high dimensions.     

Optimization of unconstrained functions with sparse hessian matrices-newton-type methods

Newton-type methods for unconstrained optimization problems have been very successful when coupled with a modified Cholesky factorization to take into account the possible lack of positive-definiteness in the Hessian matrix. In this paper we discuss the application of these method to large problems that have a sparse Hessian matrix whose sparsity is known a priori. Quite often it is difficult, if not impossible, to obtain an analytic representation of the Hessian matrix. Determining the Hessian matrix by the standard method of finite-differences is costly in terms of gradient evaluations for large problems. Automatic procedures that reduce the number of gradient evaluations by exploiting sparsity are examined and a new procedure is suggested. Once a sparse approximation to the Hessian matrix has been obtained, there still remains the problem of solving a sparse linear system of equations at each iteration. A modified Cholesky factorization can be used. However, many additional nonzeros (fill-in) may be created in the factors, and storage problems may arise. One way of approaching this problem is to ignore fill-in in a systematic manner. Such technique are calledpartial factorization schemes. Various existing partial factorization are analyzed and three new ones are developed. The above algorithms were tested on a set of problems. The overall conclusions were that these methods perfom well in practice.     

Detection of near-singularity in Cholesky and LDLT factorizations

In sparse matrix applications it is often important to implement the Cholesky and LDL^T factorization methods without pivoting in order to avoid excess fillin. We consider methods for detection of a nearly singular matrix by means of these factorizations without pivoting and demonstrate that a technique based on estimation of the smallest eigenvalue via inverse iteration will always reveal a nearly singular matrix.     

Efficient Adaptive MCMC Through Precision Estimation

The performance of Markov chain Monte Carlo (MCMC) algorithms like the Metropolis Hastings Random Walk (MHRW) is highly dependent on the choice of scaling matrix for the proposal distributions. A popular choice of scaling matrix in adaptive MCMC methods is to use the empirical covariance matrix (ECM) of previous samples. However, this choice is problematic if the dimension of the target distribution is large, since the ECM then converges slowly and is computationally expensive to use. We propose two algorithms to improve convergence and decrease computational cost of adaptive MCMC methods in cases when the precision (inverse covariance) matrix of the target density can be well-approximated by a sparse matrix. The first is an algorithm for online estimation of the Cholesky factor of a sparse precision matrix. The second estimates the sparsity structure of the precision matrix. Combining the two algorithms allows us to construct precision-based adaptive MCMC algorithms that can be used as black-box methods for densities with unknown dependency structures. We construct precision-based versions of the adaptive MHRW and the adaptive Metropolis adjusted Langevin algorithm and demonstrate the performance of the methods in two examples. Supplementary materials for this article are available online.     

Avoiding numerical cancellation in the interior point method for solving semidefinite programs

 The matrix variables in a primal-dual pair of semidefinite programs are getting increasingly ill-conditioned as they approach a complementary solution. Multiplying the primal matrix variable with a vector from the eigenspace of the non-basic part will therefore result in heavy numerical cancellation. This effect is amplified by the scaling operation in interior point methods. A complete example illustrates these numerical issues. In order to avoid numerical problems in interior point methods, we propose to maintain the matrix variables in a Cholesky form. We discuss how the factors of the v-space Cholesky form can be updated after a main iteration of the interior point method with Nesterov-Todd scaling. An analogue for second order cone programming is also developed. Numerical results demonstrate the success of this approach. Received: June 16, 2001 / Accepted: April 5, 2002 Published online: October 9, 2002 Key Words. semidefinite programming – second order cone programming Mathematics Subject Classification (2000): 90C22, 90C20     

Computation of connection coefficients and measure modifications for orthogonal polynomials

We observe that polynomial measure modifications for families of univariate orthogonal polynomials imply sparse connection coefficient relations. We therefore propose connecting L ² expansion coefficients between a polynomial family and a modified family by a sparse transformation. Accuracy and conditioning of the connection and its inverse are explored. The connection and recurrence coefficients can simultaneously be obtained as the Cholesky decomposition of a matrix polynomial involving the Jacobi matrix; this property extends to continuous, non-polynomial measure modifications on finite intervals. We conclude with an example of a useful application to families of Jacobi polynomials with parameters (γ,δ) where the fast Fourier transform may be applied in order to obtain expansion coefficients whenever 2γ and 2δ are odd integers.     

Correlative Sparsity in Primal-Dual Interior-Point Methods for LP,SDP, and SOCP

Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient matrix of the equation which is determined by the sparsity of an optimization problem (linear program, semidefinite program or second-order cone program). We show if an optimization problem is correlatively sparse, then the coefficient matrix of the Schur complement equation inherits the sparsity, and a sparse Cholesky factorization applied to the matrix results in no fill-in. S. Kim’s research was supported by Kosef R01-2005-000-10271-0 and KRF-2006-312-C00062.     

Estimation of a Multivariate Normal Covariance Matrix with Staircase Pattern Data

In this paper, we study the problem of estimating a multivariate normal covariance matrix with staircase pattern data. Two kinds of parameterizations in terms of the covariance matrix are used. One is Cholesky decomposition and another is Bartlett decomposition. Based on Cholesky decomposition of the covariance matrix, the closed form of the maximum likelihood estimator (MLE) of the covariance matrix is given. Using Bayesian method, we prove that the best equivariant estimator of the covariance matrix with respect to the special group related to Cholesky decomposition uniquely exists under the Stein loss. Consequently, the MLE of the covariance matrix is inadmissible under the Stein loss. Our method can also be applied to other invariant loss functions like the entropy loss and the symmetric loss. In addition, based on Bartlett decomposition of the covariance matrix, the Jeffreys prior and the reference prior of the covariance matrix with staircase pattern data are also obtained. Our reference prior is different from Berger and Yang’s reference prior. Interestingly, the Jeffreys prior with staircase pattern data is the same as that with complete data. The posterior properties are also investigated. Some simulation results are given for illustration.     

Cholesky decomposition of a positive semidefinite matrix with known kernel

The Cholesky decomposition of a symmetric positive semidefinite matrix A is a useful tool for solving the related consistent system of linear equations or evaluating the action of a generalized inverse, especially when A is relatively large and sparse. To use the Cholesky decomposition effectively, it is necessary to identify reliably the positions of zero rows or columns of the factors and to choose these positions so that the nonsingular submatrix of A of the maximal rank is reasonably conditioned. The point of this note is to show how to exploit information about the kernel of A to accomplish both tasks. The results are illustrated by numerical experiments.     

Incremental Norm Estimation for Dense and Sparse Matrices

We present an incremental approach to 2-norm estimation for triangular matrices. Our investigation covers both dense and sparse matrices which can arise for example from a QR, a Cholesky or a LU factorization. If the explicit inverse of a triangular factor is available, as in the case of an implicit version of the LU factorization, we can relate our results to incremental condition estimation (ICE). Incremental norm estimation (INE) extends directly from the dense to the sparse case without needing the modifications that are necessary for the sparse version of ICE. INE can be applied to complement ICE, since the product of the two estimates gives an estimate for the matrix condition number. Furthermore, when applied to matrix inverses, INE can be used as the basis of a rank-revealing factorization.     

Computing Row and Column Counts for Sparse QR and LU Factorization

We present algorithms to determine the number of nonzeros in each row and column of the factors of a sparse matrix, for both the QR factorization and the LU factorization with partial pivoting. The algorithms use only the nonzero structure of the input matrix, and run in time nearly linear in the number of nonzeros in that matrix. They may be used to set up data structures or schedule parallel operations in advance of the numerical factorization.The row and column counts we compute are upper bounds on the actual counts. If the input matrix is strong Hall and there is no coincidental numerical cancellation, the counts are exact for QR factorization and are the tightest bounds possible for LU factorization.These algorithms are based on our earlier work on computing row and column counts for sparse Cholesky factorization, plus an efficient method to compute the column elimination tree of a sparse matrix without explicitly forming the product of the matrix and its transpose.This revised version was published online in October 2005 with corrections to the Cover Date.     

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.     

Approximations to the Log-Likelihood Function in the Nonlinear Mixed-Effects Model

Abstract

Nonlinear mixed-effects models have received a great deal of attention in the statistical literature in recent years because of the flexibility they offer in handling the unbalanced repeated-measures data that arise in different areas of investigation, such as pharmacokinetics and economics. Several different methods for estimating the parameters in nonlinear mixed-effects model have been proposed. We concentrate here on two of them—maximum likelihood and restricted maximum likelihood. A rather complex numerical issue for (restricted) maximum likelihood estimation in nonlinear mixed-effects models is the evaluation of the log-likelihood function of the data, because it involves the evaluation of a multiple integral that, in most cases, does not have a closed-form expression. We consider here four different approximations to the log-likelihood, comparing their computational and statistical properties. We conclude that the linear mixed-effects (LME) approximation suggested by Lindstrom and Bates, the Laplacian approximation, and Gaussian quadrature centered at the conditional modes of the random effects are quite accurate and computationally efficient. Gaussian quadrature centered at the expected value of the random effects is quite inaccurate for a smaller number of abscissas and computationally inefficient for a larger number of abscissas. Importance sampling is accurate, but quite inefficient computationally.     

A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows

The effectiveness of sparse matrix techniques for directly solving large-scale linear least-squares problems is severely limited if the system matrix A has one or more nearly dense rows. In this paper, we partition the rows of A into sparse rows and dense rows (A_s and A_d) and apply the Schur complement approach. A potential difficulty is that the reduced normal matrix AsTA_s is often rank-deficient, even if A is of full rank. To overcome this, we propose explicitly removing null columns of A_s and then employing a regularization parameter and using the resulting Cholesky factors as a preconditioner for an iterative solver applied to the symmetric indefinite reduced augmented system. We consider complete factorizations as well as incomplete Cholesky factorizations of the shifted reduced normal matrix. Numerical experiments are performed on a range of large least-squares problems arising from practical applications. These demonstrate the effectiveness of the proposed approach when combined with either a sparse parallel direct solver or a robust incomplete Cholesky factorization algorithm.     

Matrix stretching for sparse least squares problems

For linear least squares problems min _x ‖Ax − b‖₂, where A is sparse except for a few dense rows, a straightforward application of Cholesky or QR factorization will lead to catastrophic fill in the factor R. We consider handling such problems by a matrix stretching technique, where the dense rows are split into several more sparse rows. We develop both a recursive binary splitting algorithm and a more general splitting method. We show that for both schemes the stretched problem has the same set of solutions as the original least squares problem. Further, the condition number of the stretched problem differs from that of the original by only a modest factor, and hence the approach is numerically stable. Experimental results from applying the recursive binary scheme to a set of modified matrices from the Harwell‐Boeing collection are given. We conclude that when A has a small number of dense rows relative to its dimension, there is a significant gain in sparsity of the factor R. A crude estimate of the optimal number of splits is obtained by analysing a simple model problem. Copyright © 2000 John Wiley & Sons, Ltd.     

The use of generalized inverses in restricted maximum likelihood

The calculus of generalized inverses and related concepts in matrix algebra is applied to the general restricted maximum likelihood problem. Some new results on g-inverses, Kronecker products, and matrix differentials are presented. For the restricted maximum likelihood problem we obtain generalizations of the well-known results of Aitchison and Silvey [1]. We use the approach recently developed by Heijmans and Magnus [13, 14] to allow for non-i.i.d. observations. A nonlinear seemingly unrelated regressions model with possibly singular covariance matrix and linear restrictions (NLSURSR) is analyzed, and the linear expenditure system (LES) is discussed as a special case.