Approximate Bayesian computation

Approximate Bayesian computation (ABC) constitutes a class of computational methods rooted in Bayesian statistics that can be used to estimate the posterior distributions of model parameters. In all model-based statistical inference, the likelihood function is of central importance, since it expresses the probability of the observed data under a particular statistical model, and thus quantifies the support data lend to particular values of parameters and to choices among different models. For simple models, an analytical formula for the likelihood function can typically be derived. However, for more complex models, an analytical formula might be elusive or the likelihood function might be computationally very costly to evaluate. ABC methods bypass the evaluation of the likelihood function. In this way, ABC methods widen the realm of models for which statistical inference can be considered. ABC methods are mathematically well-founded, but they inevitably make assumptions and approxi

Finite Element Method on Riemann Surfaces and Applications to the Laplacian Spectrum

Marc Maintrot

The objective of this PhD thesis is the approximate computation of the solutions of the Spectral Problem associated with the Laplace operator on a compact Riemann surface without boundaries. A Riemann surface can be seen as a gluing of portions of the Hyperbolic Plane made with suitable conditions to obtain a 2 dimensional manifold. The solutions of the Spectral Problem associated with the Laplace operator are to be understood as the eigenfunctions defined on the surface and their corresponding eigenvalues. This work is separated into two parts: the first part describes the method used to approximate the eigenvalues and eigenfunctions, the second focuses on the design of a program to compute these approximations. The approximation method is inspired by the Finite Element Method (FEM), in that it relies on the variational expression of the Spectral Problem and the definition of a finite subspace of functions in which the approximated eigenvalues and eigenfunctions are computed. However, it differs from the FEM in that it removes the euclidian basis of the FEM and is invariant under the isometries of the Hyperbolic Plane. To ful fill this objective, we begin by geodesically triangulating the surface as regularly as possible. This hyperbolic triangulation allows us to de ne the finite subspace of functions by using the concept of barycentric coordinates associated with each vertex of the triangulation (idea introduced by Whitney and taken up by Dodziuk). We then prove that the approximated solutions convergence to the exact ones when the diameter of the triangulation decreases, as well as the order of convergence. The program is a practical application of the theoretical work and allows the computation of the approximated eigenfunctions and eigenvalues.

EPFL2012

Fast hierarchical solvers for symmetric eigenvalue problems

Ana Susnjara

In this thesis we address the computation of a spectral decomposition for symmetric banded matrices. In light of dealing with large-scale matrices, where classical dense linear algebra routines are not applicable, it is essential to design alternative techniques that take advantage of data properties. Our approach is based upon exploiting the underlying hierarchical low-rank structure in the intermediate results. Indeed, we study the computation in the hierarchically off-diagonal low rank (HODLR) format of two crucial tools: QR decomposition and spectral projectors, in order to devise a fast spectral divide-and-conquer method. In the first part we propose a new method for computing a QR decomposition of a HODLR matrix, where the factor R is returned in the HODLR format, while Q is given in a compact WY representation. The new algorithm enjoys linear-polylogarithmic complexity and is norm-wise accurate. Moreover, it maintains the orthogonality of the Q factor. The approximate computation of spectral projectors is addressed in the second part. This problem has raised some interest in the context of linear scaling electronic structure methods. There the presence of small spectral gaps brings difficulties to existing algorithms based on approximate sparsity. We propose a fast method based on a variant of the QDWH algorithm, and exploit that QDWH applied to a banded input generates a sequence of matrices that can be efficiently represented in the HODLR format. From the theoretical side, we provide an analysis of the structure preservation in the final outcome. More specifically, we derive a priori decay bounds on the singular values in the off-diagonal blocks of spectral projectors. Consequently, this shows that our method, based on data-sparsity, brings benefits in terms of memory requirements in comparison to approximate sparsity approaches, because of its logarithmic dependence on the spectral gap. Numerical experiments conducted on tridiagonal and banded matrices demonstrate that the proposed algorithm is robust with respect to the spectral gap and exhibits linear-polylogarithmic complexity. Furthermore, it renders very accurate approximations to the spectral projectors even for very large matrices. The last part of this thesis is concerned with developing a fast spectral divide-and-conquer method in the HODLR format. The idea behind this technique is to recursively split the spectrum, using invariant subspaces associated with its subsets. This allows to obtain a complete spectral decomposition by solving the smaller-sized problems. Following Nakatsukasa and Higham, we combine our method for the fast computation of spectral projectors with a novel technique for finding a basis for the range of such a HODLR matrix. The latter strongly relies on properties of spectral projectors, and it is analyzed theoretically. Numerical results confirm that the method is applicable for large-scale matrices, and exhibits linear-polylogarithmic complexity.

EPFL2018

The consequences of not accounting for background selection in demographic inference

Gregory Bruce Ewing, Jeffrey David Jensen

Recently, there has been increased awareness of the role of background selection (BGS) in both data analysis and modelling advances. However, BGS is still difficult to take into account because of tractability issues with simulations and difficulty with nonequilibrium demographic models. Often, simple rescaling adjustments of effective population size are used. However, there has been neither a proper characterization of how BGS could bias or shift inference when not properly taken into account, nor a thorough analysis of whether rescaling is a sufficient solution. Here, we carry out extensive simulations with BGS to determine biases and behaviour of demographic inference using an approximate Bayesian approach. We find that results can be positively misleading with significant bias, and describe the parameter space in which BGS models replicate observed neutral nonequilibrium expectations.

Wiley-Blackwell2016

Fast hierarchical solvers for symmetric eigenvalue problems

Ana Susnjara

EPFL2018