Efficient sampling in spectrahedra and volume approximation

DOI10.1016/J.LAA.2022.04.002zbMATH Open1489.90105arXiv2010.03817OpenAlexW4225384330WikidataQ114151654 ScholiaQ114151654MaRDI QIDQ2144244FDOQ2144244

Authors: Apostolos Chalkis, Ioannis Z. Emiris, Vissarion Fisikopoulos, Panagiotis Repouskos, Elias P. Tsigaridas 

Publication date: 1 June 2022

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: We present algorithmic, complexity, and implementation results 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 spectrahedra 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 efficiently sample from general probability distributions, for example the family of log-concave distributions which arise in numerous applications. We focus on two major applications 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 implementations to address the aforemen-tioned 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.

Full work available at URL: https://arxiv.org/abs/2010.03817

Recommendations

• Efficient random-walk methods for approximating polytope volume
• scientific article; zbMATH DE number 1859219
• Sampling and approximation of bandlimited volumetric data
• A fast direct sampling algorithm for equilateral closed polygons
• Efficient Delaunay mesh generation from sampled scalar functions
• Efficient numerical methods in non-uniform sampling theory
• An Optimal-Dimensionality Sampling Scheme on the Sphere With Fast Spherical Harmonic Transforms
• Fast MCMC sampling algorithms on polytopes
• Non-parametric sampling approximation via Voronoi tessellations

zbMATH Keywords

samplingoptimizationrandom walkMonte Carlopolynomial eigenvalue problemvolume approximationsemidefinite-programmingspectahedron

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Complexity and performance of numerical algorithms (65Y20) Eigenvalues, singular values, and eigenvectors (15A18) Semidefinite programming (90C22) Computational aspects related to convexity (52B55) Numerical approximation and computational geometry (primarily algorithms) (65D99) Numerical solution of nonlinear eigenvalue and eigenvector problems (65H17)

Cites Work

• Title not available (Why is that?)
• Condition. The geometry of numerical algorithms
• Title not available (Why is that?)
• On the complexity of computing determinants
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Random walks and anO*(n5) volume algorithm for convex bodies
• Semidefinite Optimization and Convex Algebraic Geometry
• Title not available (Why is that?)
• Title not available (Why is that?)
• Perturbation theory for homogeneous polynomial eigenvalue problems
• Title not available (Why is that?)
• Vector Spaces of Linearizations for Matrix Polynomials
• Symmetric Linearizations for Matrix Polynomials
• Sylvester-Habicht sequences and fast Cauchy index computation
• A survey of computational complexity results in systems and control
• Efficient estimation of covariance selection models
• Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm
• A practical volume algorithm
• A randomized cutting plane method with probabilistic geometric convergence
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0)
• Approximate volume and integration for basic semialgebraic sets
• Simulated Annealing for Convex Optimization
• Separation bounds for polynomial systems
• Nearly optimal refinement of real roots of a univariate polynomial
• A Monte Carlo approach to the analysis of control system robustness
• The \(D\)-decomposition technique for linear matrix inequalities
• Compact rational Krylov methods for nonlinear eigenvalue problems
• The nonlinear eigenvalue problem
• The Polynomial Eigenvalue Problem is Well Conditioned for Random Inputs
• Practical polytope volume approximation
• On the complexity of the Lickteig-Roy subresultant algorithm
• Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation
• Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets
• Computing the volume of compact semi-algebraic sets
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication
• Sampling the feasible sets of SDPs and volume approximation
• Random spectrahedra

Cited In (3)

• Sampling inequalities for anisotropic tensor product grids
• Random spectrahedra
• Sampling the feasible sets of SDPs and volume approximation

Uses Software

• Eigen
• Spectra
• VolEsti
• Billiard walk
• tmg

This page was built for publication: Efficient sampling in spectrahedra and volume approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2144244)