On the Isotropic Constant of Random Polytopes with Vertices on an $$\ell _p$$-Sphere

The symmetric convex hull of random points that are independent and distributed according to the cone probability measure on the \(\ell _p\)-unit sphere of \({{\mathbb {R}}}^n\) for some \(1\le p < \infty \) is considered. We prove that these random polytopes have uniformly absolutely bounded isotropic constants with overwhelming probability. This generalizes the result for the Euclidean sphere \((p=2)\) obtained by Alonso-Gutiérrez. The proof requires several different tools including a probabilistic representation of the cone measure due to Schechtman and Zinn and moment estimates for sums of independent random variables with log-concave tails originating in a paper of Gluskin and Kwapień.     

Stability Properties of Neighbourly Random Polytopes

We introduce a quantitative parameter measuring m-neighbourliness of symmetric convex polytopes in ℝ ^k . We discuss this parameter for random polytopes generated by subgaussian vectors and show its stability properties. Research of P. Mankiewicz was partially supported by KBN Grant no. 1 P03A 015 27. N. Tomczak-Jaegermann holds the Canada Research Chair in Geometric Analysis.     

An Inscribing Model for Random Polytopes

For convex bodies K with boundary in ℝ ^d , we explore random polytopes with vertices chosen along the boundary of K. In particular, we determine asymptotic properties of the volume of these random polytopes. We provide results concerning the variance and higher moments of this functional, as well as an analogous central limit theorem. The research of V.H. Vu was done under the support of A. Sloan Fellowship and an NSF Career Grant. The research of L. Wu is done while the author was at University of California San Diego.     

Multivariate Normal Approximation for Functionals of Random Polytopes

Journal of Theoretical Probability - Consider the random polytope that is given by the convex hull of a Poisson point process on a smooth convex body in $$\mathbb {R}^d$$ . We prove central limit...     

Banach-Mazur Distances and Projections on Random Subgaussian Polytopes

We consider polytopes in that are generated by N vectors in whose coordinates are independent subgaussian random variables. (A particular case of such polytopes are symmetric random polytopes generated by N independent vertices of the unit cube.) We show that for a random pair of such polytopes the Banach-Mazur distance between them is essentially of a maximal order n. This result is an analogue of the well-known Gluskin's result for spherical vectors. We also study the norms of projections on such polytopes and prove an analogue of Gluskin's and Szarek's results on basis constants. The proofs are based on a version of "small ball" estimates for linear images of random subgaussian vectors.     

Estimating Support Functions of Random Polytopes via Orlicz Norms

We study the expected value of support functions of random polytopes in a certain direction, where the random polytope is given by independent random vectors uniformly distributed in an isotropic convex body. All results are obtained using probabilistic estimates in terms of Orlicz norms that were not used in this connection before.     

Efficient Computation of the Hausdorff Distance Between Polytopes by Exterior Random Covering

In this paper, a simple yet efficient randomized algorithm (Exterior Random Covering) for finding the maximum distance from a point set to an arbitrary compact set in R^d is presented. This algorithm can be used for accelerating the computation of the Hausdorff distance between complex polytopes.     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi.     

On the Lp Minkowski Problem for Polytopes

Two new approaches are presented to establish the existence of polytopal solutions to the discrete-data L_p Minkowski problem for all p > 1.     

On the Orlicz Minkowski Problem for Polytopes

Quite recently, an Orlicz Minkowski problem has been posed and the existence part of this problem for even measures has been presented. In this paper, the existence part of the Orlicz Minkowski problem for polytopes is demonstrated. Furthermore, we obtain a solution of the Orlicz Minkowski problem for general (not necessarily even) measures.     

On the Discrepancy for Boxes and Polytopes

 We consider so-called Tusnády’s problem in dimension d: Given an n-point set P in R ^d , color the points of P red or blue in such a way that for any d-dimensional interval B, the number of red points in differs from the number of blue points in by at most Δ, where should be as small as possible. We slightly improve previous results of Beck, Bohus, and Srinivasan by showing that , with a simple proof. The same asymptotic bound is shown for an analogous problem where B is allowed to be any translated and scaled copy of a fixed convex polytope A in R ^d . Here the constant of proportionality depends on A and we give an explicit estimate. The same asymptotic bounds also follow for the Lebesgue-measure discrepancy, which improves and simplifies results of Beck and of Károlyi. Received 17 November 1997; in revised form 30 July 1998     

On Facets of Knapsack Equality Polytopes

The 0/1 knapsack equality polytope is, by definition, the convex hull of 0/1 solutions of a single linear equation. A special form of this polytope, where the defining linear equation has nonnegative integer coefficients and the number of variables having coefficient one exceeds the right-hand side, is considered. Equality constraints of this form arose in a real-world application of integer programming to a truck dispatching scheduling problem. Families of facet defining inequalities for this polytope are identified, and complete linear inequality representations are obtained for some classes of polytopes.     

凸体的对偶迷向常数与LYZ椭球

研究了凸体处于对偶迷向位置时的解析特征,并建立了凸体对偶迷向常数的新的下界;其次,证明了关于原点中心对称凸体的LYZ椭球与John椭球相等的充要条件;最后,举例具体计算了几个凸多边形的LYZ椭球和John椭球,以进一步认清两者的差别.     

Estimation Problems for Periodically Correlated Isotropic Random Fields

Spectral theory of isotropic random fields in Euclidean space developed by M. I. Yadrenko is exploited to find a solution to the problem of optimal linear estimation of the functional

$$ A\zeta ={\sum\limits_{t=0}^{\infty}}\,\,\,{\int_{S_n}} \,\,a(t,x)\zeta (t,x)\,m_n(dx) $$

which depends on unknown values of a periodically correlated (cyclostationary with period T) with respect to time isotropic on the sphere S _n in Euclidean space E ⁿ random field ζ(t, x), t?∈?Z, x?∈?S _n . Estimates are based on observations of the field ζ(t, x)?+?θ(t, x) at points (t, x), t?=???1,???2, ..., x?∈?S _n , where θ(t, x) is an uncorrelated with ζ(t, x) periodically correlated with respect to time isotropic on the sphere S _n random field. Formulas for computing the value of the mean-square error and the spectral characteristic of the optimal linear estimate of the functional Aζ are obtained. The least favourable spectral densities and the minimax (robust) spectral characteristics of the optimal estimates of the functional Aζ are determined for some special classes of spectral densities.

     

Time Varying Isotropic Vector Random Fields on Spheres

For a vector random field that is isotropic and mean square continuous on a sphere and stationary on a temporal domain, this paper derives a general form of its covariance matrix function and provides a series representation for the random field, which involve the ultraspherical polynomials. The series representation is somehow an imitator of the covariance matrix function, but differs from the spectral representation in terms of the ordinary spherical harmonics, and is useful for modeling and simulation. Some semiparametric models are also illustrated.     

Modeling Gaussian Isotropic Random Fields on a Sphere

We construct models of Gaussian isotropic random fields on a sphere in an n-dimensional space. The models approximate the fields with a given reliability and accuracy in the space L _p , p 2.     

Error Bounds for Consistent Reconstruction: Random Polytopes and Coverage Processes

Consistent reconstruction is a method for producing an estimate \(\widetilde{x} \in {\mathbb {R}}^d\) of a signal \(x\in {\mathbb {R}}^d\) if one is given a collection of \(N\) noisy linear measurements \(q_n = \langle x, \varphi _n \rangle + \epsilon _n\), \(1 \le n \le N\), that have been corrupted by i.i.d. uniform noise \(\{\epsilon _n\}_{n=1}^N\). We prove mean-squared error bounds for consistent reconstruction when the measurement vectors \(\{\varphi _n\}_{n=1}^N\subset {\mathbb {R}}^d\) are drawn independently at random from a suitable distribution on the unit-sphere \({\mathbb {S}}^{d-1}\). Our main results prove that the mean-squared error (MSE) for consistent reconstruction is of the optimal order \({\mathbb {E}}\Vert x - \widetilde{x}\Vert ^2 \le K\delta ^2/N^2\) under general conditions on the measurement vectors. We also prove refined MSE bounds when the measurement vectors are i.i.d. uniformly distributed on the unit-sphere \({\mathbb {S}}^{d-1}\) and, in particular, show that in this case, the constant \(K\) is dominated by \(d^3\), the cube of the ambient dimension. The proofs involve an analysis of random polytopes using coverage processes on the sphere.     

The Probability Content of Cones in Isotropic Random Fields

This paper provides computable representations for the evaluation of the probability content of cones in isotropic random fields. A decomposition of quadratic forms in spherically symmetric random vectors is obtained and a representation of their moments is derived in terms of finite sums. These results are combined to obtain the distribution function of quadratic forms in spherically symmetric or central elliptically contoured random vectors. Some numerical examples involving the sample serial covariance are provided. Ratios of quadratic forms are also discussed.