Faster Polytope Rounding, Sampling, and Volume Computation via a Sub-Linear Ball Walk
Faster Polytope Rounding, Sampling, and Volume Computation via a Sub-Linear Ball Walk
This paper studies the problem of "isotropically rounding" a polytope K ⊆ R^n, that is, computing a linear transformation which makes the uniform distribution on the polytope have roughly identity covariance matrix. It is assumed that K ⊆ R^n is defined by m linear inequalities. We introduce a new variant …