Neighborliness of randomly projected simplices in high dimensions

Abstract

Let A be a d × n matrix and T = T^{n -1} be the standard simplex in Rⁿ. Suppose that d and n are both large and comparable: d ≈ δn, δ ∈ (0, 1). We count the faces of the projected simplex AT when the projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of Rⁿ. We derive ρ_N(δ) > 0 with the property that, for any ρ < ρ_N(δ), with overwhelming probability for large d, the number of k-dimensional faces of P = AT is exactly the same as for T, for 0 ≤ k ≤ ρd. This implies that P is -neighborly, and its skeleton is combinatorially equivalent to . We also study a weaker notion of neighborliness where the numbers of k-dimensional faces f_k(P) ≥ f_k(T)(1 - ε). Vershik and Sporyshev previously showed existence of a threshold ρ_VS(δ) > 0 at which phase transition occurs in k/d. We compute and display ρ_VS and compare with ρ_N. Corollaries are as follows. (1) The convex hull of n Gaussian samples in R^d, with n large and proportional to d, has the same k-skeleton as the (n - 1) simplex, for k < ρ_N (d/n)d(1 + o_P(1)). (2) There is a “phase transition” in the ability of linear programming to find the sparsest nonnegative solution to systems of underdetermined linear equations. For most systems having a solution with fewer than ρ_VS(d/n)d(1 + o(1)) nonzeros, linear programming will find that solution.

• neighborly polytopes
• convex hull of Gaussian sample
• underdetermined systems of linear equations
• uniformly distributed random projections
• phase transitions