Uniform sampling from convex polytopes in high dimensions is very useful in many scientific fields and applications. The package volesti is a C++ software with an R interface in CRAN which provides 4 geometric random walks for uniform sampling from convex polytopes among other algorithms in the field of geometric statistics. A classical and difficult problem is to know when the Markov chain converges to the target distribution in order to stop sampling. Diagnostics are tools that can be used to check whether the quality of a sample generated with an MCMC algorithm is sufficient to provide an accurate approximation of the target distribution. The goals of this project are to provide: i) three diagnostic tools for a random walk to check convergence to the target distribution, ii) efficient implementations of all the known geometric random walks for uniform sampling from convex bodies, that are not implemented in volesti and iii) an improved implementation for Billiard walk which is already implemented in volesti. The diagnostic tools would allow us to compare the mixing time of various random walks, which is a classical and hard problem in high dimensional statistics.

Organization

Student

Alexandros Manochis

Mentors

  • Apostolos Chalkis
  • Vissarion Fisikopoulos
  • Haris Zafeiropoulos
  • Elias Tsigaridas
close

2020