PCG Reading Group: Dingjun Bian

About this event

A Sharp Bound for Outer Radius of Random PolytopesAbstract: We study sharp bounds for the outer radius of random polytopes arising as feasible regions of random linear constraint systems. Let (\\xi) be a symmetric subgaussian random variable with mean zero and unit variance, and let (A) be an (m\\times n) random matrix whose entries are independent copies of (\\xi). We consider the random polytope $$ P_A={x\\in\\mathbb{R}^n:|Ax|_\\infty\\leq1}. $$ We prove that there are constants (C,c>0), depending only on the entry distribution, such that, for sufficien tly large (n) and (m\\geq Cn), the outer radius of (P_A) is at most one with probability at least (1-2e^{-cm}). The radius one is optimal over this class of distributions. I will explain how a dimension-free anti-concentration estimate, a decomposition into flat and spiky directions, and a net approximation give the result. By polarity, the theorem equivalently states that the convex hull of the signed rows of (A) has Euclidean inradius at least one with the same probability. This is joint work with my advisor, Konstantin Tikhomirov.s of Random Polytopes

Abstract:

We study sharp bounds for the outer radius of random polytopes arising as feasible regions of random linear constraint systems. Let (\\xi) be a symmetric subgaussian random variable with mean zero and unit variance, and let (A) be an (m\\times n) random matrix whose entries are independent copies of (\\xi). We consider the random polytope

$$ P_A={x\\in\\mathbb{R}^n:|Ax|_\\infty\\leq1}. $$

We prove that there are constants (C,c>0), depending only on the entry distribution, such that, fo r sufficiently large (n) and (m\\geq Cn), the outer radius of (P_A) is at most one with probability at least (1-2e^{-cm}). The radius one is optimal over this class of distributions.

I will explain how a dimension-free anti-concentration estimate, a decomposition into flat and spiky directions, and a net approximation give the result. By polarity, the theorem equivalently states that the convex hull of the signed rows of (A) has Euclidean inradius at least one with the same probability.

This is joint work with my advisor, Konstantin Tikhomirov.