Search

We propose to compute a sparse approximate inverse Cholesky factor L of a dense covariance matrix \Theta by minimizing the Kullback--Leibler divergence between the Gaussian distributions \scrN (0, \Theta) and \scrN (0,L \top L 1), subject to a sparsity constraint. Surprisingly, this problem has a closed-form solution that can be computed efficiently, recovering the popular Vecchia approximation in spatial statistics. Based on recent results on the approximate sparsity of inverse Cholesky factors of \Theta obtained from pairwise evaluation of Green's functions of elliptic boundary-value problems at points \{xi\} 1\leq i\leq N \subset Rd, we propose an elimination ordering and sparsity pattern that allows us to compute \epsilon -approximate inverse Cholesky factors of such \Theta in computational complexity \scrO (N log(N/\epsilon)d) in space and \scrO (N log(N/\epsilon)2d) in time. To the best of our knowledge, this is the best asymptotic complexity for this class of problems. Furthermore, our method is embarrassingly parallel, automatically exploits low-dimensional structure in the data, and can perform Gaussian-process regression in linear (in N) space complexity. Motivated by its optimality properties, we propose applying our method to the joint covariance of training and prediction points in Gaussian-process regression, greatly improving stability and computational cost. Finally, we show how to apply our method to the important setting of Gaussian processes with additive noise, compromising neither accuracy nor computational complexity. [ABSTRACT FROM AUTHOR]

We present a fast direct solver for two-dimensional scattering problems, where an incident wave impinges on a penetrable medium with compact support. We represent the scattered field using a volume potential whose kernel is the outgoing Green's function for the exterior domain. Inserting this representation into the governing partial differential equation, we obtain an integral equation of Lippmann{Schwinger type. The principal contribution here is the development of an automatically adaptive, high-order accurate discretization based on a quad-tree data structure which provides rapid access to arbitrary elements of the discretized system matrix. This permits the straightforward application of state-of-the-art algorithms for constructing compressed versions of the solution operator. These solvers typically require O(N3/2) work, where N denotes the number of degrees of freedom. We demonstrate the performance of the method for a variety of problems in both low and high frequency regimes. [ABSTRACT FROM AUTHOR]