Organization: R project for statistical computing

Project: Efficient R tools for geometrical statistics

Topic: Volume approximation and sampling in high dimensions

mentors: Vissarion Fisikopoulos, Zafeirakis Zafeirakopoulos

Student: Chalkis Apostolos


Final Evaluation

The main goal of this project was to create a R package, using Rcpp, based on the C++ package volesti. In addition, in the proposal we suggested to add volume computation for non-linear convex bodies and V-polytopes and sampling from convex bodies in high dimensions.
In bonding period we decided to implement the randomized practical algorithm of B. Cousins and S. Vempala (CV algorithm), for volume approximation, and to focus on V-polytopes and not to non-linear convex bodies.

The main repository for C++ package volesti is here.
For the CV algorithm exists a matlab implementation here.

Summarizing GSoC project we have succeeded the following goals:

  1. We have excluded CGAL library from the initial volesti C++ implementaion.
  2. We use RcppEigen and BH libraries in order to use Eigen and Boost libraries. To solve linear programs we use lpSolve library.
  3. We have developed a C++ implementation of CV algorithm for convex polytopes.
  4. We have added volume computation for V-polytopes, using either volesti or CV algorithm.
  5. In addition to Random Directions Hit and Run and Coordinate Directions Hit and Run, we have added ball walk method for the random walks that both algorithms require.
  6. We have implemented a R package, using Rcpp, that is able to call C++ implementaion and use all the above options.
  7. In the R package we give the additional option of sampling from a convex H or V-polytope with uniform or spherical gaussian target distribution.
  8. In the R package we give also the options of rounding and applying random rotation on a H or V-polytope.

You can see the branch that we have excluded CGAL from volesti and create a basic Rcpp interface here.

List of Pull Requests

If you want to comment on the documentation of the R package, you can do it here.

Further work

  • Create the final version of the R package after mentors’ evaluation and submit it to CRAN.
  • Continue working on V-polytopes’ volume approximation by improving parts of the current algorithms, i.e. V-polytope membership by using CppOptimizationLibrary library. Test new ideas and methods for V-polytopes.
  • Extend current implementation to non-linear convex and non-convex bodies.
  • Add implementations of financial applications for crisis prediction and financial modeling, that are described here.
  • Add more sampling options, i.e. different random walk algorithms or sampling from the boundary of a convex body.
  • TODO List here