Volume-and-Sampling

Code for high-dimensional volume computation, Gaussian integration, and uniform/Gaussian sampling
924 Downloads
Updated 18 Jun 2022

We give a randomized algorithm to estimate the volume within a target relative error. The algorithm can compute a reasonable estimate for the volume of 100-dimensional bodies within a few minutes.
The implementation needs a description of a convex body as the intersection of halfspaces and an ellipsoid (only one of these must be non-empty, e.g. a polytope is only described by halfspaces). The algorithm works in a series of phases, which start out with a distribution very concentrated around a single point inside the body and slowly flatten to the uniform distribution (i.e. the volume). In each phase, a sequence of sample points from a Markov chain is used to estimate the change in volume. When a phase is sufficiently close to the uniform distribution, we will have an estimate for the volume.
In addition to the volume (i.e. uniform distribution), it can also estimate the volume of a spherical Gaussian restricted to a convex set. Also, it can compute approximate samples from a convex body, with respect to the uniform distribution or a spherical Gaussian.

This package was developed in collaboration with Santosh Vempala.

Cite As

Consider citing http://mpc.zib.de/index.php/MPC/article/view/178/99

MATLAB Release Compatibility
Created with R2015a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

external/NearestSymmetricPositiveDefinite/NearestSymmetricPositiveDefinite

Versions that use the GitHub default branch cannot be downloaded

Version Published Release Notes
2.2.1

Update citation text.

2.2

Connected matlab version to github version that is more updated.

2.1.0.0

Minor improvements to plotting functionality.

2.0.0.0

Added coordinate hit-and-run as the default Markov chain. Also, functionality to preprocess and compute the volume of a lower dimensional polytope.

1.7.0.0

New version not uploaded properly (again).

1.6.0.0

Added zonotope functionality. Also fixed small bugs with rounding and ellipsoids.

1.5.0.0

New version was not uploaded properly.

1.4.0.0

Added function to sample from a convex body. Also added Birkhoff polytope as a built-in convex body.

1.1.0.0

Updated README.

1.0.0.0

To view or report issues in this GitHub add-on, visit the GitHub Repository.
To view or report issues in this GitHub add-on, visit the GitHub Repository.