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
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.
Summarizing GSoC project we have succeeded the following goals:
- We have excluded CGAL library from the initial volesti C++ implementaion.
- We use RcppEigen and BH libraries in order to use Eigen and Boost libraries. To solve linear programs we use lpSolve library.
- We have developed a C++ implementation of CV algorithm for convex polytopes.
- We have added volume computation for V-polytopes, using either volesti or CV algorithm.
- 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.
- We have implemented a R package, using Rcpp, that is able to call C++ implementaion and use all the above options.
- 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.
- 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
- Exclude CGAL dependencies
- Implementation of CV algorithm
- Replace StdMatrix with Eigen::Matrix
- Volume approximation for V-polytopes
- Improve and develop new function for the R package
- Improve rounding
If you want to comment on the documentation of the R package, you can do it here.
- 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