首页|Efficient sampling in spectrahedra and volume approximation
Efficient sampling in spectrahedra and volume approximation
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
We present algorithmic, complexity, and implementation re-sults on the problem of sampling points from a spectrahedron, that is, the feasible region of a semidefinite program. Our main tool is geometric random walks. We analyze the arithmetic and bit complexity of certain primitive geometric operations that are based on the algebraic properties of spec-trahedra and the polynomial eigenvalue problem. This study leads to the implementation of a broad collection of random walks for sampling from spectrahedra that experimentally show faster mixing times than methods currently employed either in theoretical studies or in applications, including the popular family of Hit-and-Run walks. The different random walks offer a variety of advantages, thus allowing us to ef-ficiently sample from general probability distributions, for example the family of log-concave distributions which arise in numerous applications. We focus on two major applica-tions of independent interest: (i) approximate the volume of a spectrahedron, and (ii) compute the expectation of functions coming from robust optimal control.We exploit efficient linear algebra algorithms and implemen-tations to address the aforementioned computations in very high dimension. In particular, we provide a C++ open source implementation of our methods that scales efficiently, for the first time, up to dimension 200. We illustrate its efficiency on various data sets.(c) 2022 Elsevier Inc. All rights reserved.
NSTL
Elsevier
