Higher-Order Hit-&-Run Samplers for Linearly Constrained Densities

{Markov} chain Monte Carlo ({MCMC}) sampling of densities restricted to linearly constrained domains is an important task arising in {Bayesian} treatment of inverse problems in the natural sciences. While efficient algorithms for uniform polytope sampling exist, much less work has dealt with more complex constrained densities. In particular, gradient information as used in unconstrained {MCMC} is not necessarily helpful in the constrained case, where the gradient may push the proposal’s density out of the polytope. In this work, we propose a novel constrained sampling algorithm, which combines strengths of higher-order information, like the target’s log-density’s gradients and curvature, with the Hit-&-Run proposal, a simple mechanism which guarantees the generation of feasible proposals, fulfilling the linear constraints. Our extensive experiments demonstrate improved sampling efficiency on complex constrained densities over various constrained and unconstrained samplers.