Skip to content

Sampling from a parametric polynomial curve

Jump to bottom Edit New page
Vaibhav Thakkar edited this page Mar 25, 2021 · 8 revisions

Overview

Sampling from parametric polynomial curves is useful for numerous applications in control systems. This coding project considers n-dimensional parametric polynomial curves where each coordinate is given by a polynomial of degree k. The aim is to develop efficient open source software, expanding package volesti, to sample (near-)uniformly distributed points from the curve. The student will implement several methods in C++ and she/he will perform an extended empirical comparison and report on the results.

Related work

Sampling uniformly from a parametric polynomial curve is equivalent to sample from the velocity of the curve (i.e. the norm of the first order time derivatives of the parametric equations); that is sampling from the corresponding univariate probability density. The methods that has to be considered for sampling in this project are (i) Markov Chain Monte Carlo samplers (e.g. Metropolis Hastings, Hamiltonian Monte Carlo), (ii) Acceptance - Rejection sampling, (iii) Inverse transform sampling, (iv) slice sampling.

Details of your coding project

The student will implement in C++ (a) the 4 methods mentioned above, (b) visualization tools for the case of 2D and 3D, (c) expand the R interface exposing these methods. The student will finally perform empirical comparisons between the implemented methods.

Feel free to suggest new methods for sampling uniform points from a parametric polynomial curve.

Expected impact

The project will be a very useful addition to package volesti.

Mentors

  • Apostolos Chalkis <tolis.chal at gmail.com> is a PhD student in Computer Science. His research focuses on mathematical computing, optimization and computational finance. He has previous experience in GSoC 2018 and 2019 as a student under Org. R-project, implementing state-of-the-art algorithms for sampling from high dimensional multivariate distributions. He was GSOC mentor in three projects with Geomscale (2020). He is one of the authors of volesti.

  • Christina Katsamaki <chistina.katsamaki at inria.fr> is a PhD student at Sorbonne Université (Paris 6), in the laboratory IMJ-PRG. She is also a member of OURAGAN team at INRIA Paris. He is an expert on algebraic geometry, algorithmic theory and mathematical and geometric computing.

  • Josué Tonelli Cueto <josue.tonelli.cueto at gmail.com> is a postdoctoral researcher at INRIA Paris and the IMJ-PRG. He is an expert on numerical algorithms, condition-based complexity, computational algebraic geometry, and random geometry.

Students, please contact the first and the third mentor after completing at least one of the tests below.

Tests

Students, please do one or more of the following tests before contacting the mentors above.

  • Easy: compile and run volesti. Use the R extension to visualize sampling in a polytope.
  • Medium: Implement in C++ Acceptance-Rejection sampling for the case of a smooth univariate truncated density.
  • Hard: Implement in C++ Metropolis-Hastings for the case of a smooth univariate truncated density.

Solutions of tests

Students, please post a link to your test results here.

Add a custom footer
Add a custom sidebar
Clone this wiki locally